NOI2023游记

· · 个人记录

两题了不起，一题夸自己。

六十也算赢，拼暴力也行。

爆零就爆零，天天好心情。

模板

https://music.163.com/#/song?id=436514312 \color{white}.

day -1

报道日.

面到了 Daniel_lele.

复习了一下笔试，抢学了一下gdb.

day 0

上午开幕式.

下午笔试+试机.

虽然靠着蒙题能力AK了，但还是要强烈谴责一下：

《完全出自本题库》

day 1

8:00开考

T1无脑数据结构. 9:50 拍完.

然后想T2. 很快发现条件1等价与T'中1~n构成的虚树与T相等.

然后发现 k=0 的时候可以 O(n^3) dp.

然后没什么思路了. 去看T3.

首先有个经典性质：dfs树没有横插边.

结合容斥可以做到 O((n+m)2^k).

然后发现T是链的时候可以线段树优化dp.

然后发现可以带上容斥系数 O(n^3) dp.

此时 11:00. 然后发现T3 O(n^3) dp巨大难写.

赶紧冲一把. 12:20 过了大样例.

然后推了一下T2式子. m=0 时答案为 1，m=1 时答案为 n+n-1，m=2 时答案为 (n+n-1)(n+n+1)+[k>0](n-1)（插入两次）.

事实上这三档部分分是对 k=0 有很大的提示性的（\prod_{i=0}^{m-1}(2n+2i-1)）. 但是我当时非常愚蠢，没有想过把它扩展到 m>2,k=0 的情况. 事实上确实有很多人拿到 k=0 的分. 亏麻了.

然后花了5mins冲了一下T2 n,m\leq 4 的暴力，最后检查了一下freopen等，比赛结束.

估分：100+35+64=199

下午查分，T2 n,m\leq 4 的暴力被卡常，T3在前16个点随机挂分，过了5个.

实际：100+25+20=145

估计略低于银牌线. 想要Ag day2还要努力啊！

晚上听题. T2答案和树的形态没有任何关系. 震惊到我了

day 1.5

8:10 才起来，吃完早餐已经 8:50 了.

然后去嘉年华.

结束后去看电影. 电影之前看过，但还是再看了一遍.

day 2

T1憨憨题. 9:50 写完拍完.

T2比较神秘. 不过马上意识到字典序小相当于后缀数组中rk小，但是字典序等于的时候会出问题. SA+主席树然后对前30个特判一下即可过掉性质A. 感觉特殊性质B有点神秘.

然后就不会了，想了半个小时没有一点思路，于是搞T3.

然后发现T3也没什么思路，想了半小时无果，此时已11:00.

然后转去写T2. 12:00写完. 然后发现过不了样例. 模拟了一下感觉没什么问题，一看题目：s[i:i+l-1]<R(s[i+l:i+2l-1])

开场4小时，我才发现，我看错题了！

有点崩溃. 不过正确的暴力只需在原来暴力的基础上将字符串翻折一下即可，而且还可以顺便过掉性质B. 冷静了一下，发现正解好像只需在原来的基础上加上manacher然后再开一个主席树，不过想到了也写不完了. 赶紧把暴力改完，然后卡了卡常. 此时已 12:40.

最后20分钟冲了冲T3 20分暴力，最后2分钟调完，然后遗憾离场.

估分：100+72+20=192

实际：100+72+0=172

下午面了 wsc2008

总分：100+145+172=417

卡线ag. 今年jz 6块银牌.

再接再厉.

Linshey：我最喜欢的科学家是北京的EntropyIncreaser李白天.