ix35_ 的博客

ix35_ 的博客

NOI 2020 翻盘记

posted on 2020-08-19 20:27:36 | under 未分类 |

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)$。


D1T2:

(主要是听讲题,一些具体内容不知道真不真)

设 $dp(i,j)$ 表示 $i$ 子树外边已染色,并且 $i$ 到根的第一条黑边是深度为 $j$ 的祖先到深度为 $j+1$ 的祖先(黑边指 $1$,白边指 $0$)。

那么可以写出:

$$dp(i,j)=\prod\limits_{v\in Son(i)}(dp(v,j)+dp(v,0))$$

其中需要满足 $j\to i$ 不存在一条子路径有黑边限制。

考虑线段树合并,需要做的是:

  1. 全局加( $dp(j)+dp(0)\to dp(j)$);

  2. 乘法合并(暴力线段树合并);

  3. 单点查询( $dp(0)$ 的查询);

  4. 区间赋零(不满足限制的后缀去掉)。

用维护加法和乘法标记的线段树即可实现。


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)$,那估计复杂度是线性的了。