tiger2005 的博客

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

然后冷静分析了一下题目和数据范围。

?这 CQ 是来干什么的。如果要考出什么难度就把“互不相等”的条件删掉啊.jpg

然后 15 分钟水过去了。

T2 - $O(N+M) - 100pts$

之后是 T3。整体乘单点加,熟悉的味道.jpg想起了之前某道神奇的题目我神奇的做法。链接

然后开始大力瞎搞。

先是看到数据提示“关系形成一条链”什么的,然后就打了一下拓扑排序。

然后开始套用上面的方法。先倒着搜一次拓扑序把每个函数调用后数组被乘的系数是多少(设为 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 分。


2020-11-07 21:19:06 in 未分类