希望别伏笔
小插曲:考前 2 天说取消了,但是过了 1 天又说恢复。
Day 0
鉴于去年吃了不会网络流的亏,这次把各种算法都看了一遍,但是不想看LCT,如果考了我只能问候出题人的家人。
最后随便网上找了几道题做了一下,感觉状态还行,就先睡了/shui
Day 1 上午
睡大觉
下午
来到了半年前省选的考场,想起当时 Day 2 因为心态不好,而错过初三进入省队机会的悲剧,我心情有些复杂。
但是今天只是个体验一下的 CSP,我并不是很紧张。
和伟大的 sjc 进入考场,RP=inf
坐下来之后,发现竟然用的是笔记本,不过感觉笔记本的键盘小一点反而比上次的台式机好用。
感觉也没什么要写的板子,就先写了快读和各种define
今年的 T1 有点意思,差不多用了 30min 过了样例,大样例下发后也过了,感觉不会出问题,准备如果后面的题目做完了有时间再回来看。
T2 非常无聊,观察到查询较多,写了个 ST 表,分类讨论了一下,30min 过了所有大样例,试着改掉程序的几个分类讨论的细节,发现都无法通过大样例,感觉强度还可以,先扔了。
T3 很有意思,想了一会怎么维护这个东西,但是发现几乎不可行,就想了些歪路子,发现竟然可以 hash,因为只要判断整个序列相不相等,可以对每个位置附上一个随机值,直接用每个位置的出边数乘上当前位置的随机值,判断是否相等就行了。
T4 看了一遍之后发现 k=2 且带修就是个非常经典的动态dp,所以我用了树剖,但是没修改可以直接倍增,我傻了,树剖是log方的,好在跑的还算快。想了一下 k=3 发现最多只会走到和路径相邻的点,直接把每个点相邻最小的点当作初始矩阵中离两边都是 1 的点即可,还算好写。虽然我感觉这做法要 T 飞,但是造一下数据,发现还挺快的。
最后有差不多半小时检查,各种瞪眼之后,感觉没问题。
在infoj上都过了,但是数据好像很水,洛谷124也过了,T3数据还没有
标签:大样,发现,一下,CSP2022,感觉,Day,但是 From: https://www.cnblogs.com/njwrz/p/16840295.html