NOIP2024模拟测试赛（一）

比赛链接

A. tree

当 \(\forall v_i \le 1\) 时，可以直接从下往上贪心选，一个以 \(u\) 为根的子树中联通块如果权值和 \(>k\) 那么肯定能删到恰好 \(k\)。否则的话就把这个联通块并到 \(u\) 父亲上再看就行。

当 \(\forall v_i \le 2\) 时，直接贪心可能有问题，大于 \(k\) 的权值和可能不能删掉一些点凑成 \(k\)，因为 \(2\) 的存在有可能使 \(k+1\) 直接变成 \(k-1\)。我们肯定想要一个 \(1\) 的权值，那就找到一个 \(1\) 是从叶子删点删最少的 \(2\) 后可以删到这个 \(1\)，记最少 \(2\) 的个数是 \(minx\)，那么若当前联通块的和 \(sum-k \ge minx\)，就一定存在一种删点方式使得合法。（可以先删掉这个 \(1\) 下面的 \(minx\) 个 \(2\)，然后删其他的点直到变成 \(k\) 或 \(k+1\)，是 \(k+1\) 的话再把这个点删了就行）否则若 \(sum-k < minx\)，那么肯定不能在 \(sum\ge k\) 的情况下遇到一个 \(1\)，此时若 \(sum \equiv k \pmod{2}\) 才合法。

直接 dp 记录 \(sum_u,minx_u,ans_u\) 按上面的方法贪心即可，一个联通块合法的时候要清空 \(sum,minx\)。

B. subset

设 \(kx+b=t \sube S\)，那么有 \(x = \dfrac{t-b}{k}\)，即要求

\(t\ge b \land t \equiv b \pmod{k} \land t \sube S\)

• \(\Theta(T\sqrt{S\log S})\)

考虑阈值分治。

考虑当 \(k \le B\) 时，可以把 \(S\) 中的每个是 \(1\) 的位置 \(2^i\) 看成一个物品，做模 \(k\) 意义下的 \(01\) 背包。设 \(f_{i,j}\) 为 \(0 \sim i\) 位的物品和模 \(k\) 余 \(j\) 的最小值。由于还要满足 \(t \ge b\)，那么枚举 \(t\) 和 \(b\) 的 lcp 的下一位，即 \(t\) 第一个大于 \(b\) 的位置 \(p\)，设第 \(p \sim 31\) 位的和是 \(sum\)，那么此时的答案就是 \(f_{p-1,k-sum}\)。复杂度 \(\Theta(B\log S)\)。

当 \(k > B\) 时，可以暴力枚举 \(x\) 做到 \(\Theta(\dfrac{S}{B})\) 的复杂度。

取 \(B=\sqrt{\frac{S}{\log S}}\) 复杂度就是 \(\Theta(T\sqrt{S \log S})\)。

• \(\Theta(T\sqrt{S})\)

考虑 meet in the middle。

设 \(t = v_1 \times 2^{15} + v_2\)

考虑枚举高 \(15\) 位的值 \(v_1\)，那么此时可知 \(v_2\) 的下界和模 \(k\) 的值，即 \(v_2 \ge b - v_1 \times 2^{15} \land v_2 \equiv k - v_1 \times 2^{15} \pmod{k}\)。

从小到大枚举 \(v_1\)，则 \(v_2\) 的下界会不断变大，此时用个双指针来加入满足下界且属于 \(S\) 的 \(v_2\)，并且用桶 \(f_i\) 表示模 \(k\) 余 \(i\) 的 \(v_2\) 最小值。对于每个合法的 \(v_1 \sube S\)，去找看看桶里面是否有 \(v_2\) 即可。

复杂度 \(\Theta(T \sqrt{S})\)

C. ee

考虑怎么判断是否有四元环，假设是 \((a,b,c,d)\)，那么就是存在两个点 \((u,v)\) 有两个以上公共邻居。

假设没有修改，那么直接枚举一个点 \(i\)，然后枚举它的两个邻居 \(u,v\)，那么把 \(cnt_{u,v} \leftarrow cnt_{u,v} +1\)，表示 \((u,v)\) 多了一个 \(i\) 的公共邻居。若存在 \(cnt_{u,v} > 1\) 就有四元环了。复杂度是 \(\Theta(n^2)\)，因为 \(cnt_{u,v} \le 1\)，不然可以直接判断出来了。

考虑假如修改，由于修改只涉及到 \(\Theta(q)\) 条边，那么把这些边都先删了，其他边不会变，先判断一次，并记录 \(cnt_{u,v}\)。再考虑加入或删除一条边，加入 \(E(u,v)\) 时，枚举 \(u\) 的每个邻居 \(i\)，把 \(cnt_{i,v} \leftarrow cnt_{i,v}+1\)，\(v\) 的每个邻居同理。注意此时不能 \(>1\) 就退出，因为有删边操作。用个 \(ans\) 记录 \(cnt_{i,j}>1\) 的 \((i,j)\) 数量即可，若 \(ans>0\) 就存在。每次更新是 \(\Theta(n)\) 的，所以总复杂度 \(\Theta(n(n+q))\)。