2014 ACM/ICPC Asia Regional Shanghai Online 题解

负责出了一场网络赛,勉勉强强算是顺利过去了,虽然产生了很多意外~~

本场共有12道题,教练提供了3个题给我,学弟shumj出的1011的LCT。 然后本来这场是11个题的,开场前教练担心爆零的比较多,临时叫我加了一个水题,就是1012了。 搞完这场网络赛,估计被喷出翔了, 虽然有个别题我卡的比较紧,但是也算卡的合理的,其他题目的时限都是比较宽的了. 出题一般我都会弃掉恶心的模拟,代码量很大的题,这里的题目感觉代码量都比较小。。 但是我一般出题也出模板题, 就是来拼模板的,怕不怕!! 比较抱歉的就是1001和1008的Rejudge. 出题最不应该rejudge了, 但是因为没有好的tester. 大部分题是我自己出,自己当的tester. 1001数据是没有问题的,是OJ数据上传出现问题,然后及时加上数据。 主要是1008,因为这题我暴力对拍过的,感觉数据是正确的,也没有仔细检查。 然后比赛过程中发现我的暴力对拍写错,标程也犯了一样的错误,然后修正后两个吻合了! 然后就出现了1008的Rejudge! 为两次Rejudge以及各种卡常数,表示深深的歉意! 我就是这么弱! 没办法。 这也算是退役前出的最后一场比赛吧! 下面是简单题解。

1001: HDU5042 这一题其实主要就是因为GCD是分段的,所以分成一段一段去搞就可以了。 就是说,可能 [l,r1] ….[l,r2] 的gcd都是一样的。 因为如果 是 [l,r]之间的gcd的话, 随着r的增大,这个值是不增的,所以最多分成了log(10^5)段. 然后就可以胡搞了,当然也可以使用ST去求gcd,然后也可以搞出来。 这一题前面出现一片RE, 然后检查数据发现OJ没传上数据,然后进行了修正。

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
/* ***************

Author :kuangbin

Created Time :2014/9/5 15:28:45

File Name :A.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MAXN = 100010;

long long gcd(long long a,long long b){

if(b == 0)return a;

return gcd(b,a%b);

}

int F[MAXN];

int find(int x){

if(F[x] == -1)return x;

return F[x] = find(F[x]);

}

void bing(int x,int y){

int t1 = find(x);

int t2 = find(y);

if(t1 != t2)F[t2] = t1;

}

int a[MAXN];

struct Node1{

int r1,r2;

int val;

Node1(int _r1 = 0,int _r2 = 0,int _val = 0){

r1 = _r1;

r2 = _r2;

val = _val;

}

bool operator <(const Node1 &b)const{

if(r1 != b.r1)return r1 < b.r1;

else r2 < b.r2;

}

};

vector<Node1>vec1[MAXN];

struct Node2{

int l,r1,r2;

long long sum;

Node2(int _l = 0,int _r1 = 0,int _r2 = 0){

l = _l;

r1 = _r1;

r2 = _r2;

}

bool operator <(const Node2 &b)const{

if(l != b.l)return l < b.l;

else return r1 < b.r1;

}

};

vector<Node2>vec2[MAXN];

int num1[MAXN];

int b[MAXN];

int main()

{

//freopen("A.in","r",stdin);

//freopen("A.out","w",stdout);

int T;

scanf("%d",&T);

assert(T <= 10);

int n,Q;

int iCase = 0;

while(T--){

iCase++;

printf("Case #%d:\n",iCase);

scanf("%d%d",&n,&Q);

assert(n >= 1 && n <= 100000 && Q >= 1 && Q <= 100000);

int Max = 1;

for(int i = 1;i <= n;i++){

scanf("%d",&a[i]);

assert(a[i] >= 1 && a[i] <= 100000);

vec1[i].clear();

Max = max(Max,a[i]);

}

for(int i = 1;i <= Max;i++)vec2[i].clear();

F[n+1] = -1;

for(int i = n;i >= 1;i--){

F[i] = -1;

int start = i;

int pre = i;

b[i] = a[i];

for(int j = find(i+1);j <= n;j = find(j+1)){

b[j] = gcd(a[i],b[j]);

if(b[j] != b[pre]){

vec1[i].push_back(Node1(start,pre,b[pre]));

vec2[b[pre]].push_back(Node2(i,start,pre));

start = pre+1;

}

else bing(j,pre);

pre = j;

}

vec1[i].push_back(Node1(start,n,b[n]));

vec2[b[n]].push_back(Node2(i,start,n));

sort(vec1[i].begin(),vec1[i].end());

/*

printf("i %d\n",i);

int sz = vec1[i].size();

for(int j = 0;j < sz;j++)

printf("%d %d %d\n",vec1[i][j].r1,vec1[i][j].r2,vec1[i][j].val);

*/

}

num1[0] = 0;

for(int i = 1;i <= Max;i++){

sort(vec2[i].begin(),vec2[i].end());

int sz = vec2[i].size();

if(sz)num1[i] = num1[i-1]+1;

else num1[i] = num1[i-1];

for(int j = 0;j < sz;j++){

if(j == 0)vec2[i][j].sum = 0;

else vec2[i][j].sum = vec2[i][j-1].sum;

vec2[i][j].sum += vec2[i][j].r2-vec2[i][j].r1+1;

}

/*

printf("i: %d\n",i);

printf("num1:%d\n",num1[i]);

for(int j = 0;j < sz;j++)

printf("%d %d %d %I64d\n",vec2[i][j].l,vec2[i][j].r1,vec2[i][j].r2,vec2[i][j].sum);

*/

}

char op[20];

long long k1,k2;

while(Q--){

scanf("%s%I64d%I64d",op,&k1,&k2);

if(op[0] == 'R'){

assert(k1 >= 1 && k1 <= k2 && k2 <= n);

int id ;

int sz = vec1[k1].size();

int l = 0, r = sz-1;

while(l <= r){

int mid = (l+r)/2;

if(vec1[k1][mid].r1 <= k2 && k2 <= vec1[k1][mid].r2){

id = mid;

break;

}

else if(vec1[k1][mid].r2 < k2)l = mid+1;

else r = mid-1;

}

int val = vec1[k1][id].val;

int ans1 = num1[val];

id = lower_bound(vec2[val].begin(),vec2[val].end(),Node2(k1,0,0)) - vec2[val].begin();

long long ans2;

if(id == 0)ans2 = k2 - vec2[val][id].r1 + 1;

else ans2 = vec2[val][id-1].sum + k2 - vec2[val][id].r1 + 1;

printf("%d %I64d\n",ans1,ans2);

}

else {

assert(k1 >= 1 && k1 <= (long long)n(n+1)/2 && k2 >= 1 && k2 <= (long long)n(n+1)/2);

int id1 = lower_bound(num1+1,num1+Max+1,k1) - num1;

if(id1 > Max || num1[id1] != k1){

printf("-1\n");

continue;

}

int sz = vec2[id1].size();

if(k2 > vec2[id1][sz-1].sum){

printf("-1\n");

continue;

}

int l = 0, r = sz-1;

int id2 = 0;

while(l <= r){

int mid = (l+r)/2;

long long ss = vec2[id1][mid].sum - (vec2[id1][mid].r2 - vec2[id1][mid].r1 + 1);

if(k2 > ss){

id2 = mid;

l = mid+1;

}

else r = mid-1;

}

k2 -= vec2[id1][id2].sum - (vec2[id1][id2].r2 - vec2[id1][id2].r1 + 1);

printf("%d %d\n",vec2[id1][id2].l,(int)(vec2[id1][id2].r1 + k2 - 1));

}

}

}

