HNOI2019

先喷一句，没有大样例，差评。
再喷一句，数据水，好评。

预计 80' ，实际 110' 。

我真是个奇葩实际分比预计分高。。。

Day0-

省选前三天教练每天给我们推一道题，都是主席树应用（教练曰“线段树模板”）。
都是看了题解的思路才做出来的，自己想就找不到用主席树维护的地方。

不知道为什么这三天效率都挺高，这三天我 A 的题目估计有我平常一个星期的 A 题数。。。

然而还没来得及复习每个知识点，省选就来了。

Day1

预计 70' ，实际 40' 。

fish

我看到这题的时候就意识到我只能打暴力了。
计算几何？我对这块一片空白。
好吧，硬要说思路我大概想得到枚举线段，按斜率搞个什么数据结构？
然后真的不会，敲暴力滚粗。

预计 20' ，实际 20' 。

jojo

前缀和后缀相同？求 KMP 的 fail 数组嘛。
暴力求，一次加几个字符就求几次 fail, 全加起来就是答案。
可持久化？版本树像个 AC 自动机，但是没管这么多，无脑写了个可持久化数组。
因为是把每个字符暴力求的，只能过前 50' 。 结果我后面 30' tm TLE 了？ $ O(n log(n)) $ 的时空复杂度跑 1e5 要 6 秒？

预计 50' ，实际 20' 。

polygon

什么鬼畜题啊，简化一波题意。
把线段看做一个区间，除 (x, x + 1) 外每个区间一定可以划分成两个子区间。
然后把每个区间看做一个点，相当于有了一个满二叉树。
然后旋转操作就相当于把一个点 blablabla 换一下位置。
旋转次数可以贪心，方案数不会，大概要 DP ？
然后想着就求旋转次数吧，看看数据范围。。。
沃日 90% 的数据都要求方案数？小 W 的心情得多差啊。。。
当时我还没打其他题，感觉比较亏，就先做前面的题了，结果最后都没打。

预计 0' ，实际 0' 。

Watering

下午直接去机房颓废，死神 vs 火影真好玩。
还有被 lyy 安利太阳系争夺战，画风清新，内容硬核。

Day2

emm, 我是来测数据湿度的。。。
结果真被我水过去了。。。

预计 10' ，实际 70' 。

所以说有想法就要实现 不然就没事干了 2333 。

tour

u = v 或者 s[u] = s[v] 且 u, v 相邻的时候 (u, v) 一定是可行的。
其他点对 (u, v) 可行当且仅当 s[u] = s[v] 且存在 u -> u2, v -> v2 且 (u2, v2) 可行。
DP ？有环。
然后就只能把一个点对看做一个点，对于新的点建图，如果从初始的可行点能跑到 (u, v) 则 (u, v) 可行。
点数 $ O(n^2) $ ，边数 $ O(m^2) $ ，复杂度 $ O(n^2 + m^2 + q) $ 。
然而第一档暴力 m 就有 1e4 ， 纯随机数据开O2 本地测了一下跑 5s, 真棒。

预计 0' ，实际 30' 。

dance

好迷啊，看了看 n = 1 有 40' ，就去想 n = 1 怎么做，
推了推就是个式子： $ ans_i = _{j=0} C_L^{i+j k} W^{i+j k} $ 。 把每个 $ C_L^x W^x $ 算一遍，快速幂复杂度 $ O(L log(L)) $ ，
然而 L 有 1e8 。。。
线性都跑不过去吧这，但我实在没别的思路，就想试试线性。
做法就是预处理，预处理 L 以内的逆元和 $ W_i $ ，再线性求一排的组合数。
时空复杂度都是 $ O(L) $ ， 开 O2 本地测试 17s, 就算不 TLE 都得 MLE 。

预计 0' ，实际 30' （考完后再放本地测可以水 40' woc）。

看了看实际的 L 只有 1e7 到 2e7 左右，真棒。 至于空间，我还算有点脑子搞了波动态开空间，不然直接开 1e8 的数组肯定得炸。

sequence

b 是整数的话还能枚举枚举。分数？没救了感觉。
于是只打了 10' 的整数 DP 。

预计 10' ，实际 10' 。

Watering

下午本来打算去黄兴街打游戏的，先去麦克唐纳德吃中饭，吃完后发现就已经 3 点多了没什么时间。
于是放弃了 xbox 又回到机房颓废，死神 vs 火影昨天已经玩熟练了，打起来比较轻松。

Day3+

省选完了，结果并不想想象的那样，即使运气眷顾了我还是 wei 的一批。
实力不够啊，说啥都是扯淡。

常规欠下的帐也该还了，滚回去学文化课啦，接受作业的洗礼。

One Year Later

update on 2020.04.08

一年过去了，重新审视了去年的 HNOI ，再次分别总结一下吧。 （从去年省选到现在，这些题碰都没有碰过）

新一轮省选不远了。

fish

咕咕咕。

jojo

去年，我甚至不知道均摊数据结构是不能可持久化的，打了一个主席树满以为复杂度一个 log 。
可事实上 KMP 的最坏复杂度是 \(O(n)\) ，可持久化后复杂度可以到 \(O(n^2)\) 。

可是现在我还是不会做 jojo ，甚至看题解也看不懂，现在上考场估计也还是 20pts 。

polygon

这题不难的啊，至少现在我看来如此。
不考虑修改的话就可以分治处理这个问题，考虑上修改就动态维护分治的树状形态即可。
而方案数就是分治树的拓扑序数量。

A 了，现在上考场有信心拿到 100pts ，只不过可能得花上至少 2h 的时间。

tour

思路很妙，同类型的边的偶环是没有意义的，可以删边使得同类型的边偶环不存在进而把边数控制在 \(O(n)\) 。
可惜我没能独自得到这个结论，还是看了题解的，看了后有一种恍然大悟的感觉。

现在上考场也许还是只会 \(O(m^2)\) 暴力吧，时间足够的话说不定能想到正解，但没有把握，大概拿 30pts 。

dance

现在看来这个式子并不难推，推完后就是对一个多项式求单位根上的点值。
但是在直到看题解前我都完全没听说过 bluestein ，算是技不如人，只能拿 60pts 。

sequence

花了 30min 打了个 50pts 的暴力 \(O(nm)\) ，发现简直白给。
不过 100pts 确实难了不少，我觉得就算考场想到了也无法在考试时间内写对。