日记

以我的码力，一个晚自习改出三道 NOIP+ 还是太难了点。

能不看 std 写出来还能过就很不错了，就是实现太优秀了点

T1# Link to

赛时发现是容斥。也就发现是容斥了

设 $dp_{i,j}$ 表示前 $i$ 个家族里钦定有 $j$ 个投了自己家。转移类似背包：$dp_{i,j} = \sum_{k = 0}^{\min(j,len_i)}dp_{i - 1,j - k} \times g_k$。其中 $g_k$ 是在枚举每个家族时分别处理的，表示当前家族如果有 $k$ 个投了自己人的方案数。$len_i$ 表示家族 $i$ 的大小，

考虑如何求 $g_k$。设 $f_{i,j}$ 表示当前家族前 $i$ 个人有 $j$ 票投了自己人。那么有 $g_k = f_{len,j}$，这下只用求 $f_{i,j}$ 了。有 $f_{i,j} = \sum_{k = 0}^{\min(j,c_i)}f_{i - 1,j - k} \cdot \frac{1}{(c_i - k)!}\binom{len - j + k}{k}$。

然后容斥一下：$ans = \sum_{i = 0}^{n}(-1)^i \times dp_{m,i} \times (n - i)!$

T2# Link to

我们对每个 $a_i$ 分别考虑它所需的步数，那么题意就变成了 $a_i$ 所需的步数的最大值最小，直接开始二分。

考虑如何 chk 二分出来的 $mid$。要使 $a'$ 单调不降，$a'_i$ 必须 $a'_{i - 1}$。设当前 $a'_i = lst$。暴力枚举 $lst,lst + 1,lst + 2,\dots$。看看 $a_i$ 能不能在 $mid$ 次变成 $lst + x$。发现每次要么成功，要么 $lst + 1$，而 $lst > m$ 的时候又非法了，所以这种方法的复杂度是 $O((n + m) \times \text{检查的复杂度}$。

发现 $n \le 10^6$，所以不能双 $\log$。而我们的二分已经用了一个 $\log$，所以我们的检查复杂度必须是 $O(1)$ 的。发现 $b$ 可以建模成一个基环内向树。我们预处理每个点：所在联通块的编号；树根编号；深度；设我们要求 $s \to t$ 的距离：

• 在同一联通块
• • $t$ 在环上
    距离为 $dep_v - 1 + (rnk_t - rnk_{root_s} + len) \bmod len$。
• • $t$ 不在环上
• • • $t$ 是 $s$ 的祖先（需要奇技淫巧）
      距离为 $dep_s - dep_v$
• • • $t$ 不是 $s$ 的祖先
      return inf;
• 不在同一联通块
  return inf;

然后这题就做完了。复杂度 $O((n + m) \log m)$。

后日谈 # Link to 后日谈

其实 T2 不算太难。就是那个 $O(n + m)$ 的判断有点沟槽。

码力还得再练，不过是比之前强了。