NOI 2020 翻盘记

ix35 · 2020-08-19 20:27:36 · 个人记录

NOI 2020 翻盘记

E 类选手。

\text{Day}\ -1,0：

主要在进行社交活动和自闭活动。

自习的时候打了几个板子，但是最后啥都没用上。

\text{Day}\ 1：

开场先看了三题。

看完 T1 发现完全不会，然后看到数据范围是 n\leq 50 才醒过来。

看完 T2 感觉是容斥，T3 觉得很离谱，因为不弱于区间逆序对。

想了一下发现 T1 是矩阵快速幂，感觉复杂度是 O((4m+n)^3k\log T)，这打死也过不去，想了一下发现预处理可以 O((4m+n)^2(4m+n+k)\log T)，然后写了一发，估计是 85。

之后一档 m\leq 500 实在是想不出来啊。

之后感觉 T2 是个可做题，但是部分分不太多，就先放一下（事实：不时想 T2，但永远想不出）。

这时候大概是十点半，然后我只好去写 T3 大暴力，幸好这暴力分+A+C 挺好写的，很快就搞完了。

接下来的两个小时在测试代码和 T2 推式子间流走，但是 T2 的容斥式子怎么也不会算。

然后就 85+40+52=177 离场了。

事后发现 T1 正解和 T2 思路其实都不算很难，主要是没想到。

T1 只要把边拆点改成点拆点就可以了，T2 正解和容斥毫无关系，弄个 DP 才能做...

\text{Day}\ 2：

Day 1 比较垃圾，Day 2 却翻盘了。

对我来说感觉梦回 PKUWC 2019（或者 2020，不知道）。

刚看完题感觉心情复杂，因为一题都不会。

然后锁定 T2 是最可做的题，花了二十分钟口胡了个解法，但是过不去样例（其实就是那种三合一的做法，是错的）。

然后感觉有点慌，放下 T2 看 T1，推了半天发现数据范围 m\ge n-2，而且还有一个 m=n-1，稍微做了做感觉 n-1 还是挺容易的，顺便就搞掉了 m\ge n-1 的部分。

这个部分分的提示性确实极强，然后就可以看出 n-2 只是划分出两个 n-1，所以随便背包搞搞就可以了。

rush 了一下大概在十一点的时候写完了这题，自己出了个极限数据觉得很稳。

此时突然发现 T3 的 B 非常水，花了二十分钟做掉了。

接下来误判 T2 可能是神题，于是暂时没去做它，先写了个 T1 的 spj（吐槽：比赛不给 spj），然后找了几组大数据发现是正确的。

十二点后，感觉也没什么事，就去看 T2，做着做着忽然想到了那个 key observation，接下来全力猛冲，20 分钟惊险写完。

下午看分的时候发现 T1 不知道为啥挂了一个点，只有 95，不过 T3 有个 -1，所以总分还是 95+100+30=225，两场加上笔试总共是 502。

于是就成功翻盘 Au 了。

反思与总结

想到什么就写什么吧。

这次拿金应该说是运气极好，就实力来说肯定是不及 zjx,djq 乃至同省的 glx,gyr。

具体来说，做出 D2T2 就是很大的运气，实际上这题的难度并不大，但是由于题面较长、题目类型新颖等特点使得 AC 人数仅为不多的 20 余人，在考场上做出这道题纯属是因为做完 T1 后觉得 T3 无望，而随意推导得到的结论。

一个经验是：T1 必须做且必须首先做，其中 D1 和 D2 我分别因为误判 T2 为最简单题而浪费了半小时到一小时的时间去做无用功，但事实证明 T1 各是两天最简单的题目。

另外，通过比赛对得分和测试的时间分配大概有了点数，这次运气比较好的点是几乎没有挂分，每天大概花费了1~2h 用于测试和调试代码（包括 D2T1 手写 checker 等），目前看来在今年题目难度跨度较大，简单题较简单的情况下，我姑且认为是一种合理的时间分配。

另一点是感受到了现场赛和家里的模拟赛的巨大差异：现场比赛时周围人的键盘声对自己影响还是挺大的，想到 D2 的时候前 1h T2 写错之后不知道该干嘛，这个时候边上的人一直在码码码，心态就会比较差，这可能也需要再锻炼一下。不过现场赛的题目相对于模拟赛来说难度低一些，偏题怪题也少一些，相对比较良心。