return 0;

}
1002题: [HDU5043](http://acm.hdu.edu.cn/showproblem.php?pid=5043) 这个题就是Lucas定理的简单应用啊~~ 数位DP可搞。 这题是5倍以后标程啊,我没卡常数~ 小问题答案其实是 C(M,k1) * C(M-k1,k2) * C(M-k1-k2,k3)*********** M = k1+k2+k3+.. 如果要模P不等于0,就是k1,k2,...kn的P进制的和不能有进位。 然后就是数位DP可搞。
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
/* ***************

Author :kuangbin

Created Time :2014/9/25 0:07:36

File Name :1002.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MOD = 1e8+9;

void Add(int &a,int b){

a += b;

if(a >= MOD)a -= MOD;

}

int vis[10][33][22][1<<10];

int dp[10][33][22][1<<10];

int TT;

int prime;

int n;

int bit[10][33];

int dfs(int id,int pos,int sum,int s){

if(id == n){

id = 0;

pos--;

sum = 0;

if(pos == -1)return 1;

}

if(vis[id][pos][sum][s] == TT)return dp[id][pos][sum][s];

int end = (s&(1<<id))?bit[id][pos]:prime-1;

int ans = 0;

for(int i = 0;i <= end;i++){

if(sum + i >= prime)break;

Add(ans,dfs(id+1,pos,sum+i,i == end? s : (s & (~(1<<id)))));

}

vis[id][pos][sum][s] = TT;

return dp[id][pos][sum][s] = ans;

}

int x[10];

int solve(){

memset(bit,0,sizeof(bit));

int Max = 0;

for(int i = 0;i < n;i++){

int cnt = 0;

do{

bit[i][cnt++] = x[i]%prime;

x[i] /= prime;

}

while(x[i]);

Max = max(Max,cnt);

}

return dfs(0,Max-1,0,(1<<n)-1);

}

int main()

{

//freopen("in.txt","r",stdin);

//freopen("out.txt","w",stdout);

TT = 0;

memset(vis,0,sizeof(vis));

int T;

scanf("%d",&T);

assert(T <= 50 && T >= 1);

int iCase = 0;

while(T--){

iCase++;

TT++;

scanf("%d%d",&n,&prime);

assert(n >= 1 && n <= 10);

assert(prime == 2

|| prime == 3

|| prime == 5

|| prime == 7

|| prime == 11

|| prime == 13

|| prime == 17

|| prime == 19);

long long tot = 1;

for(int i = 0;i < n;i++){

scanf("%d",&x[i]);

assert(x[i] >= 1 && x[i] <= 1000000000);

tot = tot*(1+x[i])%MOD;

}

tot -= solve();

tot = (tot%MOD+MOD)%MOD;

printf("Case #%d: %d\n",iCase,(int)tot);

}

return 0;

}
1003: 很简单的题目, 因为我卡常数了,让大家的罚时大增~~ 原意是想卡掉LCT或者其他的什么nlogn, n longnlogn算法的,后来发现O(n+m)的比不上nlogn的算法。因为常数好大。 然后就变成了谁的姿势好,谁就可过。 至于出现有很多的PE,是我故意安排的。 我要求输出3行的,你们的程序n=1的时候输出2行,能不PE吗?   一种做法是Tarjan进行LCA,然后进行加减啊,然后扫一遍。 或者进行树链剖分转为线性,然后搞。 其余算法也可能可以卡过~ 但是本题要输入输出挂,标程也无耻地用了~~尽力吐槽吧
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
/* ***************

Author :kuangbin

Created Time :2014/9/9 15:33:50

File Name :C.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MAXN = 100010;

struct Edge{

int to,next;

int index;

}edge[MAXN*2];

int head[MAXN],tot;

void init(){

tot = 0;

memset(head,-1,sizeof(head));

}

inline void addedge(int u,int v,int index){

edge[tot].to = v;

edge[tot].next = head[u];

edge[tot].index = index;

head[u] = tot++;

}

int F[MAXN];

inline int find(int x){

if(F[x] == -1)return x;

return F[x] = find(F[x]);

}

inline void bing(int x,int y){

int t1 = find(x);

int t2 = find(y);

if(t1 != t2)F[t1] = t2;

}

long long PF[MAXN],EF[MAXN];

struct Node{

int id;

int v,val;

int next;

Node(int _id = 0,int _v = 0,int _val = 0){

id = _id;

v = _v;

val = _val;

}

}query[MAXN*2];

int h[MAXN];

int tt;

inline void init2(){

tt = 0;

memset(h,-1,sizeof(h));

}

inline void add_query(int u,int v,int id,int val){

query[tt].id = id;

query[tt].next = h[u];

query[tt].v = v;

query[tt].val = val;

h[u] = tt++;

}

bool vis[MAXN];

int fa[MAXN];

bool ff[MAXN];

int sta[MAXN];

int cur[MAXN];

void dfs1(int u,int pre){

memcpy(cur,head,sizeof(head));

memset(ff,false,sizeof(ff));

fa[1] = -1;

int top = 0;

sta[top++] = 1;

while(top != 0){

u = sta[top-1];

if(!ff[u])ff[u] = true;

bool flag = false;

for(int i = cur[u];i != -1;i = edge[i].next){

int v = edge[i].to;

if(ff[v])continue;

fa[v] = u;

sta[top++] = v;

flag = true;

cur[u] = edge[i].next;

break;

}

if(!flag){

top--;

for(int i = h[u];i != -1;i = query[i].next){

int v = query[i].v;

int type = query[i].id;

int w = query[i].val;

if(vis[v]){

if(type == 1){

PF[find(v)] -= w;

if(fa[find(v)] != -1)PF[fa[find(v)]] -= w;

PF[v] += w;

}

else {

EF[find(v)] -= 2*w;

EF[v] += w;

}

}

else {

if(type == 1)PF[v] += w;

else EF[v] += w;

}

}

if(fa[u] != -1)bing(u,fa[u]);

vis[u] = true;

}

}

}

long long a[MAXN];

long long ans1[MAXN],ans2[MAXN];

int gg[MAXN];

void dfs2(int u,int pre){

int l,r;

gg[l = r = 1] = 1;

for(;l <= r;l++)

for(int i = head[gg[l]];i != -1;i = edge[i].next){

int v = edge[i].to;

if(v == fa[gg[l]])continue;

gg[++r] = v;

}

for(l--;l;l--){

u = gg[l];

for(int i = head[u];i != -1;i = edge[i].next){

int v = edge[i].to;

if(v == fa[u])continue;

EF[u] += EF[v];

PF[u] += PF[v];

ans2[edge[i].index] = EF[v];

}

ans1[u] = PF[u] + a[u];

}

}

//适用于正负整数

template <class T>

inline bool scan_d(T &ret) {

char c; int sgn;

if(c=getchar(),c==EOF) return 0; //EOF

while(c!='-'&&(c<'0'||c>'9')) c=getchar();

sgn=(c=='-')?-1:1;

ret=(c=='-')?0:(c-'0');

while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

ret*=sgn;

return 1;

}

inline void out(long long x) {

if(x>9) out(x/10);

putchar(x%10+'0');

}

int main()

{

//freopen("C.in","r",stdin);

//freopen("C.out","w",stdout);

//freopen("in.txt","r",stdin);

//freopen("out1.txt","w",stdout);

int n,m;

int T;

scanf("%d",&T);

int iCase = 0;

while(T--){

iCase++;

init();

//scanf("%d%d",&n,&m);

scan_d(n);

scan_d(m);

assert(n >= 1 && n <= 100000 && m >= 1 && m <= 100000);

memset(a,0,sizeof(a));

int u,v,w;

for(int i = 1;i < n;i++){

//scanf("%d%d",&u,&v);

scan_d(u);

scan_d(v);

addedge(u,v,i);

addedge(v,u,i);

}

char op[20];

init2();

while(m--){

//scanf("%s%d%d%d",op,&u,&v,&w);

scanf("%s",op);

scan_d(u);

scan_d(v);

scan_d(w);

assert(u >= 1 && u <= n);

assert(v >= 1 && v <= n);

assert(abs(w) <= 100000);

if(op[3] == '1'){

if(u == v)a[u] += w;

else {

// vec[u].push_back(Node(1,v,w));

//vec[v].push_back(Node(1,u,w));

add_query(u,v,1,w);

add_query(v,u,1,w);

}

}

else {

if(u == v)continue;

else {

//vec[u].push_back(Node(2,v,w));

//vec[v].push_back(Node(2,u,w));

add_query(u,v,2,w);

add_query(v,u,2,w);

}

}

}

memset(PF,0,sizeof(PF));

memset(EF,0,sizeof(EF));

memset(F,-1,sizeof(F));

memset(vis,false,sizeof(vis));

dfs1(1,-1);

//for(int i = 1;i <= n;i++)

//printf("%I64d %I64d\n",PF[i],EF[i]);

//memset(ans1,0,sizeof(ans1));

//memset(ans2,0,sizeof(ans2));

dfs2(1,-1);

printf("Case #%d:\n",iCase);

for(int i = 1;i <= n;i++){

//printf("%I64d",ans1[i]);

out(ans1[i]);

if(i < n)printf(" ");

else printf("\n");

}

for(int i = 1;i < n;i++){

//printf("%I64d",ans2[i]);

out(ans2[i]);

if(i < n-1)printf(" ");

}

printf("\n");

}

return 0;

}

树链剖分:

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
/* ***************

Author :kuangbin

Created Time :2014/9/24 14:12:20

File Name :F:\题目_上海网络赛\2014上海网络赛题目\C\标程\C3.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 100010;

struct Edge{

int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

int top[MAXN];

int fa[MAXN];

int deep[MAXN];

int num[MAXN];

int p[MAXN];

int fp[MAXN];

int son[MAXN];

int pos;

void init(){

tot = 0;

memset(head,-1,sizeof(head));

pos = 1;

memset(son,-1,sizeof(son));

}

inline void addedge(int u,int v){

edge[tot].to = v;

edge[tot].next = head[u];

head[u] = tot++;

}

inline void dfs1(int u,int pre,int d){

deep[u] = d;

fa[u] = pre;

num[u] = 1;

for(int i = head[u];i != -1;i = edge[i].next){

int v = edge[i].to;

if(v != pre){

dfs1(v,u,d+1);

num[u] += num[v];

if(son[u] == -1 || num[v] > num[son[u]])

son[u] = v;

}

}

}

inline void getpos(int u,int sp){

top[u] = sp;

p[u] = pos++;

fp[p[u]] = u;

if(son[u] == -1)return;

getpos(son[u],sp);

for(int i = head[u];i != -1;i = edge[i].next){

int v = edge[i].to;

if(v != son[u] && v != fa[u])

getpos(v,v);

}

}

long long w1[MAXN];

void add1(int u,int v,int w){

int f1 = top[u],f2 = top[v];

while(f1 != f2){

if(deep[f1] < deep[f2]){

swap(f1,f2);

swap(u,v);

}

w1[p[f1]] += w;

w1[p[u]+1] -= w;

u = fa[f1];

f1 = top[u];

}

if(deep[u] > deep[v])swap(u,v);

w1[p[u]] += w;

w1[p[v]+1] -= w;

}

long long w2[MAXN];

void add2(int u,int v,int w){

int f1 = top[u], f2 = top[v];

while(f1 != f2){

if(deep[f1] < deep[f2]){

swap(f1,f2);

swap(u,v);

}

w2[p[f1]] += w;

w2[p[u]+1] -= w;

u = fa[f1];

f1 = top[u];

}

if(u == v)return;

if(deep[u] > deep[v])swap(u,v);

w2[p[son[u]]] += w;

w2[p[v]+1] -= w;

}

//适用于正负整数

template <class T>

inline bool scan_d(T &ret) {

char c; int sgn;

if(c=getchar(),c==EOF) return 0; //EOF

while(c!='-'&&(c<'0'||c>'9')) c=getchar();

sgn=(c=='-')?-1:1;

ret=(c=='-')?0:(c-'0');

while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

ret*=sgn;

return 1;

}

inline void out(long long x) {

if(x>9) out(x/10);

putchar(x%10+'0');

}

pair<int,int>pp[MAXN];

int link[MAXN];

long long ans1[MAXN],ans2[MAXN];

int main()

{

int __size__ = 256 << 20;

char * __p__ = (char *) malloc(__size__) + __size__;

__asm__("movl %0,%%esp\n"::"r"(__p__));

//freopen("in.txt","r",stdin);

//freopen("out2.txt","w",stdout);

int n,m;

int T;

int iCase = 0;

scanf("%d",&T);

while(T--){

iCase++;

init();

scan_d(n);

scan_d(m);

memset(w1,0,sizeof(w1));

memset(w2,0,sizeof(w2));

int u,v,w;

for(int i = 1;i < n;i++){

scan_d(u);

scan_d(v);

addedge(u,v);

addedge(v,u);

pp[i] = make_pair(u,v);

}

dfs1(1,0,0);

getpos(1,1);

for(int i = 1;i < n;i++){

if(deep[pp[i].first] > deep[pp[i].second])

swap(pp[i].first,pp[i].second);

link[pp[i].second] = i;

}

char op[10];

while(m--){

scanf("%s",op);

scan_d(u);

scan_d(v);

scan_d(w);

if(op[3] == '1'){

add1(u,v,w);

}

else add2(u,v,w);

}

for(int i = 1;i <= n;i++){

w1[i] += w1[i-1];

w2[i] += w2[i-1];

ans1[fp[i]] = w1[i];

ans2[link[fp[i]]] = w2[i];

}

printf("Case #%d:\n",iCase);

for(int i = 1;i <= n;i++){

//printf("%I64d",ans1[i]);

out(ans1[i]);

if(i < n)printf(" ");

else printf("\n");

}

for(int i = 1;i < n;i++){

//printf("%I64d",ans2[i]);

out(ans2[i]);

if(i < n-1)printf(" ");

}

printf("\n");

}

return 0;

}

1004 HDU5045 直接状压DP。 可能题意好多人没理解,但是该表述的都表述清楚了,英语太渣了。

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
/* ***************

Author :kuangbin

Created Time :2014/9/10 20:04:53

File Name :D.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

double dp[1010][1<<10];

bool vis[1010][1<<10];

double p[10][1010];

int n,m;

double solve(int id,int s){

if(s == (1<<n)-1)s = 0;

if(vis[id][s])return dp[id][s];

vis[id][s] = true;

dp[id][s] = 0;

if(id == m)return dp[id][s];

for(int i = 0;i < n;i++){

if(s&(1<<i))continue;

dp[id][s] = max(dp[id][s],(1-p[i][id])*solve(id+1,s|(1<<i))+p[i][id]*(solve(id+1,s|(1<<i))+1));

}

return dp[id][s];

}

int main()

{

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

int T;

int iCase = 0;

scanf("%d",&T);

while(T--){

iCase++;

scanf("%d%d",&n,&m);

for(int i = 0;i < n;i++)

for(int j = 0;j < m;j++)

scanf("%lf",&p[i][j]);

memset(vis,false,sizeof(vis));

printf("Case #%d: %.5lf\n",iCase,solve(0,0));

}

return 0;

}

1005: HDU5046 直接DLX模板题!!! 有点裸! 而且貌似好多人被卡了!!!模板不够优啊! 这题3倍标程了,感觉也够了。

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int maxnode = 4000;

const int MaxM = 70;

const int MaxN = 70;

int K;

struct DLX

{

int n,m,size;

int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];

int H[MaxN],S[MaxM];

int ands,ans[MaxN];

void init(int _n,int _m)

{

n = _n;

m = _m;

for(int i = 0;i <= m;i++)

{

S[i] = 0;

U[i] = D[i] = i;

L[i] = i-1;

R[i] = i+1;

}

R[m] = 0; L[0] = m;

size = m;

for(int i = 1;i <= n;i++)

H[i] = -1;

}

void Link(int r,int c)

{

++S[Col[++size]=c];

Row[size] = r;

D[size] = D[c];

U[D[c]] = size;

U[size] = c;

D[c] = size;

if(H[r] < 0)H[r] = L[size] = R[size] = size;

else

{

R[size] = R[H[r]];

L[R[H[r]]] = size;

L[size] = H[r];

R[H[r]] = size;

}

}

void remove(int c)

{

for(int i = D[c];i != c;i = D[i])

L[R[i]] = L[i], R[L[i]] = R[i];

}

void resume(int c)

{

for(int i = U[c];i != c;i = U[i])

L[R[i]]=R[L[i]]=i;

}

bool v[maxnode];

int f()

{

int ret = 0;

for(int c = R[0];c != 0;c = R[c])v[c] = true;

for(int c = R[0];c != 0;c = R[c])

if(v[c])

{

ret++;

v[c] = false;

for(int i = D[c];i != c;i = D[i])

for(int j = R[i];j != i;j = R[j])

v[Col[j]] = false;

}

return ret;

}
bool Dance(int d)
{
if(d + f() > K)return false;
if(R\[0\] == 0)return d <= K;
int c = R\[0\];
for(int i = R\[0\];i != 0;i = R\[i\])
if(S\[i\] < S\[c\])
c = i;
for(int i = D\[c\];i != c;i = D\[i\])
{
remove(i);
for(int j = R\[i\];j != i;j = R\[j\])remove(j);
if(Dance(d+1))return true;
for(int j = L\[i\];j != i;j = L\[j\])resume(j);
resume(i);
}
return false;
}

};

DLX g;

struct Point

{

int x,y;

void input()

{

scanf("%d%d",&x,&y);

}

}city[MaxM];

long long dis(Point a,Point b)

{

return (long long)abs(a.x-b.x)+(long long)abs(a.y-b.y);

}

int main()

{

//freopen("E.in","r",stdin);

//freopen("E.out","w",stdout);

int T;

int n;

scanf("%d",&T);

int iCase = 0;

while(T--)

{

iCase++;

scanf("%d%d",&n,&K);

assert(n >= 1 && n <= 60 && K >= 1 && K <= n);

for(int i = 0;i < n;i++){

city[i].input();

assert(abs(city[i].x) <= 1000000000);

assert(abs(city[i].y) <= 1000000000);

}

long long l = 0, r = 100000000000LL;

long long ans = 0;

while(l <= r)

{

long long mid = (l+r)/2;

g.init(n,n);

for(int i = 0;i < n;i++)

for(int j = 0;j < n;j++)

if(dis(city[i],city[j]) <= mid)

g.Link(i+1,j+1);

if(g.Dance(0)){r = mid-1;ans = mid;}

else l = mid+1;

}

printf("Case #%d: %I64d\n",iCase,ans);

}

return 0;

}
1006: [HDU5047](http://acm.hdu.edu.cn/showproblem.php?pid=5047) 直接根据多少个交点,多少个边,然后就是推公式。 很简单,故意组数比较多,可能少数JAVA.         sorry.  
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
/* ***************

Author :kuangbin

Created Time :2014/9/11 13:19:51

File Name :F.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

/*

* 高精度,支持乘法和加法

*/

struct BigInt

{

const static int mod = 10000;

const static int DLEN = 4;

int a[600],len;

BigInt()

{

memset(a,0,sizeof(a));

len = 1;

}

BigInt(long long v)

{

memset(a,0,sizeof(a));

len = 0;

do

{

a[len++] = v%mod;

v /= mod;

}while(v);

}

BigInt(const char s[])

{

memset(a,0,sizeof(a));

int L = strlen(s);

len = L/DLEN;

if(L%DLEN)len++;

int index = 0;

for(int i = L-1;i >= 0;i -= DLEN)

{

int t = 0;

int k = i - DLEN + 1;

if(k < 0)k = 0;

for(int j = k;j <= i;j++)

t = t*10 + s[j] - '0';

a[index++] = t;

}

}

BigInt operator +(const BigInt &b)const

{

BigInt res;

res.len = max(len,b.len);

for(int i = 0;i <= res.len;i++)

res.a[i] = 0;

for(int i = 0;i < res.len;i++)

{

res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);

res.a[i+1] += res.a[i]/mod;

res.a[i] %= mod;

}

if(res.a[res.len] > 0)res.len++;

return res;

}

BigInt operator *(const BigInt &b)const

{

BigInt res;

for(int i = 0; i < len;i++)

{

int up = 0;

for(int j = 0;j < b.len;j++)

{

int temp = a[i]*b.a[j] + res.a[i+j] + up;

res.a[i+j] = temp%mod;

up = temp/mod;

}

if(up != 0)

res.a[i + b.len] = up;

}

res.len = len + b.len;

while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;

return res;

}

void output()

{

printf("%d",a[len-1]);

for(int i = len-2;i >=0 ;i--)

printf("%04d",a[i]);

printf("\n");

}

};

