当前位置:网站首页>CSP-S 2020 游记

CSP-S 2020 游记

2020-11-10 12:48:06 osc_zk7ydfv6

本博客建立于 2020 年 11 月 6 日晚,于次日正式认证后更新涉及题目的内容并公开。本人未提前知晓认证试题,请读者不必恐慌。

Day -4

久违地 AK 了一场模拟赛。

Day -2

因为模拟赛不给大样例,T3 T4都A了,反而挂了 SB 模拟和欧拉路板子题,300分。

不过呢也是好事,至少不会给自己太大的压力吧。

Day -1

吹了一上午的水,中午离校。

下午去看考场,和门卫对线后对方表示没有接到任何通知,所以进不去……?

然后回家看了会 CDQ 分治,还是无法理解它的本质。

因为太久没写状压dp,就写了个斯坦纳树练练手,又一次惊异于这个绝妙的构思。

写了个整体二分,调了半天发现又是手贱把 vr 写成了 r……

搜了几篇游记看看发现完全没用。

写了发左偏树,还WA了一次

众所周知,考前复习板子的作用是把它移出考纲

睡了

Day 1

梦见在熬夜打麻将

上午划水,看了下板子

下午进考场,感觉精神状态不错

13:50 就进机房了,然而不让动电脑……

感觉这键盘比自己的还好用?

14:20 发题,密码好像是什么 他山之石?

怎么输都不对

过了会儿进来个工作人员说这是上午的密码……orz

然后在大屏幕上打出真正的密码,可以攻玉?

先是把 0 输成 o,然后还是怎么输都不对。旁边的老哥也怎么输都不对,监考过来看了我的屏幕一眼,

“你输的括号呢?”

……

T1 ……大模拟
T2 奇怪的东西
T3 好像是个数据结构?
T4 诡异的博弈论


先把月份天数的数组打出来!然后什么都不会了……

把公元前看成负数+1,可以少判很多奇怪的东西。感觉十分精神污染,就直接一个月一个月加,1582 年 10 月特判一下,貌似就有 80 分了?

后面随便打个暴力都有三四十分吧,先放了

15:00 发现 T2 非常的水,随便写一下就过大样例了,特判一下 2 64 2^{64} 264 ,但感觉非常不稳。

15:20 开 T3 ,怎么看都像可持久化线段树合并,但这个 256M 空间限制了我的想象力……而且 DAG 线段树合并的复杂度好像不太对。

遇事不决根号分治?考虑按每个函数的调用次数数据分治,发现没有任何用处。

然后看了下部分分,只有乘随便做,只有加……维护每个函数的调用次数?

有乘法的话把这个调用次数带个前面乘的数的逆元的权就可以了?

那就是记录一下之前的乘积,然后乘到这个点的线段树上再乱搞一下?

16:00 了,感觉有点虚,就先打了个指数级暴力,懒得分析有多少分。

发现不用线段树啥的,直接记录每个点的贡献往下甩锅就可以了。

于是在草稿纸上写下了:

  1. 拓扑排序
  2. 倒着计算每个点乘上的数 m u l u mul_u mulu
  3. 正着计算每个函数的贡献 f u f_u fu

写出来大样例死活过不去,就把暴力拉过来测,发现大样例暴力跑得飞快……

把最后一步乘以总的乘积注释掉,发现第一个答案和暴力是一样的,但注释前不一样。说明是总乘积算错了?

重新开个文件人肉而二分,最后发现我拓扑排序只把虚点压进队列里了,但有些没用的点会贡献度数,导致一些点入不了队……

改了之后很快过了。

17:00,写了个数据生成器对拍

然后 RE 了,调了一下发现生成器有环,就强制让编号大于自己

然后暴力 T 了,就把数据改得非常小。

然后还是拍不上,标程好像输出不了文件,但双击 exe 运行是对的。开始以为是暴力太慢,但改了顺序和一步一步执行都没用。后来发现批处理有个叫 call 的命令……

17:30拍上了,挂在后台慢慢跑。 T4肯定没希望了,就用 vector 写了个指数级暴力,很快过了。

回去突然发现 T1 拿不到 80 分……于是冷静分析正解。

拿暴力人肉二分历法起点到公元元年和消失的 10 天的天数,然后前面 4 年为周期,后面 400 年为周期先算出整块的,剩下的先年后月暴力,日直接加上。1582年后面两个月硬讨论。

还有 15 分钟,边开虚拟机边调 T1。最后 5 分钟调出来了,随便测了下就交了。

预估

T1 因为 1582 年后面两个月的硬讨论出了点问题,会在 1582.12.1 \text{1582.12.1} 1582.12.1 1583.1.1 \text{1583.1.1} 1583.1.1 挂掉,民间数据只有 40pts。

T2 k = 64 k=64 k=64 并没有判完,还是会 ub。

T3 0 0 0 求的逆元是 0 0 0,所以一旦乘了 0 0 0 输出会全是 0 0 0 。不知道会不会卡。

T4 其实状态只有 O ( n ) O(n) O(n) 个,复杂度是 O ( n 2 ) O(n^2) O(n2) 的。

最低 40+60+60+55=215,最高 100+100+100+55=355,期望 40+95+80+55=270

真刺激

听天由命了

版权声明
本文为[osc_zk7ydfv6]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4389900/blog/4711093