从科技树的角度来讲，这次似乎主要是败在了 DP 这个领域上（人均会切的 D1T2 我只拿了 40 分），当然我想信这只是因为这次 NOI 没有考计数以至于没有显露出我组合计数的重灾区罢了。值得一提的是这次没有出字符串和数论（也包括线性代数等），字符串是我相对比较有自信的一个板块，数论应该和组合计数一样算是我比较菜的。

题解区（简单写下我现在会的几题）

D1T1：

考虑将长度为 w 的边拆成 w 条无权边，然后转化成无权情况。

假设 k=0，只需对带点权的邻接矩阵 M 做 T 次幂（乘法为加法，加法为取 \max）

如果 k>0，那么只需要把时间分成 k+1 段，每段分别做矩阵快速幂，然后遇到美食节的时候暴力乘一次不同的矩阵即可。

目前时间复杂度为 O((4m+n)^3k\log T)，十分惨烈。

首先，我们可以预处理 M 的二的幂次的次数，是 O((4m+n)^3\log T)，然后快速幂时使用向量乘矩阵，就是 O((4m+n)^2k\log T) 的了，总共是 O((4m+n)^2(4m+n+k)\log T)。

但是这只能得 85 分，我们只需将边拆点改成点拆点，即每个点拆成五个点，终点相同的边可以共用终点的那五个点作为公共中转结点，时间复杂度即优化到 O((5n)^2(5n+k)\log T+m)。

D2T1：

考虑 m=n-1 做法如下：

每次选择最小和最大的两个 d_i，将最小的选完，最大的选一部分凑成 k，下面给个证明：

因为 \sum\limits_{i=1}^n d_i=mk=(n-1)k，不妨设 d_1\leq \ldots\leq d_n，那么有：

所以 d_1+d_n\ge k，所以一定可以凑成 k，又 d_1< k，所以最小的食材一定可以用完（其实有个细节，如果 d_1+d_n=k，那么会转化成 m=n，但问题不大）。

接下来考虑 m\ge n，那么显然最大的一个 \ge k，所以直接将它拿走 k 即可，最后转化成 m=n-1。

接下来考虑 m=n-2，把它拆成两个 m=n-1 的子问题分别解决即可。

具体地，选出一个子集 |S|=t，使得 S 元素和为 (t-1)k，那么移项后可以知道 S 中元素减去 k 之后的和为 -k，这是个简单的背包问题，直接 DP 解决即可。

可能需要 bitset 优化，我没有使用只获得了 95 分。

D2T2：

讲题主要讲了合并的思路，但是我用的是分治的思路。

观察 1：如果一棵树每个点的左右儿子 size 的 \min 不超过 1，那么称为好树，则一旦仅有有限多个好树不在 \operatorname{grow}(\mathcal{T}) 中，那么树林 \mathcal{T} 便是几乎完备的。

证明非常简单，因为任何一棵树 T 可以由深度相等的一棵好树长出，所以只要一定深度以上的好树都能被生成，那么这个深度以上的所有树都能被生成。

观察 2：如果输入的一棵树不是好树，那么它便无用。

证明：非不能长出好树，所以它对长出好树没有任何帮助，根据观察 1，我们只关心好树能否被长出，它自然就无用了。

这告诉我们，如果只保留有效的树，那么对于每一个结点，向下递归不可能同时递归左右子树，因为至少有一个是大小不超过 1 的平凡情况。

因此递归可以考虑，设 solve(\mathcal{T}) 表示判定树林 \mathcal{T} 是否几乎完备，将其中的树分成四类：

1. 根只有左儿子；

2. 根只有右儿子；

3. 根有左右儿子且左儿子大小为 1；

4. 根有左右儿子且右儿子大小为 1；

（3.4 可能有唯一交集，但问题不大）

对于 1,2，直接递归其左/右儿子即可。

对于 3,4，对应递归相反方向（即较大的一边）的儿子即可。

如果四种情况全部几乎完备，则原树林几乎完备；特殊地，如果 \mathcal{T} 中存在单点，则直接返回几乎完备。

考虑证明上面断言的正确性：

所有可能的好树仅有上面四种，并且分别可以利用上面说的四种情况的树生成，所以只要四种树都分别几乎完备，则原树林几乎完备；反之如果有一种树不几乎完备，那么就可以构造无穷多的反例。

由于每个树最多被递归深度次，根据讲课时讲师的分析，在卡满情况下深度仅能到达 O(\sqrt n)，那估计复杂度是线性的了。