NOIP2019 pj备战计划-6

Task pj试炼场2-6(续)

T8 P1080

debug了不知道多久

【吐血】看错题目了,其实不用高精加,要高精除(高精除以低精就行了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll ans1[100000];
string s,maxx="";
struct node
{
ll a,b;
string c,d;
string sum;
}p[1005];
bool cmp(node x,node y)
{
return (x.a*x.b)<(y.a*y.b);
}
string time_(string a,string b)
{
memset(ans1,0,sizeof(ans1));
string ans="";
int len1=a.length(),len2=b.length();
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
{
ans1[i+j]+=(a[len1-i-1]-'0')*(b[len2-j-1]-'0');
ans1[i+j+1]+=ans1[i+j]/10;
ans1[i+j]%=10;
}
int len=10000;
while(ans1[len]==0)len--;
//cout<<len<<endl;
for(int i=len;i>=0;i--)
{
// cout<<ans1[i];
ans=ans+(char)(ans1[i]+'0');
}
return ans;
}// 1 10 3 2 2
string chu(string a,ll b)
{
string ans="";
memset(ans1,0,sizeof(ans1));
int len=a.length();
ll rm=0;
for(int i=0;i<len;i++)
{
ans1[i]=(rm*10+(a[i]-'0'))/b;
rm=(rm*10+(a[i]-'0'))%b;
}
ll t=0;
while(ans1[t]==0&&t!=len-1)
{
t++;
}
//cout<<t<<endl;
if(len<=t)ans=ans+'0';
else
{
for(int i=t;i<len;i++)
{
//cout<<ans1[i]<<endl;
ans=ans+(char)(ans1[i]+'0');
}
}

return ans;
}
bool compare(string a1,string a2)//a1是否大于a2
{
int len1=a1.length(),len2=a2.length();
if(len1<len2)return 0;
if(len1>len2)return 1;
for(int i=0;i<len1;i++)
{
if(a1[i]<a2[i])return 0;
if(a1[i]>a2[i])return 1;
}
}
int main()
{
scanf("%lld%lld%lld",&n,&p[0].a,&p[0].b);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&p[i].a,&p[i].b);
}
sort(p+1,p+n+1,cmp);
for(int i=0;i<=n;i++)
{
while(p[i].a)
{
p[i].c=(char)(p[i].a%10+'0')+p[i].c;
p[i].a/=10;
}
}
s=p[0].c;
//cout<<p[0].c<<" "<<p[1].c<<endl;
//cout<<time_(p[0].c,p[1].c)<<endl;
//cout<chu(p[1].c,p[1].b)<<endl;
for(int i=1;i<=n;i++)
{
p[i].sum=chu(s,p[i].b);
//cout<<s<<endl;
//cout<<p[i].sum<<endl;
if(compare(p[i].sum,maxx))maxx=p[i].sum;
s=time_(s,p[i].c);
}
cout<<maxx<<endl;
}