20220918 ICPC 网络赛

过了 8 个题，比上一场稍微好点了，但是被过了一片的 I 卡住了，有点可惜。

C Deltete the Tree

首先可以发现几个简单的性质：操作过程中点的度数不会增加，shrink 操作不改变其他点的度数，每次 delete 操作后其他某个点的度数至多减少 1。

那么度数 \(\le 1\) 的点只能通过 delete 操作删掉，而其他点在操作过程中总会存在某个度数为 2 的时刻，用 shrink 操作将其去掉即可，于是答案为度数 \(\le 1\) 的点的数目。

D Find the Number

先枚举 ctz 为 \(k\) ，那么末尾一定是一个 1 和 \(k\) 个 0 ，只需要考虑前面怎么填。于是问题转化为构造出一个 popcount 为 \(k-1\) 的数，且要落在区间 \([l,r]\) 中。

从高位往低位依次考虑，如果首位填 0 时能填出的最大值 \(a \ge l\) ，首位填 1 时能填出的最小值 \(b \le r\) ，由于一定有 \(a<b\) ，故 \(a,b\) 都在区间 \([l,r]\) 中，可以直接构造出解；否则 \(a\ge l,b\le r\) 至少有一者不成立，首位也至多有一种填法，填了之后再考虑后面的位即可。

F Bacteria

记 \(f(x)\) 表示最后一个数是 \(x\) 的时候的合法数列数目，那么答案就是 \(f\) 的前缀和 \(\sum_{x\le n} f(x)\) 。

考虑 \(x\) 的质因数分解形式 \(x=\prod p_i^{t_i}\) ，那么就有 \(f(x)=\prod \binom{k+t_i-1}{t_i}\) 。不难发现 \(f\) 是个积性函数，并且质数次幂处的函数值 \(f(p^c)=\binom{k+c-1}{c}\) ，用 min_25 筛进行计算即可。比赛的时候发现没带 min_25 的板子，于是和 wwj 两个人又手搓了一遍 min_25。

H Step Debugging

用栈模拟这个循环结构即可。

K Pyramad

考虑一种极端情况，打败每个敌人都需要 5000 的攻击力，那么也只需要让 \(w\) 增大到 \(\sqrt x\)，再让攻击力增加 \(\sqrt x\) 次，后面的战斗就都能获胜了。那么 \(w\) 的值不会超过 \(\sqrt x\) ，没有打败的敌人的个数不会超过 \(2\sqrt x\) 。

设 \(dp(i,j,k)\) 表示考虑了前 \(i\) 个敌人，\(w\) 现在的值是 \(j\) ，前面 \(i\) 个敌人中有 \(k\) 个人没有打败，此时攻击力的最大值。转移是 \(O(1)\) 的，讨论对下一个敌人用哪种操作即可。后面两维都是 \(O(\sqrt x)\) 的，于是时间复杂度为 \(O(nx)\) ，可以通过。