CSP 2020 S2 游记

UPD: 这个垃圾炸成 320 pts 了 /kk ### Day -7 -> Day -1 ~~全部在编写和升级聊天室~~准确来讲其实也是有复习的。打了几场模拟赛热身。 ### Day 0 终于开始超级全面的复习。打了 后缀数组 扩展欧几里得 矩阵乘法 网络流 Tarjan AC 自动机 顺便自学了 线段树合并。~~然后这些知识点一个都没有考到~~ ### Day 1 早上强行喝了一罐红牛提神。毕竟我前一个星期太肝了我爸我妈看到我脸色就不对（但是我内心非常精神）。 好的准备考试。拿着我爸给我的一瓶“动脉”上考场。然后被承认自己菜后满意的走进考场。 毕竟在主场考试，电脑也用多了，也就习惯了。考试的时候心跳十分平静。 先开 T1。微微扫了一眼，嘴里默念着：“出题人我***” 然后花了 10 分钟定在电脑前。10 分钟终于发现自己快睡着了然后调出计算器把年份一个个算出来。然后花了 15 分钟写好了代码。最后 5 分钟扫了代码然后把 0 年的锅修了。 T1 - $O(400Q) - 100pts$ （因为我判年份没用二分） 然后开 T2。一开始还以为是 $0 \to 2^n-1$ 差点开始动手打高精度 /kk 然后冷静分析了一下题目和数据范围。 ？这 `C` 和 `Q` 是来干什么的。如果要考出什么难度就把“互不相等”的条件删掉啊.jpg 然后 15 分钟水过去了。 T2 - $O(N+M) - 100pts$ 之后是 T3。整体乘单点加，熟悉的味道.jpg想起了之前某道神奇的题目我神奇的做法。[链接](https://www.luogu.com.cn/blog/tiger2005/solution-of-p6835) 然后开始大力瞎搞。 先是看到数据提示“关系形成一条链”什么的，然后就打了一下拓扑排序。 然后开始套用上面的方法。先倒着搜一次拓扑序把每个函数调用后数组被乘的系数是多少（设为 `M[i]`）。然后在询问的时候算出每个函数运行前面函数时数组乘上的数的积，把其倒数累加起来。 然后函数 DAG 内每一个点都有一个系数（假定为 `x`），那么：（伪代码仅供参考） 操作 1 = `a[argv[0]]+=argv[1]*niyuan(x)%Md;` 操作 2 = `none` 操作 3 = `for i in argv: x[i]+=t,t*=niyuan(M[i]);` 最后把数组乘上一个总值就算出来了。 然后这代码就写了 40 分钟…… T3: $O(N+\sum g_i) - (100-?)pts$ （有乘 0 就会炸开） 最后就是 T4。还是瞎搞，但是复杂度未知（最高 $O(nTlogn)$） 这道题明显是让你求每条蛇被吃的时间和每个时间的决策。算的时候就看当前答案的时间内自己会不会被吃。 但是用 $O(n)$ 的复杂度模拟过程就很复杂.jpg T4 - $O(nTlogn) - (70+?)pts$（常数低，因为有优化） 还剩下 90 分钟，开始操作。 首先回去看 T1，发现大数据要开 `long long`，然后紧急救回 5 分。 然后是 T2。自己搞了一个 `0 0 1 64` 发现答案是 1 。之后就把 `(1ull<<64)` 的特判整上了。救回了不知道多少分。 之后是 T3。把逆元放在一开始，差点就把复杂度写成 $O(32M)$。 T4 的话突然发现自己假了。追加了一些特判。 最后，离考试结束还有 15 分钟，我打了一个快读嵌到所有代码里面，效果不错。 最后 1 分钟把 `snakes4.in` 改了过来。 最后的一些时间成功挽回了至少 50 分 qwq 考试出来跟 VG 讲了半个小时的 T3，回到家才发现自己没有判 0 qwq --- 总的来说除了 T1 贼恶心外难度放低了。 目前估分 `100+100+(100-?)+(70+?)=370(?)`。还是太菜了 /kk UPD: luogu 测 T3 因为没有判 0 被卡了 20 分。