CSP 2020 游记

Vocalise

2020-10-12 23:40:33

Personal

## -1 month 初赛 ### S 组 前一天晚上翻下真题,感觉也不知道复习些什么了,于是扔了。 早上也是。 考场要 20 min 才能到。找到考场坐下来,怎么感觉一堆人比我小啊,是不是没救了( 开题。 选择题没啥问题。视频大小一开始以为 32 位 32bit,没救了( CRT 的题,直接算出来 53,不知道怎么估计区间。 信息论??? 草昨晚才看到这题啊,当时就扔了没翻答案,当时蒙对了,现在蒙错了,没救了( 选择 -2。 阅读 1 没错。 阅读 2 是个经典求 k 小,但是为什么都是算复杂度的??? T3 错题,一半猜的 $\log$。 T4 没啥问题第一层就是 $\mathcal O(n)$ 了。 T5 前一个显然是 $\mathcal O(n)$,后一个排除掉 $\log n$ 就行了。 T6 显然。 阅读 3,挺自闭的,不过坚持看完了,大概是个双向 BFS,搜什么过一会才看出来是 $[0,m]$ 和 $[m,len)$ 的循环置换。 T3 以为比 $n!$ 还低,就是以为是 $[0,m - 1]$ 和 $[m,len)$ 然后只有多项式种状态。 不过好歹对了( T5 T6 当场爬了,想了一会,尝试找 T5 的最优方案。然后没找出来。 只有 30 min 了,非常自闭。 于是先去完善程序。 第一篇没问题,就是猜也能大概对了。T5 空脑残,错掉了。 -3。 第二篇前两空和 DP 没关系。但是没时间去细想转移方式了,T3 空填错,T4 空半猜对,T5 空填错。 -6。 回去看两个 4 分题。 打算猜一个 T5,然后觉得可以猜二次关系。 然后好像真有,但是想当然觉得可以 $f(0) = 0$,就算不出来,没救了( 非常自闭。 猜了个错的。 T6 没时间了,蒙对了( -4。 预计 85。 ### 中午 出来的时候觉得要完蛋了。 但是对了下粉兔答案,发现蒙对挺多( 下午的也就放心了( ### J 组 挂得非常惨。 考场一群小学生,感觉非常不自在。 我市 380 人左右(J 组)。S 组的名单上午没看,下午就撕了,不知道。 开题,单选前面非常简单,又是 15 题,看到了**恰好**但没算进去,150 完美踩坑。 -2。 阅读 1 是个字符映射,没问题。 阅读 2 是对于 k 进制,问一个一个加进位多少。k = 1 特殊情况。 不记得 T2 T3 填的是什么。。。大概脑残都填的是正确。 -1.5。 T4 仍然脑残,踩坑了。 -2。 阅读 3 是喜闻乐见的合并求价值。 T1 又又又脑残了。 -1.5。 T4 T5 T6 就都是计算吗。。算出个 T4,后面暂时不会,去完善了。 完善 1 是个板子。 完善 2 贪心,也挺经典。 T1 反了,没救了。 T5 加了个 1,没救了。 -6。 回去看阅读后几题。主要是 1 序列(取绝对值的)不知怎样分析的。 草原来是 $\max$ 吗。。。这就去眼科医院。 那么 T5 就切掉了。 T6 发现仍然和前几问一样,从左往右合并就行的。。。 还以为是什么题呢,原来是单纯算就完了吗( 但是 1 序列不太好算,14 个二次式子求和,决定暴力算。 还有 15 min 吗,不过来得及。怎么做这么慢啊草 算了两三遍,然后和选项对上了,就填上去了。后面在略略检查。 ~~查了个寂寞,一个脑残都没查出来~~ 出来后对一下三个计算都没错,但是出正式答案才知道挂了多少分... 大概是 87,233333333要是没有 S 高( 大概就这样了。祝好。不过还是一样菜。 --- ## 10.16 成绩 S 组 85。 J 组 83,果真挂成傻逼。 分数线:S 是 46.5,J 是 50.5。 复习复赛了。 ## 复习 没什么计划,反正这么菜。 不过会把做过的题目列举出来,尽量写题解。 [杂题选做](https://www.luogu.com.cn/blog/vocalise/csp-2020-fu-xi-za-ti-xuan-zuo) --- ## Day 0 下午 3:00 的高铁。只带了手机,要不是要防疫连手机也不会带。 一个晚上就翻了翻模板题。 ## Day 1 ### J 组 早上没啥压力,当作为下午做准备了。 不过还是得认真考的。 进考场,是纯 NOI Linux。写了个 a + b,然后试了试对拍,没问题。 然后下载题目。 T1 直接切了。而且 $n$ 只有 $10^7$,连 `long long` 都不用考虑。 T2 一眼看上去简单的。于是写了一遍,发现读题错了。 但是这东西怎么维护来着...当时差点就上线段树了,但是才发现 $w\leq 600$,于是仍然是个水题,5min 切了。 不过出来后发现即使值域非常大也可以对顶堆。这东西全忘光了。 然而因为这里拖延,已经过去 1h。 T3 首先没什么思路,花了大概 30min 写了一个建树暴力。其中 `!` 的处理用了一点时间。 10:00。 然后看 T4。 这东西好像似曾相识。 想到两个顺序分别 DP 一遍,于是写了,然后大样例过不去,答案算大了。 尝试改,然后小样例就过不去了...怒而重写,发现了错误,开了三个 `dp` 数组,然后过了。 用去 1h。11:00。 回去检查前三题。拍了一下 T2 觉得很稳。 T4 倒没有拍。不过大样例小的可以。 想了一下 T3,然后暂时想不到。出来后就有思路了,对的。 其实考场上要是认真一点,是可以做出来的。 于是还有 30min 时,加文件。 ??????? 我 T4 代码呢??? 变成乱码了??? 不用想,肯定是编译时搞错了。就是 `g++ number.cpp -o number.cpp -g -Wall` 了。 但是还有 30min,不慌。 于是 5min 写回去了。测了样例,对的。 在此时竟然还发现,第一遍写的以为答案最大是 $10^3\times 10^4$ 不会爆,现在才发现是 $(10^3)^2\times 10^4=10^{10}$,于是加了 `long long`,`inf` 改成 $10^{11}$。 真 tm 得感恩戴德。 剩下的时间就在检查。草草草 T1 的 `power.in` 写成 T4 的 `number.in` 了,我是 sb。 然后出来。当场估计是 100 + 100 + 30 + 100 = 330。 如果手速快一点,多一点梦想的话,说不定就阿克了。 ### 中午 没干什么。睡觉没有睡着,也没有什么上午 T3,T4 的消息。 上午用 vim 时发现一个 `tab` 是 $8$ 个格,非常不舒服,忘了要 `set` 什么了。 查一下发现是 `ts`,于是下午记着要改。 ### S 组 心情还不错,上午感受过了机子,不怎么慌。 于是开题。 T1 恶心日期糊我一脸,还记得有道日期题死也调不出来。没错,就是[它](https://www.luogu.com.cn/problem/P1167)。 于是略看下题,没看懂。 觉得有点爆炸,想着这次做出 T1 就不错了。 看后面的题,T2 比较奇怪,不知道 `q` 和 `c` 是干什么用的。不过好像很套路。 T3 和 T4 不抱什么希望。 于是决定对 T1 写一个一天一天加的暴力。然而就是让这个暴力过去样例就花了 1h。 但是好歹有了一点信心(,主要处理了这些东西: - $0$ 年不存在; - BC 的 $1,5,9$ 是闰年。 然后就去写 T2。显然每位独立,果然套路。 于是答案是 $2^x - n$ 了。 随便写了一个,然后过去了。 `q` 和 `c` 果然没用吗??? 诈骗??? 还有,$2^{64}$ 连 `ull` 也存不下。 怎么办?当然是 `long double` 了。 测了一下发现没有误差,好事。 ~~怎么 `printf` `long double` 来着,不管了~~ ~~`std::cout << std::fixed << std::setprecision(0)` 虽然不清楚,但大概是这样用吧~~ 但是觉得很玄,因为没有怎么做过这种有条件不用的诈骗题。 大概只用去了不到 20min。回去 T1。 首先用暴力找了一下 $1582.10.4$ 发现是喜闻乐见的常数 $2299160$,分了个段。 两边分别对于 $400$ 年和 $4$ 年循环模一下,然后一年一年加,然后一天一天加。 快了很多,但是大样例过不去了。发现有很多都是差个几天。 发现直到一年一年加之前都没错。于是懂了,今年是闰年不代表今年到下一年要加 $366$ 天。 于是加上了月日是否在 $2$ 月 $29$ 日前/后的一大串判断。然后过了。 拍了几千组,没问题。 算了下时间,循环模后最多还有 $400$ 年及 $365$ 天,$10^5\times(365+400)=76500000$,应该稳了。 此时已经过去 2h。 T2 还是不放心,于是根据题意写了个 $2^n$ 的暴力,拍了一下,对的。 重新检查。发现 T1 有一个拍炸了,是关于公元 $0$ 年的。还好,小问题。 2.5h,17:00,大概有 200pts。 T3 不会。于是当机立断,打了个暴力。正在写就开始头痛,不过不是很要紧。 T4 也不会,看起来可以搜,但实际上我也不会搜...于是浪费 20min 后写了 $n = 3$ 的 20pts。 差不多 18:00。不是很清楚。 感觉 T3 和 T4 查无可查,于是差不多到这时就把写好的全丢一边了。 类似于颓废地加文件。 还有部分分?不过应该写不完了。 剩下的时间里并没有干什么,也许的确是头痛的原因,没有做其它部分分的想法了。 出来后,直接上地铁,然后高铁,回家是 23:30。 睡了。大概是 100 + 100 + 20 + 20 = 240,大众分。 现在觉得不是没可能做出 T3 的。但是太颓废了。 ## Day 2 只有 luogu 的民间数据。 ### J 组民间数据 T4 意外地挂了 30pts,因为 $1$ 个 `int` 开小了,$1001$ 开到 $1002$ 就过了。~~wdnmd~~ T3 也应该要挂分的,不过 luogu 的小数据里没有。[这里](https://www.luogu.com.cn/discuss/show/276050)提到。 所以是 100 + 100 + 30 + 70 = 300,感觉不是很差,但也挺丢人的。 ### S 组民间数据 T1 过去了。不过还有一点疑问,就在[这里](https://www.luogu.com.cn/discuss/show/275686)。 由于和大家做法都不一样,挺慌的。 100 + 100 + 25 + 20 = 245。 ## Day 3 感觉 T1 有问题啊... 感觉那个帖子里说的 2 月 29 日的确有问题啊... 啊日期都是 1.1 和 10.15 吗( 那没事了( ## Day 10 成绩 J 组 100 + 100 + 55 + 75 = 330 S 组 60 + 100 + 25 + 30 = 215 T1 在 luogu 上交过了,成为全场唯一被卡常的选手。/kk 除此以外和预期情况没差多少。 --- ## 考场代码 留作纪念。 ### J 组 T1 `power.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> const int BIT = 25; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int main() { freopen("power.in","r",stdin); freopen("power.out","w",stdout); int n = read(); if(n & 1) return std::puts("-1"), 0; for(int i = BIT;i >= 1;i--) { if((n >> i) & 1) { std::printf("%d ",1 << i); } } std::puts(""); return 0; } ``` 因为上午 $8$ 格 tab,有点奇怪。 T2 `live.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> const int N = 100001; const int V = 601; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int n,w,a[N],b[V]; int main() { freopen("live.in","r",stdin); freopen("live.out","w",stdout); n = read(), w = read(); for(int i = 1;i <= n;i++) a[i] = read(); for(int i = 1;i <= n;i++) { b[a[i]]++; int l = std::max(1,i * w / 100), rk = 0; for(int i = V - 1;i >= 0;i--) { if(rk + b[i] >= l) { std::printf("%d ",i); break; } else rk += b[i]; } } return 0; } ``` T3 `expr.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> const int N = 100001; const int L = 1000001; // -1 & // -2 | // -3 ! // 0 \n inline int readx() { int x = 0; char ch = getchar(); while(ch != 'x' && ch != '&' && ch != '|' && ch != '!' && ch != '\n') ch = getchar(); if(ch == '\n') return 0; if(ch == '&') return -1; if(ch == '|') return -2; if(ch == '!') return -3; ch = getchar(); while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x; } inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int n,map[N],st[N],tot; int s[L],rev[L],lc[L],rc[L],fa[L],cnt; int res[L]; void Dfs(int x) { if(!lc[x] && !rc[x]) return void(res[x] = s[x] ^ rev[x]); Dfs(lc[x]), Dfs(rc[x]); if(s[x] == -1) res[x] = res[lc[x]] & res[rc[x]]; if(s[x] == -2) res[x] = res[lc[x]] | res[rc[x]]; if(rev[x] == 1) res[x] ^= 1; // std::printf("%d ",res[x]); } void Change(int x) { res[map[x]] ^= 1; int p = fa[map[x]]; while(p != st[tot]) { if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]]; if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]]; if(rev[p] == 1) res[p] ^= 1; p = fa[p]; } if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]]; if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]]; if(rev[p] == 1) res[p] ^= 1; return; } int main() { freopen("expr.in","r",stdin); freopen("expr.out","w",stdout); int x; while(true) { x = readx(); if(!x) break; if(x > 0) { st[++tot] = map[x] = ++cnt; } else if(x == -3) { rev[st[tot]] = true; } else { int b = st[tot--]; int a = st[tot--]; s[++cnt] = x; lc[cnt] = a, rc[cnt] = b; fa[a] = cnt, fa[b] = cnt; st[++tot] = cnt; } } n = read(); for(int i = 1;i <= n;i++) s[map[i]] = read(); Dfs(st[tot]); int q = read(); while(q--) { int x = read(); Change(x); std::printf("%d\n",res[st[tot]]); Change(x); } // std::puts(""); return 0; } ``` T4 `number.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> typedef long long ll; const int N = 1001; const ll inf = 100000000000ll; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int n,m,a[N][N]; ll dp1[N][N],dp2[N][N],dp[N][N]; int main() { freopen("number.in","r",stdin); freopen("number.out","w",stdout); n = read(), m = read(); for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) a[i][j] = read(); for(int i = 0;i <= n + 1;i++) for(int j = 0;j <= m + 1;j++) dp[i][j] = dp1[i][j] = dp2[i][j] = -inf; dp[1][0] = 0; for(int i = 1;i <= m;i++) { for(int j = 1;j <= n;j++) dp1[j][i] = std::max(dp[j][i - 1],dp1[j - 1][i]) + a[j][i]; for(int j = n;j >= 1;j--) dp2[j][i] = std::max(dp[j][i - 1],dp2[j + 1][i]) + a[j][i]; for(int j = 1;j <= n;j++) dp[j][i] = std::max(dp1[j][i],dp2[j][i]); } std::printf("%lld\n",dp[n][m]); return 0; } ``` ### S 组 T1 `julian.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> typedef long long ll; const int Q = 100001; inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int mon[13] = {0,31,0,31,30,31,30,31,31,30,31,30,31}; struct Date { ll y, m, d; Date() {} Date(ll _y, ll _m, ll _d) : y(_y), m(_m), d(_d) {} friend bool operator <(const Date &x,const Date &y) { if(x.y != y.y) return x.y < y.y; if(x.m != y.m) return x.m < y.m; return x.d < y.d; } friend bool operator ==(const Date &x,const Date &y) { return x.y == y.y && x.m == y.m && x.d == y.d; } friend bool operator <=(const Date &x,const Date &y) { return x < y || x == y; } int Run1() { ll Y = y; if(y < 0) Y++; Y = (Y % 400 + 400) % 400; return !(Y % 4); } int Run2() { ll Y = y; if(y < 0) Y++; Y = (Y % 400 + 400) % 400; return !(Y % 400) || (!(Y % 4) && Y % 100); } int Month1() { if(m != 2) return mon[m]; if(Run1()) return 29; else return 28; } int Month2() { if(m != 2) return mon[m]; if(Run2()) return 29; else return 28; } void NextDay() { if(*this < Date(1582,10,4)) { d++; if(d > Month1()) d = 1, m++; if(m > 12) { m = 1; if(y == -1) y = 1; else y++; } } else if(*this == Date(1582,10,4)) { *this = Date(1582,10,15); } else { d++; if(d > Month2()) d = 1, m++; if(m > 12) { m = 1; if(y == -1) y = 1; else y++; } } } void print() { if(y < 0) std::printf("%lld %lld %lld BC\n",d,m,-y); else std::printf("%lld %lld %lld\n",d,m,y); } }; void AddY(ll &y,ll d) { ll p = y; y += d; if(p < 0 && y >= 0) y++; } void Solve1(Date now,ll r) { const int L = 365 * 4 + 1; AddY(now.y,r / L * 4); r %= L; while(r >= 366) { if((now.Run1() && Date(0,now.m,now.d) <= Date(0,2,29)) || (Date(now.y + 1,now.m,now.d).Run1() && Date(0,2,29) < Date(0,now.m,now.d))) r -= 366; else r -= 365; AddY(now.y,1); } while(r--) now.NextDay(); now.print(); } void Solve2(Date now,ll r) { const int L = (365 * 4 + 1) * 100 - 3; AddY(now.y,r / L * 400); r %= L; while(r >= 366) { if((now.Run2() && Date(0,now.m,now.d) <= Date(0,2,29)) || (Date(now.y + 1,now.m,now.d).Run2() && Date(0,2,29) < Date(0,now.m,now.d))) r -= 366; else r -= 365; AddY(now.y,1); } while(r--) now.NextDay(); now.print(); } int main() { freopen("julian.in","r",stdin); freopen("julian.out","w",stdout); int q = read(); while(q--) { ll r = read(); if(r <= 2299160) Solve1(Date(-4713,1,1),r); else Solve2(Date(1582,10,15),r - 2299161); } return 0; } ``` T2 `zoo.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> #include <iomanip> typedef unsigned long long ull; const int N = 1000001; const int BIT = 64; inline ull read() { ull x = 0; bool f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int n,m,c,k,p[N],q[N],ocp[BIT]; ull a[N]; int main() { freopen("zoo.in","r",stdin); freopen("zoo.out","w",stdout); n = read(), m = read(), c = read(), k = read(); for(int i = 1;i <= n;i++) a[i] = read(); for(int i = 1;i <= m;i++) p[i] = read(), q[i] = read(), ocp[p[i]] = true; long double ans = 1.0; for(int i = 0;i < k;i++) { int v = 0; for(int j = 1;j <= n;j++) v |= (a[j] >> i) & 1; if(v || (!v && !ocp[i])) ans *= 2.0; } std::cout << std::fixed << std::setprecision(0) << ans - n << std::endl; return 0; } ``` T3 `call.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <cstdlib> const int N = 100001; const int P = 998244353; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int n,a[N],m,t[N],p[N],v[N]; std::vector <int> g[N]; void Call(int i) { if(t[i] == 1) a[p[i]] = (a[p[i]] + v[i]) % P; else if(t[i] == 2) for(int j = 1;j <= n;j++) a[j] = 1ll * a[j] * v[i] % P; else { for(int j = 0;j < p[i];j++) Call(g[i][j]); } } int main() { freopen("call.in","r",stdin); freopen("call.out","w",stdout); n = read(); for(int i = 1;i <= n;i++) a[i] = read(); m = read(); for(int i = 1;i <= m;i++) { t[i] = read(); if(t[i] == 1) p[i] = read(), v[i] = read(); if(t[i] == 2) v[i] = read(); if(t[i] == 3) { p[i] = read(); for(int j = 1;j <= p[i];j++) g[i].push_back(read()); } } int Q = read(); while(Q--) { int i = read(); Call(i); } for(int i = 1;i <= n;i++) std::printf("%d ",a[i]); std::puts(""); return 0; } ``` T4 `snakes.cpp`: ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> const int N = 1000001; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar(); return x * f; } int n,a[N]; void Solve() { int ans = 0; if(a[3] - a[1] >= a[2]) ans = 1; else ans = 3; std::printf("%d\n",ans); return; } int main() { freopen("snakes.in","r",stdin); freopen("snakes.out","w",stdout); int t = read(); n = read(); for(int i = 1;i <= n;i++) a[i] = read(); Solve(), t--; while(t--) { int k = read(); while(k--) { int x = read(), y = read(); a[x] = y; } Solve(); } return 0; } ``` 这里不知道为什么两个 `#include` 间没有空行,不过编译只有 `Warning`,这是好的。 --- ## 评价 - 复习的全没考。T3 可以线段树合并?~~那我什么也没说~~ - J 组较去年比较简单。(大概) - S 的 T1 恶心人。自己做题量也远远不够。 - 全省 J 组和 S 组都只坐了一个机房,200 人左右。 - 学校方面服务满分,一个一个问你有没有上传代码。 - 想找 WYX 和 LHQ,结果没找到。 应该算是符合水平的成绩吧。 - 要有梦想,去猜正解。 - 要多打比赛,练手速。CF 不能用娱乐式的打法了。 NOIP 是啥,不知道。 如果真可以参加(想桃子),会开新坑。