2023NOIP A层联测31 总结

题目

T1 暴力操作

\(n\leq 5\times 10^5,m\leq 5\times 10^5\)

赛时思路

可以二分一个中位数 \(mid\)，将较小的 \(\lceil \frac{n}{2} \rceil\) 个数拿出来，将这 \(\lceil \frac{n}{2} \rceil\) 个数变小到 \(mid\) 以内的花费就好了。

对于每一个 \(c_i\) 都可以通过它的因子得来，即 \(c_{i\times j}=\min(c_i+c_j,c_{i\times j})\)。

\(\ln m\) 预处理出 \(m\) 以内每个数的因子，然后求 \(c_i\)。最后再求一个 \(i\) 超过 \(m\) 的 \(c_i\) 最小，将其花费存在 \(c_{m+1}\) 中。

接着可以 \(c_i=\min(c_j)\ (i \leq j \leq n)\)。

赛后思路

同上。

T2 异或连通

\(n,m,q\leq 10^5\) \(x,k \leq 2^{30}\)

赛时思路

一个基于 \(x\leq 2^{10}\) 次方的暴力思路。

每次输入 \(x\) 以后，暴力的使用生成树算法求联通块数量并记忆化，可以拿到 80pts 的高分。不过需要由于数据规模顶着 \(O(mx)\) 的极限，所以需要比较精湛的卡常技巧。

赛后思路

考虑和 Tire 树结合，那么对于每一个 \(c_i\) 可以求出在 Tire 树上至多的 \(\log c_i\) 个点，使得该点深度最小且子树内所有的点的值异或上 \(c_i\) 均小于 \(K\)。

使用类似于线段树分治的做法，在遍历一个点的子树时，将这个点所包含的边加入图，同时按秩并查集，使得 find_root 操作在 \(\log n\) 级别，每一个 Tire 树上的点都可以求出一个答案，当我们遍历到 \(w\) 在 Tire 树上的点时，求答案就好。

T3 诡异键盘

赛时思路

对于 \(K=1\) 的情况，暴力模拟一个前缀的转移，类似于 01bfs 的手法暴力即可。

赛后思路

还在补。

T4 民主投票

赛时思路

暴力枚举那个点时要被投票的，将其从树上断开，用下文方法求最小投票内不能小于 \(siz-1\)。

对于二叉树和链的情况，加特判即可。

赛后思路

原博客链接：2023NOIP A层联测31 T4 民主投票 - 彬彬冰激凌 - 博客园 (cnblogs.com)

首先可以设 \(s\) 每个人最多获得的票数，一开始所有点都把自己的票投给自己父亲。

如果一个点的票数超过 \(s\) 了，那么这个点肯定要把票分给他的父亲。

设 \(f_{u,s}\) 为 \(u\) 点在最多获得 \(s\) 票的情况下要向父亲分的票数（不包括一开始投的）。

如果 \(f_{1,s}\) 大于 \(0\) 表示无法每个点至多获得 \(s\)，反之则可以。

可以二分求这个最小的 \(s\) 值。

点 \(u\) 获得的最多票数是 \(siz_u-1\) 票。

如果 \(siz_u-1>s\) 那么 \(u\) 肯定可以获胜。如果 \(siz_u-1<s\) 那么证明 \(f_{u,s}=0\)，把 \(u\) 子树脱离原树不造成影响，即 \(u\) 子树内所以点投 \(u\) 无法影响最小值 \(s\)，所以 \(siz_u-1<s\) 时，\(u\) 肯定无法获胜。

对于 \(siz_u-1=s\) 而言，\(f_{u,s}=1/0\)。

此时求 \(f_{1,s-1}\)，\(f_{1,s-1}\) 必然大于 \(0\)。

如果 \(f_{1,s-1}=1\)，则这一票肯定是通过某个 \(siz_u-1=s\) 的点传上来，由于点 \(u\) 在被取的情况下不会向上传票，所以点 \(u\) 可以获胜，即去掉 \(u\) 的后代后，\(f_{1,s-1}=0\)。

如果 \(f_{1,s-1}>1\)，肯定是有多个上文分析的点会传票到根，\(u\) 节点不能获胜。