国王游戏,高精度完全模板

Posted by Cww97 on 2018-10-27

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/83450847
为啥是这贪心策略啥的我就不细说了

一开始高精除高精除的TLE了,然后就改成了高精除单精,java,py用多了这个板子还真是欠修理

这里就是补充一哈高精度的模板

加减乘除,完整的输入输出体系,支持各种进制 default B = 10

还有啥呢,完善的运算符重载,写 bign 的时候和写 int 感觉不到什么区别

当然板子还没达到完美的地步(写一题修一次板子)

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1003;
const int MAXN = 3003;
int B = 10;

struct bign{ // big number
int len, s[MAXN];

bign (){
memset(s, 0, sizeof(s));
len = 1;
}
bign (int num) { *this = num; }
bign (const char *num) { *this = num; }

bign operator = (const int num){
char s[MAXN];
sprintf(s, "%d", num);
*this = s;
return *this;
}

void clean(){
while(len > 1 && !s[len-1]) len--;
}

bign operator = (const char *num){
memset(s, 0, sizeof s);
len = strlen(num);
for(int i = 0; i < len; i++) {
if (isdigit(num[len-i-1])) s[i] = num[len-i-1] - '0';
else s[i] = num[len-i-1] - 'A' + 10;
}
clean();
return *this;
}

bign operator + (const bign &b) const{
bign c;
c.len = max(len, b.len);
for (int i = 0; i < c.len; i++){
c.s[i] += s[i] + b.s[i];
c.s[i+1] += c.s[i] / B; // B default = 10
c.s[i] %= B;
}
if (c.s[c.len]) c.len++;
c.clean();
return c;
}

bign operator += (const bign &b){
*this = *this + b;
return *this;
}

bign operator * (const bign &b) {//*
bign c;
c.len = len + b.len;
for(int i = 0; i < len; i++)
for(int j = 0; j < b.len; j++){
c.s[i+j] += s[i] * b.s[j];
}

for(int i = 0; i < c.len; i++){
c.s[i+1] += c.s[i]/10;
c.s[i] %= 10;
}

c.clean();
return c;
}
bign operator *= (const bign &b){
*this = *this * b;
return *this;
}
bign operator - (const bign &b){
bign c;
c.len = 0;
for(int i = 0, g = 0; i < len; i++){
int x = s[i] - g;
if(i < b.len) x -= b.s[i];
if(x >= 0) g = 0;
else{
g = 1;
x += 10;
}
c.s[c.len++] = x;
}
c.clean();
return c;
}
bign operator -= (const bign &b){
*this = *this - b;
return *this;
}
bign operator / (const int &b){
int f = 0;
bign c;
for (int i = len-1; i >= 0; i--){
f = f *10 + s[i];
c.s[i] = f / b;
f %= b;
}
c.len = len;
c.clean();
return c;
}
bign operator / (const bign &b){
bign c, f = 0;
for(int i = len-1; i >= 0; i--){

f = f*10; // f = 0
f.s[0] = s[i]; // f = 1
while(f > b || f == b){

f -= b;
c.s[i]++;
}
}
c.len = len;
c.clean();
return c;
}
bign operator /= (const bign &b){
*this = *this / b;
return *this;
}
bign operator % (const bign &b){
bign r = *this / b;
r = *this - r*b;
return r;
}
bign operator %= (const bign &b){
*this = *this % b;
return *this;
}

bool operator < (const bign &b){
if(len != b.len) return len < b.len;
for(int i = len-1; i >= 0; i--){
if(s[i] != b.s[i]) return s[i] < b.s[i];
}
return false;
}

bool operator > (const bign &b){
if(len != b.len) return len > b.len;
for(int i = len-1; i >= 0; i--){
if(s[i] != b.s[i]) return s[i] > b.s[i];
}
return false;
}

bool operator == (const bign &b){
return !(*this > b) && !(*this < b);
}

string str() const{
string res = ""; // result
for (int i = 0; i < len; i++) {
if (s[i] < 10) res = char(s[i]+'0') + res;
else res = char(s[i] + 'A' - 10) + res;
}
return res;
}
} a, b, c;

struct people{
int l, r, mon;

void scan(int i){
scanf("%d %d", &l, &r);
mon = r * l;
}

bool operator < (const people &b)const{
if(mon != b.mon) return mon < b.mon;
return r < b.r;
}
}peo[N];

int main() {
//freopen("in.txt", "r", stdin);
int n;
scanf("%d", &n);
for(int i = 0; i <= n; i++){
peo[i].scan(i);
}

sort(peo + 1, peo + 1+n);

bign mone = peo[0].l, ans = 0;
for(int i = 1; i <= n; i++){
bign tmp = (mone / peo[i].r);
if (tmp > ans) ans = tmp;
mone *= bign(peo[i].l);
}
cout << ans.str() << endl;
return 0;
}

啥时候不这么困再写个py和java版本的吧