BigInt A,B;

int main()

{

//freopen("F.in","r",stdin);

//freopen("F.out","w",stdout);

int iCase = 0;

int T;

scanf("%d",&T);

assert(T >= 1 && T <= 100000);

assert(T == 100000);

long long n;

while(T--){

iCase++;

scanf("%I64d",&n);

assert(n >= 0 && n <= 1000000000000LL);

if(n == 0){

printf("Case #%d: 1\n",iCase);

continue;

}

A = (BigInt(n)*BigInt(8*n-7))+1;

printf("Case #%d: ",iCase);

A.output();

}

return 0;

}
1007: [HDU5048](http://acm.hdu.edu.cn/showproblem.php?pid=5048) 比较水的几何了。 只要解方程去求线段和椭球的交点。
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
/* ***************

Author :kuangbin

Created Time :2014/9/15 17:56:58

File Name :E:\2014ACM\题目_上海网络赛\color\标程\G.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const double eps = 1e-8;

inline double sqr(double x){return x*x;}

struct Point{

double x,y,z;

void input(){

scanf("%lf%lf%lf",&x,&y,&z);

assert(fabs(x) <= 10000);

assert(fabs(y) <= 10000);

assert(fabs(z) <= 10000);

}

};

struct Line{

Point s,e;

void input(){

s.input();

e.input();

}

double len(){

return sqrt((s.x-e.x)(s.x-e.x)+(s.y-e.y)(s.y-e.y)+(s.z-e.z)*(s.z-e.z));

}

};

struct Ellipsoid{

double x,y,z,a,b,c;

char color[5];

void input(){

scanf("%lf%lf%lf%lf%lf%lf%s",&x,&y,&z,&a,&b,&c,color);

assert(fabs(x) <= 10000);

assert(fabs(y) <= 10000);

assert(fabs(z) <= 10000);

assert(a >= 1 && a <= 10000);

assert(b >= 1 && b <= 10000);

assert(c >= 1 && c <= 10000);

assert(color[0] == 'R' || color[0] == 'G' || color[0] == 'B');

}

void output(){

printf("%lf %lf %lf %lf %lf %lf %s\n",x,y,z,a,b,c,color);

}

};

double calc(vector<Line>line,vector<Ellipsoid>el){

//for(int i = 0; i < el.size();i++)

//el[i].output();

double ans = 0;

int sz1 = line.size();

for(int i = 0;i < sz1;i++){

vector<pair<double,int> >vec;

vec.push_back(make_pair(0.0,0));

vec.push_back(make_pair(1.0,0));

double len = line[i].len();

if(fabs(len) < eps)continue;

double x1 = line[i].s.x;

double y1 = line[i].s.y;

double z1 = line[i].s.z;

double dx = line[i].e.x - line[i].s.x;

double dy = line[i].e.y - line[i].s.y;

double dz = line[i].e.z - line[i].s.z;

//printf("%lf %lf %lf %lf %lf %lf\n",line[i].s.x,line[i].s.y,line[i].s.z,line[i].e.x,line[i].e.y,line[i].e.z);

int sz = el.size();

for(int j = 0;j < sz;j++){

double a = sqr(dx)/sqr(el[j].a) + sqr(dy)/sqr(el[j].b) + sqr(dz)/sqr(el[j].c);

double b = 2*dx*(x1-el[j].x)/sqr(el[j].a) +

2*dy*(y1-el[j].y)/sqr(el[j].b) + 2*dz*(z1-el[j].z)/sqr(el[j].c);

double c = sqr(x1-el[j].x)/sqr(el[j].a) + sqr(y1-el[j].y)/sqr(el[j].b)

\+ sqr(z1-el[j].z)/sqr(el[j].c) - 1;

double delta = b*b - 4*a*c;

//cout<<delta<<endl;

if(delta < eps)continue;

double k1 = (-b+sqrt(delta))/(2*a);

double k2 = (-b-sqrt(delta))/(2*a);

//printf("a %.10lf b %.10lf c %.10lf \n",a,b,c);

//printf("%.10lf %.10lf\n",k1,k2);

if(k1 > k2)swap(k1,k2);

k1 = max(0.0,k1);

k2 = min(1.0,k2);

//printf("%.10lf %.10lf\n",k1,k2);

if(k1 >= k2)continue;

vec.push_back(make_pair(k1,1));

vec.push_back(make_pair(k2,-1));

}

int cnt = 0;

sort(vec.begin(),vec.end());

int sz2 = vec.size();

double pre = 0;

for(int j = 0;j < sz2;j++){

if(cnt > 0)

ans += (vec[j].first - pre)*len;

pre = vec[j].first;

cnt += vec[j].second;

}

}

return ans;

}

Line line[110];

Ellipsoid el[110];

vector<Line>vec1;

vector<Ellipsoid>vec2;

int main()

{

//freopen("G.in","r",stdin);

//freopen("G.out","w",stdout);

int T;

scanf("%d",&T);

assert(T >= 1 && T <= 100);

int iCase = 0;

int n,m;

while(T--){

iCase++;

scanf("%d%d",&n,&m);

for(int i = 0;i < n;i++)line[i].input();

for(int i = 0;i < m;i++){

el[i].input();

// printf("i %d %c\n",i,el[i].color[0]);

}

vec1.clear();

for(int i = 0;i < n;i++)vec1.push_back(line[i]);

double tot = 0;

for(int i = 0;i < n;i++)tot += line[i].len();

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'R')

vec2.push_back(el[i]);

double R = calc(vec1,vec2);

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'G')

vec2.push_back(el[i]);

double G = calc(vec1,vec2);

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'B')

vec2.push_back(el[i]);

double B = calc(vec1,vec2);

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'R' || el[i].color[0] == 'G')

vec2.push_back(el[i]);

double RG = calc(vec1,vec2);

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'R' || el[i].color[0] == 'B')

vec2.push_back(el[i]);

double RB = calc(vec1,vec2);

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'G' || el[i].color[0] == 'B')

vec2.push_back(el[i]);

double GB = calc(vec1,vec2);

vec2.clear();

for(int i = 0;i < m;i++)

if(el[i].color[0] == 'R' || el[i].color[0] == 'G' || el[i].color[0] == 'B')

vec2.push_back(el[i]);

double RGB = calc(vec1,vec2);

//printf("tot %.6lf R %lf G %lf B %lf RG %lf RB %lf GB %lf RGB %lf\n",tot,R,G,B,RG,RB,GB,RGB);

double ans1 = RGB - GB;

double ans2 = RGB - RB;

double ans3 = RGB - RG;

double ans4 = RGB - B - ans1 - ans2;

double ans5 = RGB - G - ans1 - ans3;

double ans6 = RGB - R - ans2 - ans3;

double ans7 = R + G - RG - ans4;

double aa = tot-RGB;

if(fabs(aa) < eps)aa = 0;

if(fabs(ans1) < eps)ans1 = 0;

if(fabs(ans2) < eps)ans2 = 0;

if(fabs(ans3) < eps)ans3 = 0;

if(fabs(ans4) < eps)ans4 = 0;

if(fabs(ans5) < eps)ans5 = 0;

if(fabs(ans6) < eps)ans6 = 0;

if(fabs(ans7) < eps)ans7 = 0;

//printf("Case #%d:\n",iCase);

printf("%.10lf\n",aa);

printf("%.10lf\n",ans1);

printf("%.10lf\n",ans2);

printf("%.10lf\n",ans3);

printf("%.10lf\n",ans4);

printf("%.10lf\n",ans5);

printf("%.10lf\n",ans6);

printf("%.10lf\n",ans7);

}

return 0;

}
1008: [HDU5049](http://acm.hdu.edu.cn/showproblem.php?pid=5049) 就是一个简单的DP。 使用矩阵去优化。  故意把范围设的不大的,太大一想就是矩阵了。 注意特判一些情况。 还有答案为0,可能不是 Impossible. 故意造的数据。
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
/* ***************

Author :kuangbin

Created Time :2014/9/16 22:41:06

File Name :E:\2014ACM\题目_上海网络赛\Guess\标程\H.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MOD = 20140927;

struct Matrix{

int mat[2][2];

void init(){

memset(mat,0,sizeof(mat));

}

Matrix operator *(const Matrix &b)const{

Matrix ret;

for(int i = 0;i < 2;i++)

for(int j = 0;j < 2;j++){

ret.mat[i][j] = 0;

for(int k = 0;k < 2;k++){

ret.mat[i][j] += (long long)mat[i][k]*b.mat[k][j]%MOD;

if(ret.mat[i][j] >= MOD)

ret.mat[i][j] -= MOD;

}

}

return ret;

}

void output(){

printf("%d %d\n%d %d\n",mat[0][0],mat[0][1],mat[1][0],mat[1][1]);

}

};

Matrix pow_M(Matrix A,int n){

Matrix ret;

ret.mat[0][0] = ret.mat[1][1] = 1;

ret.mat[0][1] = ret.mat[1][0] = 0;

Matrix tmp = A;

while(n){

if(n&1)ret = ret*tmp;

tmp = tmp*tmp;

n >>= 1;

}

return ret;

}

Matrix A[11*11*11 + 100];

vector<int>vec;

Matrix B;

Matrix C;

struct Matrix2{

int mat[2][2];

void init(){

memset(mat,0,sizeof(mat));

}

Matrix2 operator *(const Matrix2 &b)const{

Matrix2 ret;

for(int i = 0;i < 2;i++)

for(int j = 0;j < 2;j++){

ret.mat[i][j] = 0;

for(int k = 0;k < 2;k++)

if(mat[i][k] && b.mat[k][j])

ret.mat[i][j] = 1;

}

return ret;

}

};

Matrix2 pow_M(Matrix2 A,int n){

Matrix2 ret;

ret.mat[0][0] = ret.mat[1][1] = 1;

ret.mat[0][1] = ret.mat[1][0] = 0;

Matrix2 tmp = A;

while(n){

if(n&1)ret = ret*tmp;

tmp = tmp*tmp;

n >>= 1;

}

return ret;

}

Matrix2 A2[11*11*11 + 100];

Matrix2 B2;

Matrix2 C2;

void Add(int &a,int b){

if(a || b)a = 1;

}

int main()

{

//freopen("H.in","r",stdin);

//freopen("H.out","w",stdout);

for(int i = 0;i < 11*11*11;i++)A[i].init();

for(int i = 0;i < 11*11*11;i++)A2[i].init();

for(int x = 0;x < 11;x++)

for(int y = 0;y < 11;y++)

for(int z = 0; z < 11;z++){

int id = x*11*11 + y*11 + z;

for(int i = 0;i < 10;i++){

if(x != 10 && x != i)continue;

for(int j = 0;j < 10;j++){

if(y != 10 && y != j)continue;

for(int k = 0;k < 10;k++){

if(z != 10 && z != k)continue;

if(i + j == k)A[id].mat[0][0]++;

if(i + j == 10 + k)A[id].mat[0][1]++;

if(i + j + 1 == k)A[id].mat[1][0]++;

if(i + j + 1 == 10 + k)A[id].mat[1][1]++;

if(i + j == k)Add(A2[id].mat[0][0],1);

if(i + j == 10 + k)Add(A2[id].mat[0][1],1);

if(i + j + 1 == k)Add(A2[id].mat[1][0],1);

if(i + j + 1 == 10 + k)Add(A2[id].mat[1][1],1);

}

}

}

}

int T;

int iCase = 0;

int n1,m1,n2,m2,n3,m3;

scanf("%d",&T);

while(T--){

iCase++;

scanf("%d%d",&n1,&m1);

assert(n1 >= 1 && n1 <= 10000000);

assert(m1 >= 0 && m1 <= n1);

map<int,int>mp1;

map<int,int>mp2;

map<int,int>mp3;

bool flag = true;

vec.clear();

int id,x;

while(m1--){

scanf("%d%d",&id,&x);

id = n1 - 1 - id;

vec.push_back(id);

if(mp1.find(id) != mp1.end()){

if(mp1[id] != x)flag = false;

}

else mp1[id] = x;

}

scanf("%d%d",&n2,&m2);

assert(n2 >= 1 && n2 <= 10000000);

assert(m2 >= 0 && m2 <= n2);

while(m2--){

scanf("%d%d",&id,&x);

id = n2 - 1 - id;

vec.push_back(id);

if(mp2.find(id) != mp2.end()){

if(mp2[id] != x)flag = false;

}

else mp2[id] = x;

}

scanf("%d%d",&n3,&m3);

assert(n3 >= 1 && n3 <= 10000000);

assert(m3 >= 0 && m3 <= n3);

while(m3--){

scanf("%d%d",&id,&x);

id = n3 - 1 - id;

vec.push_back(id);

if(mp3.find(id) != mp3.end()){

if(mp3[id] != x)flag = false;

}

else mp3[id] = x;

}

if((!flag) || (n1 < max(n2,n3)) || (n1 > max(n2,n3)+1)){

printf("Case #%d: IMPOSSIBLE\n",iCase);

continue;

}

//vec.push_back(n1-1);

vec.push_back(n2-1);

vec.push_back(n3-1);

sort(vec.begin(),vec.end());

vec.erase(unique(vec.begin(),vec.end()),vec.end());

int mn = max(n2,n3);

B.init();

B.mat[0][0] = B.mat[1][1] = 1;

B2.init();

B2.mat[0][0] = B2.mat[1][1] = 1;

if(vec[0] > 0)B = B * pow_M(A[10*11*11+10*11+10],vec[0]);

if(vec[0] > 0)B2 = B2 * pow_M(A2[10*11*11+10*11+10],vec[0]);

int sz = vec.size();

for(int i = 0;i < sz;i++){

//printf("%d\n",vec[i]);

//B.output();

if(i > 0){

B = B * pow_M(A[10*11*11+10*11+10],vec[i]-vec[i-1]-1);

}

int x,y,z;

if(mp2.find(vec[i]) == mp2.end())x = 10;

else x = mp2[vec[i]];

if(vec[i] >= n2)x = 0;

if(mp3.find(vec[i]) == mp3.end())y = 10;

else y = mp3[vec[i]];

if(vec[i] >= n3)y = 0;

if(mp1.find(vec[i]) == mp1.end())z = 10;

else z = mp1[vec[i]];

if(vec[i] >= n1)z = 0;

if(vec[i] != n2-1 && vec[i] != n3-1){

B = B * A[x*11*11+y*11+z];

B2 = B2 * A2[x*11*11+y*11+z];

}

else {

C.init();

C2.init();

for(int p = 0;p < 10;p++)

for(int q = 0;q < 10;q++)

for(int r = 0;r < 10;r++){

if(x != 10 && p != x)continue;

if(y != 10 && q != y)continue;

if(z != 10 && r != z)continue;

if(n2 != 1 && vec[i] == n2-1 && p == 0)continue;

if(n3 != 1 && vec[i] == n3-1 && q == 0)continue;

if(vec[i] >= n2 && p != 0)continue;

if(vec[i] >= n3 && q != 0)continue;

if(p+q == r)C.mat[0][0]++;

if(p+q == r+10)C.mat[0][1]++;

if(p+q+1 == r)C.mat[1][0]++;

if(p+q+1 == r + 10)C.mat[1][1]++;

if(p+q == r)Add(C2.mat\[0\]\[0\],1);
if(p+q == r+10)Add(C2.mat\[0\]\[1\],1);
if(p+q+1 == r)Add(C2.mat\[1\]\[0\],1);
if(p+q+1 == r + 10)Add(C2.mat\[1\]\[1\],1);
}
//C.output();
B = B*C;
B2 = B2*C2;
}
}
int ans = 0;
int ans2 = 0;
if(n1 == max(n2,n3)){
ans = B.mat\[0\]\[0\];
ans2 = B2.mat\[0\]\[0\];
}
else{
if(mp1.find(n1-1) != mp1.end() && mp1\[n1-1\] != 1){
printf("Case #%d: IMPOSSIBLE\\n",iCase);
continue;
}
ans = B.mat\[0\]\[1\];
ans2 = B2.mat\[0\]\[1\];
}
//printf("%d %d\\n",ans,ans2);
if(ans2 == 0)printf("Case #%d: IMPOSSIBLE\\n",iCase);
else printf("Case #%d: %d\\n",iCase,ans);
}
return 0;

}
1009: [HDU5050](http://acm.hdu.edu.cn/showproblem.php?pid=5050) 就是求两个大数的GCD。 JAVA可以随便搞! 本题定位就是签到题。当然C++也可以搞。
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
/* ***************

Author :kuangbin

Created Time :2014/9/18 16:43:54

File Name :F:\题目_上海网络赛\dividedland\标程\I.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

struct BigNum{

int a[10100];

int n;

void input(char str[]){

n = strlen(str);

for(int i = 0;i < n;i++)

a[i] = str[n-1-i]-'0';

}

bool operator <(const BigNum &b)const{

if(n < b.n)return true;

if(n > b.n)return false;

for(int i = n-1;i >= 0;i--){

if(a[i] < b.a[i])return true;

if(a[i] > b.a[i])return false;

}

return true;

}

BigNum operator -(const BigNum &b)const{

BigNum ret;

ret.n = n;

int mu = 0;

for(int i = 0;i < n;i++){

int tmp;

if(i < b.n)tmp = a[i] - b.a[i] - mu;

else tmp = a[i] - mu;

if(tmp >= 0){

mu = 0;

ret.a[i] = tmp;

}

else {

mu = 1;

ret.a[i] = tmp+2;

}

}

while(ret.n > 0 && ret.a[ret.n-1] == 0)ret.n--;

return ret;

}

BigNum div2(){

BigNum ret;

ret.n = n-1;

for(int i = 0;i < n-1;i++)

ret.a[i] = a[i+1];

return ret;

}

void output(){

for(int i = n-1;i >= 0;i--)

printf("%d",a[i]);

}

};

void gcd(BigNum a,BigNum b){

int c2 = 0;

while(a.n && b.n){

if(a.a[0]){

if(b.a[0]){

if(b < a)a = a-b;

else b = b-a;

}

else b = b.div2();

}

else {

if(b.a[0])a = a.div2();

else{

a = a.div2();

b = b.div2();

c2++;

}

}

}

if(a.n)a.output();

else b.output();

while(c2--){

printf("0");

}

printf("\n");

}

char str[10010];

BigNum a,b,c;

int main()

{

//freopen("I.in","r",stdin);

//freopen("I.out","w",stdout);

int T;

scanf("%d",&T);

int iCase = 0;

while(T--){

iCase++;

scanf("%s",str);

a.input(str);

scanf("%s",str);

b.input(str);

printf("Case #%d: ",iCase);

gcd(a,b);

}

return 0;

}
1010: [HDU5051](http://acm.hdu.edu.cn/showproblem.php?pid=5051) Benford's law http://baike.baidu.com/view/1405011.htm?from_id=11319476&type=syn&fromtitle=Benford%27s+law&fr=aladdin http://zh.wikipedia.org/wiki/%E6%9C%AC%E7%A6%8F%E7%89%B9%E5%AE%9A%E5%BE%8B 这个教练提供的题。 特判一些情况就可以AC了。
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
/* ***************

Author :kuangbin

Created Time :2014/9/18 20:01:40

File Name :F:\题目_上海网络赛\fraction\标程\J.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

int main()

{

//freopen("J.in","r",stdin);

//freopen("J.out","w",stdout);

int T;

int iCase = 0;

scanf("%d",&T);

int n,b,q;

while(T--){

iCase++;

scanf("%d%d%d",&n,&b,&q);

printf("Case #%d: ",iCase);

if(q == 1){

bool flag = false;

while(b){

if(n == b){

flag = true;

break;

}

b /= 10;

}

if(flag)printf("1.00000\n");

else printf("0.00000\n");

}

else if(q == 10 || q == 100 || q == 1000){

b *= 100000;

bool flag = false;

while(b){

if(n == b){

flag = true;

break;

}

b /= 10;

}

if(flag)printf("1.00000\n");

else printf("0.00000\n");

}

else {

double ans = (log(n+1)-log(n))/log(10);

printf("%.5lf\n",ans);

}

}

return 0;

}
1011: [HDU5052](http://acm.hdu.edu.cn/showproblem.php?pid=5052) shumj出的LCT题。 直接LCT搞就可以了。 LCT的姿势不够优美可能被卡。
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
/* ***************

Author :kuangbin

Created Time :2014/9/18 21:59:15

File Name :K.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MAXN = 50010;

const int INF = 0x3f3f3f3f;

struct Node *null;

struct Node{

Node *fa,*ch[2];

int val;

int Max,Min;

int mm;

int rmm;

int rev,add;

inline void clear(int _val){

fa = ch[0] = ch[1] = null;

val = Max = Min = _val;

mm = 0;

rmm = 0;

rev = 0;

add = 0;

}

inline void push_up(){

if(this == null)return;

mm = 0;

mm = max(mm,ch[0]->mm);

mm = max(mm,ch[1]->mm);

mm = max(mm,max(val,ch[1]->Max)-ch[0]->Min);

mm = max(mm,ch[1]->Max-min(ch[0]->Min,val));

rmm = 0;

rmm = max(rmm,ch[0]->rmm);

rmm = max(rmm,ch[1]->rmm);

rmm = max(rmm,max(val,ch[0]->Max)-ch[1]->Min);

rmm = max(rmm,ch[0]->Max-min(ch[1]->Min,val));

Max = max(val,max(ch[0]->Max,ch[1]->Max));

Min = min(val,min(ch[0]->Min,ch[1]->Min));

}

inline void setc(Node *p,int d){

ch[d] = p;

p->fa = this;

}

inline bool d(){

return fa->ch[1] == this;

}

inline bool isroot(){

return fa == null || fa->ch[0] != this && fa->ch[1] != this;

}

inline void flip(){

if(this == null)return;

swap(ch[0],ch[1]);

swap(mm,rmm);

rev ^= 1;

}

inline void update_add(int w){

if(this == null)return;

val += w;

Min += w;

Max += w;

add += w;

}

inline void push_down(){

if(this == null)return;

if(rev){

ch[0]->flip(); ch[1]->flip(); rev = 0;

}

if(add){

ch[0]->update_add(add);ch[1]->update_add(add);

add = 0;

}

}

inline void go(){

if(!isroot())fa->go();

push_down();

}

inline void rot(){

Node *f = fa, *ff = fa->fa;

int c = d(), cc = fa->d();

f->setc(ch[!c],c);

this->setc(f,!c);

if(ff->ch[cc] == f)ff->setc(this,cc);

else this->fa = ff;

f->push_up();

}

inline Node* splay(){

go();

while(!isroot()){

if(!fa->isroot())

d()==fa->d() ? fa->rot() : rot();

rot();

}

push_up();

return this;

}

inline Node* access(){

for(Node *p = this, *q = null; p != null; q = p, p = p->fa){

p->splay()->setc(q,1);

p->push_up();

}

return splay();

}

inline void make_root(){

access()->flip();

}

};

Node pool[MAXN],*tail;

Node *node[MAXN];

struct Edge{

int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

void init(){

tot = 0;

memset(head,-1,sizeof(head));

}

inline void addedge(int u,int v){

edge[tot].to = v;

edge[tot].next = head[u];

head[u] = tot++;

}

int g[MAXN];

int fa[MAXN];

void bfs(int s){

int l,r;

g[l=r=1] = s;

fa[s] = s;

while(l <= r){

int u = g[l++];

for(int i = head[u];i != -1;i = edge[i].next){

int v = edge[i].to;

if(v == fa[u])continue;

fa[v] = u;

node[v]->fa = node[u];

g[++r] = v;

}

}

}

int main()

{

//freopen("big1.in","r",stdin);

//freopen("out1.txt","w",stdout);

int T;

int n,m;

scanf("%d",&T);

assert(T > 0 && T <= 10);

while(T--){

scanf("%d",&n);

//assert(n > 0 && n <= 50000);

tail = pool;

null = tail++;

null->fa = null->ch[0] = null->ch[1] = null;

null->Max = -INF;

null->Min = INF;

null->mm = 0;

null->add = null->rev = 0;

int w;

for(int i = 1;i <= n;i++){

scanf("%d",&w);

//assert(w > 0 && w <= 10000);

node[i] = tail++;

node[i]->clear(w);

}

init();

int u,v;

for(int i = 1;i < n;i++){

scanf("%d%d",&u,&v);

addedge(u,v);

addedge(v,u);

}

bfs(1);

scanf("%d",&m);

while(m--){

scanf("%d%d%d",&u,&v,&w);

//assert(u >= 1 && u <= n && v >= 1 && v <= n);

//assert(w > 0 && w <= 10000);

node[u]->make_root();

node[v]->access();

printf("%d\n",node[v]->mm);

node[v]->update_add(w);

}

}

return 0;

}
1012: [HDU5053](http://acm.hdu.edu.cn/showproblem.php?pid=5053) 签到题!
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
/* ***************

Author :kuangbin

Created Time :2014/9/27 10:51:53

File Name :E:\2014ACM\题目_上海网络赛\cube\标程\L.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

int main()

{

//freopen("L.in","r",stdin);

//freopen("L.out","w",stdout);

int T;

int iCase = 0;

scanf("%d",&T);

long long a,b;

while(T--){

iCase++;

scanf("%I64d%I64d",&a,&b);

a--;

long long ans = (b(b+1)/2)(b(b+1)/2) - (a(a+1)/2)(a(a+1)/2);

printf("Case #%d: %I64d\n",iCase,ans);

}

return 0;

}
再次为两次Rejudge深表歉意!
------ 本文结束------
  • 本文作者: kuangbin
  • 本文链接: 411.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
0%