CSP2023游记

发布时间 2023-11-03 21:30:08作者: Mr_KaYa

省流:挂麻了

考试前

疯狂复习了板子,一进考场走了一发线段树,看时间还够就写了写 LCA、Tarjan、AC自动机等提高组的高频考点(结果啥也没考到/kk)

考试中

信心满满开题,一读 A 整个人都傻了,这不是普及题?没仔细看,先读完了所有题,用了大概20分钟。鉴定一下,A是傻子题,B看起来很DP,C感觉就是模拟?D好像可以二分。

开A,重读了一遍题面以免读错题,结果一看样例二给我整不会了。啊?这里思维直接死掉,我当时觉得两个同时转相对差应该不变(或者变为10-相对差)过了将近半个小时我才发现可以一个锁转两个拨圈,另一个锁转一个。好家伙,10min胡乱写了个结论,当时没想暴力(败笔1)结果错的结论胡乱过了我自己手糊的hack,也没对拍就开B了(upd:A只需要81n序列暴力求交就可以了,错误原因是没保证给的5长度序列互不相同,要是保证不同结论很对,sad)。

开B,时间是15:40,看起来就十分DP。我先看了可消除序列的式子,发现要么回文,要么回文拼起来的(这里想的不对,如 caabbc)。初始想了好几种DP状态,尝试n方暴力转移,结果写着写着发现好像只需要记录一个上次出现的位置 \(pre_i\) 转移。这样就是线性的了。附上丑陋的错误式子

\(f_i=f_{i-1}+check(pre_i+1,i-1)+g_{pre_{i}-1}\)

其中check用来判断是否合法(map维护),g记录连续的合法段个数。

结果过不了大样例,一直手造hack自己但hack不掉,回来觉得自己式子非常对,就很迷。调啊调,脑子都不清醒了。中途我想写个 simple 做法来着,但是想着能写正解,就不浪费时间了(败笔2)也没写C和D。(upd:看了B的原 CF1223F *2600题解解法是神秘的矩阵qwq还是菜了呀)
(upd2:B也有字典树+栈 || 哈希栈的做法)

只剩下半个小时了!我一看不好,B的大样例还是不过,只能去看C和D的暴力分能不能拿到。C看起来纯模拟肯定写不完了,所以去做D。二分以后处理一下每棵树最晚啥时候种,合并一下这些约束信息好像可以?写写写,写不完!当时慌慌慌,剩下5min,不敢写了,检查了文件跑路/kel

考试后

出考场感觉非常寄。问了问群u,今年的B竟是CF原题。C真是模拟即可,怒骂出题人!忍不了了!回家测民间数据,发现A结论挂了,B挂麻了(大悲)D的想法似乎很对但没写完,感觉要死了。

这次主要是是没稳切A,当时1个多小时才做出A慌了,没写拍子,也没细想会不会有坑,就去做B。还有就是C的模拟应该是稳拿分的,B的n方也有50分,不应该一味去写正解,先打暴力!先打暴力!先打暴力!最后时间不够了D也没写完。这次属于4个题都有思路但考的很拉。思维能力和代码能力还是太弱。开摆了,好好准备NOIP争取翻盘。