CSP-J2020
T1
入门题。
如果输入的这个 n 是奇数的话，那么肯定有一个 20 在拆分里面，就不成立了。
否则就把这个数转为二进制，碰到个 1 就输出。
或者说，从大到小枚举 2 的整数次幂，碰到一个可以用的就从原来的数里减掉，输出。
1 #include2 #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 }
打了个 2 的次幂的表，实际上打不打无所谓。
期望得分100。
T2
到死都没想到用桶来装。
虽然他说成绩不超 600 。
我是进来一个数就插在当前的表里，然后搞出分数线。
然后我搞了个链来存（？，优化了一下常数，但没用。
O(n2) 想搞过 10W 还是很艰难的。
1 #include2 #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 }
期望得分85。
正解使用桶装数据，可以做到 O(600n) 的水平。
但有一说一，我没写正解的代码。
T3
一看就是大模拟。
不会。
20 分走人。
的确， Subtask 1 蛮好写的，写一面的判断语句就好了。
1 #include2 #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 }
其他的一概不会。
T4
入门DP。
考虑只能上，下，右而不能左，所以可以以列来划分状态。
每一个格子先从左边继承而来，然后往上走一遍，往下走一遍，就可以得到当前位置的最大值。
本来写了个滚动数组的，结果调着出问题了，所以又改用了二维数组。
1 #include2 #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 }
好像真的要开 long long。
期望得分100。
总结
这么烂的成绩。400都没到。可以退役了。
测出来 100 + 90 + 20 + 100 = 310。
T2数据真的水。