2021 GDOI 普及省选游记

因为就在我们学校举行，所以我就是来凑个热闹+%%%各位大佬的。 ### DAY 0 下午两点钟的时候，被教练叫去拍照（只有我们队的\qq），拿了牌子。 五点多的时候考完泛珠模拟考（难死了草）。 看到楼下还挺多人的。 然后去签到，发现竟然和深中大佬住同一个宿舍%%%。 下午打了会篮球，然后回到家（离得近）。 回家之后，那就只能做题喽。 也就看了几道题，没有任何想法就先颓废了。 希望明天能正常发挥+要到大佬们的签名%%% ### DAY 1 上午一早就起来去学校打篮球了qwq。 打到快讲评的时候就回去了。 讲评讲的是搜索和 DP 本以为会将什么高大尚的搜索（IDA* 或 A* 等），谁知道竟然就讲普通的搜索+记忆化....... 然后就开始写作业，看着旁边的 BMTX 爆切高数，看着初一的 tjb 大佬在睡觉。 然后就讲到DP了，然后就震撼我了，竟然讲数位DP（草是我太菜了还是啥怎么感觉大家都学过）。 把区间DP和背包重新理解了一番，之后就在那里专心的听数位DP，但最后还是一知半解（初一的tjb大佬还是在睡觉%%%）。 讲评的时候，老师告诉我们明天的题里面有两道数位DP（总共三道题），然后他给我们讲了一道明天题目的弱化版。 题目大意大概是：问有多少非负上升序列，满足每个元素都小于n，且没有相邻三个元素异或和为零。 然后就到了下午，下午的比赛有三道题。 把全部题目都看了一遍后，看上去T1是道博弈论，T2是道数学题，T3是道图论，有点求环的意思。于是先开T3。 数据是 $10^5$ 级别的，所以只能用SPFA。花了大概半小时打完。 接着开T2，T2跟钟表问题很像。我想的是判断差是否相同，相同的话看顺时针逆时针哪个时间短。 接着看周期，大概不超过 $43200$ 就能得到一次答案。十分钟打完。 最后开T1，第一组样例是最简单的情况，简单的判断了一下。 接着看第二组样例，看着看着好像发现了什么：好像是（最大数 $+ 1$)$\times \frac{1}{2}$。大概五分钟打完。 三道题打完刚刚好一小时。 然后花了十多分钟仔细地检查了文件等。 然后就开始“脚造小数据”了。 很幸运，T3第一次造的数据就把我的代码 hack 掉了，仔细地想了想，看了一下题面，惊奇的发现竟然看漏了一句话 `不会走回头路`，一顿魔改，把代码改为了 SPFA+dfs，然后发现好像SPFA有问题，于是只留了dfs,又造了几组样例，都过了（）。 然后搞T1,搞着搞着发现好像不太对劲，好像是个二分，就赶紧写了个二分,然后连样例都没过，就改回去了。 然后看T2,随手打了几个数据，都炸了，赶紧查代码，发现存差的时候有一个地方忘记打abs了az。 考完试后，与其他学校的奆佬交流，发现我T3打假了。 正解应该是tarjan判环？我连环都没判,瞎打还忘记清0了......。 有个 $270$ 分最高分的大佬%%% **T1：** 估分：$[60,100]$ 实际得分：$100$ **T2** 估分：$[60,100]$ 实际得分：$40$ **T3** 估分：$[40,60]$ 实际得分：$0$ **总分** 估分：$[160,260]$。 实际得分:$100+40+0=140$(wtcl) **DAY1总结** 总的来说，这次比上次打NOIO的时候最大的进步就是考试心态很稳定，不会很慌张。希望明天也能保持这样的心态。 另外可以发现，自己估的分与实际得分有很大的出入，这说明了我的还是很菜的。 ### DAY2 上午又去打篮球了（（（ 顺便在听讲座前把 [P2657 [SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657) A 了。希望自己今天数位DP能拿到点分。 讲座讲的东西是我最不会的——贪心。 当然不只是单纯的讲贪心，还会串杂DP，二分，背包等 当然最难的可能都在后面了（对我而言），哈夫曼树，反悔贪心等。虽然自己认真听了，但是还是没太听懂（%%%上台讲思路的大佬。） 中午吃完饭后，就一个人在教室里打数位DP，顺便还小睡了一会。 到了下午，便进了考场。 当时的心态不像昨天那样稳定了，心里更多的是害怕，毕竟DP是我最不熟的，更何况还是我昨天才第一次接触的数位DP。 考试开始了，按照往常一样，先把题目全部看一遍。 T1,字符串匹配？KMP?完蛋不会了，看样子只能打个暴力。 T2，什么？就是昨天那到被魔改的题？草怎么从连续三个变到连续四个了？这我打个鬼。 T3,就这？就这？就这？不就是模拟吗。再看了一下样例，草这是什么鬼。贪心？DP?不会。 危今天要爆零了。 先打T1,20分钟打了个 $O(n^2)$ 的暴力+一点小优化。 然后直接看T3，1h打了个模拟骗分 接着看T2,T2按照昨天老师的思路，看上去是要二进制分解，然后找到一些可行的规律，结果又花了40min,连个毛都没找出来，暴力也不会打，就把样例打上去了。 接下来还有大概1h的时间，先是查了查T3模拟，发现第三个样例过不了。想了想，想到了怎么改正确，但是发现复杂度增长了一个指数级，于是就放那了。 这个时候还剩下10几分钟的时间，就查了查注释，输出，checker。 然后就重新肝T2，虽然到最后还是没肝出来。 出考场之后，听说3,4,5考场那边的Pdf炸了？延迟20min开始。 出考场就赶紧回到教室，BX就开始了他的肝题面。 他竟然把题面完完整整一字不拉的抄了下来（他哪来的时间）。 问了一下同班的大佬，发现他们也快打傻了，他们肯定会比我高得（确信）。 晚自习的时候就在班上写作业qwq。 然后省选就结束了 **T1** 估分：$[40,60]$。 实际得分：$30$ **T2** 估分：$0$ 实际得分：$10$ **T3** 估分:$[0,20]$ 实际得分：$0$ **总分** 估分:$[40,80]$ 实际得分：$30+10+0=40$ **DAY2总结** 实际上没什么好总结的，就是自己太菜了，没得说。在CSP前争取多刷题！ 最终得分：$100+40+0+30+10+0=180$ $rank$ $90$ ### 整体总结 可以发现，这次考试，我能跟往常一样，还算准确的判断出了正解的算法，可惜不会打。 这次的心态也很好（可能是ls让我们多大比赛的原因？） 下次继续保持。 不得不说，这次的省选给我的启发还是很大的，希望下次还能参加，还是以自己的实力参加（今年是东道主名额参加的）。 ## 2021RP++