社区讨论

调高精调绝望了求调+一关

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
LATEX
100
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:
LATEX
2166489661101032350678866897536628698296804147316726878162441737980268621335310233327258927458239967674879428851028800069063620140885606400000000000000000
out:
LATEX
216648966110103235067886689753662869829680414731672687816244173798026862133531023332725892745823996767487942885102880006906362014088560640000000000000000
/*少一个0*/

回复

1 条回复,欢迎继续交流。

正在加载回复...