T1
入门题。
如果输入的这个 n 是奇数的话，那么肯定有一个 20 在拆分里面，就不成立了。
否则就把这个数转为二进制，碰到个 1 就输出。
或者说，从大到小枚举 2 的整数次幂，碰到一个可以用的就从原来的数里减掉，输出。
1 #include<stdio.h>
2 #define reg register
3 #define ri reg int
4 #define rep(i, j, k) for(i = j; i <= k; ++i)
5 #define nrep(i, j, k) for(i = j; i >= k; --i)
6 #define ll long long
7 FILE *fin, *fout;
8 int read() {
9 reg char c;
10 ri res, flag = 1;
11 while((c = fgetc(fin)) < '0' || c > '9') if(c == '-') flag = -1;
12 res = c - '0';
13 while((c = fgetc(fin)) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
14 return res * flag;
15 }
16 int t[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};
17 int n;
18 int main() {
19 ri i;
20 #ifndef CCF
21 fin = stdin;
22 fout = stdout;
23 #else
24 fin = fopen("power.in", "r");
25 fout = fopen("power.out", "w");
26 #endif
27 n = read();
28 if(n % 2) fputs("-1", fout);
29 else {
30 nrep(i, 30, 1) if(n) {
31 if(n >= t[i]) {
32 n -= t[i];
33 fprintf(fout, "%d ", t[i]);
34 }
35 }
36 }
37 return 0;
38 }
View Code
打了个 2 的次幂的表，实际上打不打无所谓。
期望得分100。
T2
到死都没想到用桶来装。
虽然他说成绩不超 600 。
我是进来一个数就插在当前的表里，然后搞出分数线。
然后我搞了个链来存（？，优化了一下常数，但没用。
O(n2) 想搞过 10W 还是很艰难的。
1 #include<stdio.h>
2 #define reg register
3 #define ri reg int
4 #define rep(i, j, k) for(i = j; i <= k; ++i)
5 #define nrep(i, j, k) for(i = j; i >= k; --i)
6 #define ll long long
7 #define A(i) a[i + 50000]
8 FILE *fin, *fout;
9 int read() {
10 reg char c;
11 ri res, flag = 1;
12 while((c = fgetc(fin)) < '0' || c > '9') if(c == '-') flag = -1;
13 res = c - '0';
14 while((c = fgetc(fin)) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
15 return res * flag;
16 }
17 int a[200010];
18 int main() {
19 ri i, j, n, w, head = 0, tail = 0, t, num;
20 #ifndef CCF
21 fin = stdin;
22 fout = stdout;
23 #else
24 fin = fopen("live.in", "r");
25 fout = fopen("live.out", "w");
26 #endif
27 n = read();
28 w = read();
29 rep(i, 1, n) {
30 t = read();
31 if(t < A((head + tail) / 2)) {
32 rep(j, head, tail) {
33 if(t > A(j)) A(j - 1) = A(j);
34 else { A(j - 1) = t; break; }
35 }
36 --head;
37 }
38 else {
39 nrep(j, tail, head) {
40 if(t < A(j)) A(j + 1) = A(j);
41 else { A(j + 1) = t; break; }
42 }
43 ++tail;
44 }
45 num = w * (tail - head) / 100;
46 if(!num) num = 1;
47 fprintf(fout, "%d ", A(tail - num + 1));
48 }
49 return 0;
50 }
View Code
期望得分85。
正解使用桶装数据，可以做到 O(600n) 的水平。
但有一说一，我没写正解的代码。
T3
一看就是大模拟。
不会。
20 分走人。
的确， Subtask 1 蛮好写的，写一面的判断语句就好了。
1 #include<stdio.h>
2 #include<string.h>
3 #define reg register
4 #define ri reg int
5 #define rep(i, j, k) for(i = j; i <= k; ++i)
6 #define nrep(i, j, k) for(i = j; i >= k; --i)
7 #define ll long long
8 FILE *fin, *fout;
9 int read() {
10 reg char c;
11 ri res, flag = 1;
12 while((c = fgetc(fin)) < '0' || c > '9') if(c == '-') flag = -1;
13 res = c - '0';
14 while((c = fgetc(fin)) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
15 return res * flag;
16 }
17 int main() {
18 char st[1000010];
19 ri len, i, n, q, x, flag = 1, f_1 = 0, f_2 = 0, f_3 = 0, f_4 = 0, ze = 0, on = 0;
20 int a;
21 #ifndef CCF
22 fin = stdin;
23 fout = stdout;
24 #else
25 fin = fopen("expr.in", "r");
26 fout = fopen("expr.out", "w");
27 #endif
28 fgets(st, 1000001, fin);
29 len = strlen(st);
30 rep(i, 0, len - 1) if(st[i] == '&') flag = 0;
31 n = read();
32 rep(i, 1, n) {
33 a = read();
34 if(f_1 && a == 0) f_2 = 1;
35 if(a == 0) f_1 = 1, ze = i;
36 if(f_3 && a == 1) f_4 = 1;
37 if(a == 1) f_3 = 1, on = i;
38 }
39 q = read();
40 if(!f_4 && f_3 && flag) {
41 rep(i, 1, q) {
42 x = read();
43 if(x == on) fputs("0\n", fout);
44 else fputs("1\n", fout);
45 }
46 }
47 else if(flag) {
48 rep(i, 1, q) fputs("1\n", fout);
49 }
50 else if(!flag && f_1 && !f_2) {
51 rep(i, 1, q) {
52 x = read();
53 if(x == ze) fputs("1\n", fout);
54 else fputs("0\n", fout);
55 }
56 }
57 else {
58 rep(i, 1, q) fputs("0\n", fout);
59 }
60 return 0;
61 }
View Code
其他的一概不会。
T4
入门DP。
考虑只能上，下，右而不能左，所以可以以列来划分状态。
每一个格子先从左边继承而来，然后往上走一遍，往下走一遍，就可以得到当前位置的最大值。
本来写了个滚动数组的，结果调着出问题了，所以又改用了二维数组。
1 #include<stdio.h>
2 #define reg register
3 #define ri reg int
4 #define rep(i, j, k) for(i = j; i <= k; ++i)
5 #define nrep(i, j, k) for(i = j; i >= k; --i)
6 #define ll long long
7 #define max(i, j) (i) > (j) ? (i) : (j)
8 FILE *fin, *fout;
9 int read() {
10 reg char c;
11 ri res, flag = 1;
12 while((c = fgetc(fin)) < '0' || c > '9') if(c == '-') flag = -1;
13 res = c - '0';
14 while((c = fgetc(fin)) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
15 return res * flag;
16 }
17 int n, m;
18 ll map[1010][1010], mc[1010][1010], f[1010][1010];
19 int main() {
20 ri i, j, k;
21 #ifndef CCF
22 fin = stdin;
23 fout = stdout;
24 #else
25 fin = fopen("number.in", "r");
26 fout = fopen("number.out", "w");
27 #endif
28 n = read(), m = read();
29 rep(i, 1, n) rep(j, 1, m) map[i][j] = read();
30 mc[1][1] = f[1][1] = map[1][1];
31 rep(i, 2, n) mc[i][1] = f[i][1] = f[i - 1][1] + map[i][1];
32 rep(i, 2, m) {
33 rep(j, 1, n) mc[j][i] = f[j][i] = f[j][i - 1] + map[j][i];
34 rep(k, 2, n) if(f[k][i] < f[k - 1][i] + map[k][i]) f[k][i] = f[k - 1][i] + map[k][i];
35 nrep(k, n - 1, 1) if(mc[k][i] < mc[k + 1][i] + map[k][i]) mc[k][i] = mc[k + 1][i] + map[k][i];
36 rep(k, 1, n) f[k][i] = max(f[k][i], mc[k][i]);
37 }
38 fprintf(fout, "%lld", f[n][m]);
39 return 0;
40 }
View Code
好像真的要开 long long。
期望得分100。
总结
这么烂的成绩。400都没到。可以退役了。
测出来 100 + 90 + 20 + 100 = 310。
T2数据真的水。