社区讨论
调高精调绝望了求调+一关
P1080[NOIP 2012 提高组] 国王游戏参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mknmk6rn
- 此快照首次捕获于
- 2026/01/21 14:11 2 个月前
- 此快照最后确认于
- 2026/01/24 18:15 上个月
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
string a;
int b, dis[4007], len, val;
}ma[1007];
int n, tot = 0;
string mul, ans1[5007];
int cmp(node a, node b){
if(a.len != b.len){
return a.len < b.len;
}else{
for(int i = a.len - 1;i >= 0;--i){
if(a.dis[i] != b.dis[i]){
return a.dis[i] < b.dis[i];
}
}
return a.len > b.len;
}
}
int cmp1(string a, string b){
if(a.size() != b.size()){
return a.size() < b.size();
}else{
for(int i = a.size() - 1;i >= 0;--i){
if(a[i] != b[i]){
return a[i] < b[i];
}
}
return a.size() > b.size();
}
}
void mull(string a, int b, int p){
for(int i = 0;i < a.size();++i){
ma[p].dis[i] = (a[i] - '0') * b;
}
for(int i = 0;i < a.size();++i){
ma[p].dis[i + 1] += (ma[p].dis[i] - (ma[p].dis[i] % 10)) / 10;
ma[p].dis[i] = ma[p].dis[i] % 10;
}
if(ma[p].dis[a.size()] == 0){
ma[p].len = a.size();
}else{
if(ma[p].dis[a.size()] <= 10){
ma[p].len = a.size() + 1;
}else{
for(int i = a.size();ma[p].dis[i] >= 10;++i){
ma[p].dis[i + 1] += (ma[p].dis[i] - (ma[p].dis[i] % 10)) / 10;
ma[p].dis[i] = ma[p].dis[i] % 10;
if(ma[p].dis[i + 1] <= 10){
ma[p].len = i + 2;
}
}
}
}
}
void mul1(string a, int b){
int ans[5007], len;
for(int i = 0;i < a.size();++i){
ans[i] = (a[i] - '0') * b;
}
for(int i = 0;i < a.size();++i){
ans[i + 1] += (ans[i] - (ans[i] % 10)) / 10;
ans[i] %= 10;
}
if(ans[a.size()] == 0){
len = a.size();
}else{
if(ans[a.size()] <= 10){
len = a.size() + 1;
}else{
for(int i = a.size();ans[i] >= 10;++i){
ans[i + 1] += (ans[i] - (ans[i] % 10)) / 10;
ans[i] = ans[i] % 10;
if(ans[i + 1] <= 10){
len = i + 2;
}
}
}
}
mul.resize(len);
for(int i = 0;i < len;++i){
mul[i] = ans[i] + '0';
}
}
void divide(string a, int b){
int ans[5007], r = 0, c;
for(int i = a.size() - 1;i >= 0;--i){
c = r * 10 + a[i] - '0';
ans[i] = (c - (c % b)) / b;
r = c % b;
}
int sum = 0, len = 0;
tot++;
for(int i = a.size() - 1;i >= 0;--i){
if(ans[i] != 0){
len = i;
break;
}
}
ans1[tot].resize(len + 1);
for(int i = len;i >= 0;--i){
ans1[tot][i] = ans[i] + '0';
}
reverse(ans1[tot].begin(), ans1[tot].end());
}
signed main(){
cin >> n;
cin >> ma[0].a >> ma[0].b;
for(int i = 1;i <= n;++i){
cin >> ma[i].a >> ma[i].b;
reverse(ma[i].a.begin(), ma[i].a.end());
mull(ma[i].a, ma[i].b, i);
}
sort(ma + 1, ma + n + 1, cmp);
for(int i = 0;i <= n;++i){
for(int j = ma[i].a.size() - 1;j >= 0;--j){
ma[i].val *= 10;
ma[i].val += (ma[i].a[j] - '0');
}
}
mul = "1";
for(int i = 1;i <= n;++i){
mul1(mul, ma[i - 1].val);
divide(mul, ma[i].b);
}
sort(ans1 + 1, ans1 + tot + 1, cmp1);
cout << ans1[tot];
return 0;
}
#5in
LATEX100
70 94
43 9
92 18
18 9
86 31
24 32
46 49
23 69
40 56
27 75
28 85
37 29
99 80
44 70
14 9
30 38
46 32
93 87
42 49
35 60
99 73
57 8
38 35
73 33
6 32
10 36
78 75
49 98
50 48
91 78
18 3
86 24
18 84
27 28
83 25
15 95
38 18
50 89
79 9
3 17
1 52
74 32
76 99
24 36
9 43
93 7
65 27
36 84
75 31
94 44
33 2
85 5
42 18
4 33
45 84
92 87
86 34
36 44
61 59
59 28
1 97
60 23
9 64
96 47
57 100
90 7
54 93
17 30
71 23
72 32
14 95
48 40
27 15
92 78
52 11
93 21
56 60
22 47
21 58
89 11
29 13
36 14
95 91
47 12
16 36
19 80
19 92
73 68
66 1
53 97
13 60
83 5
63 99
98 37
2 67
84 95
26 60
63 33
2 78
91 38
9 31
ans:
LATEX2166489661101032350678866897536628698296804147316726878162441737980268621335310233327258927458239967674879428851028800069063620140885606400000000000000000
out:
LATEX216648966110103235067886689753662869829680414731672687816244173798026862133531023332725892745823996767487942885102880006906362014088560640000000000000000
/*少一个0*/
回复
共 1 条回复,欢迎继续交流。
正在加载回复...