NOI 2020 翻盘记

## 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$，那么有： $$(n-1)(d_1+d_n)\ge(n-1)d_1+\sum\limits_{i=2}^n d_i\ge \sum\limits_{i=1}^n d_i=(n-1)k$$ 所以 $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)$，那估计复杂度是线性的了。