尼玛在游记里立 flag 是吧。1 月必更新是吧。寒假作业都写不完了！！！！！
这篇四舍五入就是 1 月学习记录了。1 月剩下的杂题可能放 2 月去写。嗯也可能 2 月就退役了。退役了就没后续了这样。
先放前两天。Day3 杂题选讲没给更新后 PPT（）。Day4 题我还没写呢（目移）
因为这个 Rainy7 菜的要死，少部分题鸽了没写。菜死了菜死了怎么有这么菜的人。
精神状况极差。但应该没有拿题解发泄。语言应该很正常。
有链接的标题是提交入口。
「WC2023 Day1」题目选讲
「IOI 2022」最罕见的昆虫
这是一道交互题。
有 \(n\) 只昆虫，第 \(i\) 只昆虫的类型是 \(a_i\)，但不知类型。初始昆虫都在机器外，你可以执行如下操作：(1) 将一只机器外的昆虫放进机器 (2) 将一只机器内的昆虫取出机器 (3) 查询当前机器内类型众数的数量 。
你需要求出，\(n\) 只昆虫中，最少的类型出现了几次。
三种操作的最大次数不得超过 \(3n\)，\(2 \le n \le 2000\)，交互库不自适应。
考虑让机器内的众数始终为 \(1\)。于是以 \(n\) 的代价就知道类型的数量 \(k\)。
接下来二分答案，查询答案是否 \(\ge x\)。依次加入虫子并且维持众数为 \(x\)，然后最后判一下在机器内的数量是否为 \(xk\) 即可。如果不是说明还有类型的数量小于 \(x\)。
如何优化？二分的时候考虑去掉部分虫子。如果答案是 \(>x\)，那么就意味着全部类型的数量都 \(>x\)，那么我们直接舍去机器中的所有虫子，然后接下来的答案统一加上 \(x\) 即可。否则，就舍去机器外的所有虫子，因为对于那些众数 \(\ge x\) 的数即使去掉了外面的数，数量变成了 \(x\) 个，也不影响接下来的答案判定。
加上此优化后可以通过本题。
「CCPC2022 绵阳站 E」Hammer to Fall
有一张 \(n\) 个点，\(m\) 条边的无向图，每个点上初始有一个人。有 \(q\) 天，第 \(i\) 天会袭击点 \(b_i\)。每个人可以在图上以无限的速度行走，但是袭击时必须停留在某个不是袭击点的点上。
问 \(q\) 天结束之后，所有人行走距离之和最小是多少。
保证 \(n, m, q \le 10^5, w \le 10^9\)。
倒着考虑，不妨设 \(f(i,j)\) 表示时刻 \(i\) 的时候在点 \(j\)，需要最小代价能活到最后。于是答案为 \(\sum\limits_{i=1}^n f(0,i)\)。转移如下
\[f(i-1,b_i) = \min\limits_{(b_i,v)\in G}\{ f(i,v)+w(b_i,v) \} \]对于多次修改，考虑根号分治，每个点开个 set。度数小于 \(\sqrt{n}\) 的点，暴力修改；查询的时候再去查询大于 \(\sqrt{n}\) 的点。
复杂度 \(\mathcal{O}(q \sqrt{m \log n})\)。
「CF1707D」Partial Virtual Trees
给定以 \(1\) 为根的树，定义一个点集是虚树当且仅当点集中任意两个点的 \(\text{LCA}\) 同样在点集中。
询问有多少长为 \(k\) 的虚树序列 \(S_1, S_2,\dots, S_k\) 满足 \(S_1 = \{1, 2,\dots, n\}, S_k = \{1\}, S_{i+1} \in S_i\)。
此处 \(\in\) 表示真子集，\(n, k \le 2000\)。
先容斥一下，这样就没有真子集的要求了。问题转化成每次删除若干个点。
删除的过程，为了满足虚树的条件，每次删除一定是先删除到剩下根一颗儿子树。然后删除根，再删除儿子。于是不妨设 \(f(i,j)\) 表示以 \(i\) 为根节点，在 \(j\) 次删完的方案数。于是有：
\[f(i,j) = \sum\limits_{k=1}^j \left( \prod\limits_{v \in \text{son}_i} f(v,k) \right)\left( 1 + \sum\limits_{v \in \text{son}_v} \dfrac{f(v,j)-f(v,k)}{f(v,k)} \right) \]这大概就是先求出儿子删掉的方案数，然后讨论，根如果是在所有儿子都删后才删，还是保留一个儿子树，先删根然后再删儿子。
前缀和优化一下，就是 \(\mathcal{O}(n^2)\)。
「CCPC2020 秦皇岛站 D」Exam Results
给定 \(n\) 个区域，每个区域形如某个点的左上方 / 左下方 / 右上方 / 右下方。
求最少选择多少区域覆盖整个平面（或无解）。
保证 \(n \le 10^6\)。
分成四组。左上左下右上右下一定至少选一个。可以证明一定存在一个最优解，其中一个对角组（左上右下 / 左下右上）只需要各选一个。
于是可以枚举是那组。然后就剩下来另外两个对角的两块正方形。对于剩下那个对角组，每组先单调排序。
对于恰好选一个的对角组，我们枚举其中一组选哪个，然后剩下的先选最高 / 低的，接着贪心往下选就行了。选完后另一个对角组该选哪个也呼之欲出了。
贪心过程可以倍增优化。复杂度 \(\mathcal{O}(n \log n)\)。
「ptz camp summer 2022 Day3 F」Flower’s Land
给定一棵 \(n\) 个点的树，每个点有点权。对于每个点，求出包含它的大小恰为 \(k\) 的所有子联通块中，最大的权值和。
保证 \(n \le 4 \times 10^4,k \le 3000\)。
因为 \(k\) 比较大，所以背包合并之类的做法是肯定过不去的。
不妨先考虑假设一定包含 \(1\) 的情况。考虑对 dfs 序 DP，按着顺序 DP，先处理出前缀和后缀的信息，每个点只要合并他的前后缀信息即可。
那么基于这个思想，我们点分治。以包含分治中心为根的子连通块 dfs 序上 DP。同上。复杂度 \(\mathcal{O}(nk \log n)\)。
考虑继续优化，如果当前子连通块大小小于 \(k\) 显然可以舍弃。于是复杂度 \(\mathcal{O}(n \log (\dfrac{n}{k}))\)。
「ptz camp summer 2022 Day3 C」Counting Sequence
一个序列 \(a_1,\dots, a_m\) 是好的当且仅当：(1) \(a_i>0\) (2) \(|a_i - a_{i+1}|=1\) (3) \(\sum\limits_{i=1}^{m-1}a_i =n\)。
对于好的序列，定义权值 \(f(a) = \sum\limits_{i=1}^{m-1} [a_i > a_{i+1}]\)，求所有好的序列的 \(c^{f(a)}\) 之和。
保证 \(n \le 3\times 10^5\)。
考虑 DP。不妨设 \(f(i,j)\) 表示当前元素和为 \(i\)，上一个数为 \(j\)，的答案。转移如下：
\[f(i,j) = \begin{cases} f(i-j,j+1) & j=1 \\ f(i-j,j-1)+f(i-j,j+1) & j>1 \end{cases} \]复杂度 \(\mathcal{O}(n^2)\)。观察一下，发现 \(m\) 和权值不能同时很大。于是考虑分治。不妨设分治大小为 \(S\)。
如果 \(a_i<S\)，这个值域就很小，直接做 DP 就行了。
如果 \(a_1>S\)，则有 \(m < S\) 所以也不会存在 \(a_i \le 0\) 的情况，所以考虑没有限制的版本，然后 \(a_1=0\) 总和为 \(j\)，长度为 \(i\) 的方案和。然后枚举 \(a_1\) 和 \(m\)，结果乘上 \(c^{a_1}\) 即可。
复杂度 \(\mathcal{O}(n \sqrt{n})\)。
「JOI Open 2020 T2」黑白点
在一个环上均匀分布 \(2n\) 个点，其中黑白点各 \(n\) 个。你要画 \(n\) 条线段，形成黑白点之间的匹基于配。
请你求出求最大的相交线段对数。
保证 \(n \le 2 \times 10^5\)。
首先注意到最优情况一定不存在以下这个结构，他可以转化。
基于这个想法， 考虑构造。最优解一定形如，分别选一个黑点白点作为起点，然后顺时针按顺序连起来。这个可以通过反证法证明。
所以一条线段的交点数就是 \(\min(w_1,b_2)+\min(w_2,b_1)\)。但因为黑点白点数量相等，所以 \(\min(w_1+b_1,w_2+b_2)\)。
双指针即可。复杂度 \(\mathcal{O}(n)\)。
「ICPC2022 济南站 L」Tree Distance
给定一棵带边权的树，每次询问给出一个区间，求：
\[\min\limits_{l \le i < j \le r} \{ \text{dist}(i,j) \} \]保证 \(n \le 2 \times 10^5,1 \le w \le 10^9\)。
考虑点分治，对于一个分治中心 \(u\)，我们处理出所有区间内到 \(u\) 的最小值和次小值，然后在这个子连通块中，该区间的答案就是，最小值到 \(u\) 到次小值这个路径。注意到如果选出两个点如果在同一个子树内，这种情况一定会在继续分治下去的过程中被更优的情况覆盖。
所以每次分治的时候可以看成一个序列，求出最小值加次小值。我们可以先处理出每一段的最小值和次小值，然后扫描线求他们的和，但这样更慢了（。
考虑枚举次小值位置 \(x\)，这样最小值只需要取两侧最近的小于的数，假设有 \(z<y<x,a_y,a_z \le a_x\)，因为我们要满足 \(x\) 是次小值，所以显然 \(y\) 是更优的。
因此对于一个长度为 \(l\) 的序列，可以选出至多 \(2l\) 个关键点。直接扫描线维护就可以了。
「UNR D2T2」神隐
这是一道交互题。
有一棵 \(n\) 个点的树，询问时可以给出 \(\{1,\dots,n-1\}\) 的子集，交互库会返回，连上这些边后，图的联通情况（连通块的集合）。
你需要以任意顺序返回这棵树的所有边。
保证 \(n \le 131072,limit \ge 20\)，其中 \(limit\) 表示操作次数限制。交互库不自适应。
考虑把所有边二进制分组。分成 \(0\) 和 \(1\) 两组，两个点在一次查询内连通当且仅当他们之间的边的该位都是 \(0\) 或 \(1\)。
如果两个点在 \(\log\) 次询问都连通，这意味着这两个点是直接相连的。查询次数 \(2 \log n\)，复杂度 \(\mathcal{O}(n^2 \log n)\)。
考虑把查询边改成查询点，每个点用 \(2m\) 个位，恰好有 \(m\) 个 \(0\) 和 \(1\) 的二进制编号。然后类似上面的方法查询，操作次数就满足限制了。
不妨先确立出树的拓扑序。叶子等价于恰好有 \(m\) 次都是孤立点。所以每次找叶子删除后继续找，就可以确立拓扑序。
然后确立父亲，对于已经确立的过的点可以打个标记，这样就不用重复判断了。
复杂度 \(\mathcal{O}(n \log n)\)。
「ICPC2022 南京站 L」Proposition Composition
有一条 \(1\) 到 \(n\) 的链，接下来有 \(m\) 次加边操作。
每次加边操作结束后，你需要求出，有多少删除两条边的方式，使得图不连通。
保证 \(n,m \le 2.5 \times 10^5\)。
是一个很神奇的模型转化。
首先找出一个生成树。于是对于非树边，第 \(i\) 条设权值为 \(2^i\)。对于树边，他的权值为所有覆盖他的非树边的权值异或和。
于是可以发现，如果选出两条边的异或和为 \(0\)，那么图不连通。否则连通。
考虑用双向链表把本质相同的边串在一起。每次加入一条额外边的时候，就相当于把一些双向链表断开。
但是断开前后缀是不会变的，所以线段树维护一下前后缀，复杂度 \(\mathcal{O}(n \log n)\)。然后再维护一下每次没切的大小就可以了，可以用启发式分裂。
「PR #5」和平共处
平面上有 \(n\) 个黑点，接下来有 \(m\) 个白点依次被加入。对于一对黑白点，如果黑点在白点右上角，那么连一条边。
你需要在每个白点加入后，求出二分图匹配大小。
保证 \(n,m \le 10^5\)。
二分图匹配转成二分图独立集。所以我们只需要画一条左上到右下的折线，因为此时左上白点不可能连上右下角黑点，因此最大化右上角白点和左下角黑点数即可。
因为折线是单调的，所以整体二分的时候，某个时间的决策后，每个点只会在一侧，贡献另一侧。
「WC2023 Day2」网络流在最优化问题中的应用
「Google Code Jam 2022 Round 2」Saving the Jelly
给定平面上 \(n\) 个红点和 \(n + 1\) 个黑点，黑点编号为 \(1\) 到 \(n + 1\)。
每次，你可以选择一个红点，并同时删去它和离它最近的黑点（如果并列，你可以决定删哪一个）。
试构造一种进行 \(n\) 次操作的方案，使得剩下的黑点编号为 \(1\)，或报告无解。
保证 \(n \le 10^3\) 坐标范围 \(10^9\)。
可以发现一个红点 \(u\) 能删当且仅当 \(\text{dist}(u,v) \le \text{dist}(u,1)\)。所以依据此建出二分图。如果有解，则一定有完美匹配。
那是否有完美匹配就一定有解？考虑调整法。
对于一个完美匹配，不妨设 \(f(u)\) 表示距离点 \(u\) 的距离比匹配点到 \(u\) 的距离更小的点。然后每次跳 \(f(u)\)。
如果跳到一个 \(f(u)\) 不存在的，就把这跳的过程全部都移到 \(f(u)\) 上。如果跳到一个环，就整体移一位。调整后的完美匹配就是解。
复杂度 \(\mathcal{O}(n^2)\)。
「AGC031E」Snuke the Phantom Thief
在二维平面上，有 \(n\) 颗珠宝，第\(i\)颗珠宝在 \((x_i,y_i)\) 的位置，价值为 \(v_i\)。
现在有一个盗贼想要偷这些珠宝。现在给出 \(m\) 个限制约束偷的珠宝，约束有以下四种：
- 横坐标小于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 横坐标大于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 纵坐标小于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 纵坐标大于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
现在问你在满足这些约束的条件下，盗贼偷的珠宝的最大价值和是多少。
保证 \(n\le80,m \le 320,1 \le v_i \le 10^{15}\)，坐标范围 \(100\)。
考虑一维的情况。我们把限制转化一下。改成前 / 后 \(k-b_i\) 个珠宝的坐标要小于 \(a_i\)。而 \(k\) 可以枚举。这样我们就得到了每个珠宝的取值范围。暴力连边跑费用流即可。
二维的话差不多。就是把一维的图建两次拼起来。
「HNOI2013」切糕
有一个 \(p \times q \times r\) 的蛋糕，每个点有权值 \(v\)。对于每个纵轴需要选一个点 \(f(x,y)\)，且满足 \(|x-x'|+|y+y'|=1\) 的两对点，需要满足 \(|f(x,y)-f(x',y')| \le d\)。
求选出点的权值和最小值。
保证 \(1 \le p,q,r \le 40,0 \le d\le r, \forall v \le 1000\)。
考虑最小割，相当于每个纵轴需要切掉一条边。所以对于所有的 \((x,y)\) 都有 \((x,y,i) \rightarrow (x,y,i+1)\)，边权为 \(v_{x,y,i}\)。当然对于 \(i=r\) 的情况可以直接连到大汇点。
考虑那个限制。如果不满足限制，割了等于没割。于是连边 \((x,y,i)\rightarrow (x+1,y,k-d),(x,y,i)\rightarrow (x,y+1,k-d)\)。
求最小割即可。
「CF1630F」Making It Bipartite
图上有 \(n\) 个点，点有点权，点权互不相同，如果两个点点权成倍数关系，那么他们有边。
现在希望删去一些点，来使图变成二分图，求出最少删去多少点。
保证 \(n,a_i \le 5 \times 10^4\)。
我们将偏序关系进行大向小连边，图是二分图当且仅当不存在长度为 \(3\) 的链。所以每个点只有出度或者入度。
因为不能出现连续 \(3\) 个点。所以相当于求独立集。因为图不存在环，也就是说图是一个 DAG，那我们求最大反链即可。
由 Dilworth 定理，我们只需要求最小链覆盖即可。
「AGC029F」Construction of a tree
给定 \(n-1\) 个点集（全集为 \(\{1,2,\ldots,n\}\)），从每个集合内选两个点连边，使得最后形成一棵树。输出方案。
保证 \(n \leq 10^5\)，\(\sum |S| \leq 2 \times 10^5\)。
首先，如果 \(n-1\) 条边的图是树的条件是，所有的子集的点大小至少为 \(|S|+1\)。那么考虑充分性。
建图。左侧表示集合，右侧表示点，然后如果包含就连边。跑出来如果匹配为完美匹配，我们从那个没有匹配的点出发跑 dfs，出来的 dfs 序就是这棵树。
如果没有完美匹配。那么一定无解，因为这意味着有 \(2\) 个点是没有匹配的，那么这棵树肯定没法连通。
构造的过程，因为他跑的是增广路，每一个集合相当于都选了非匹配边的点和一个匹配边的点。我们任选一个真子点集，他都一定存在完美匹配，也就意味着他一定满足上面那个条件。得到他的充分性。
「NOI2019」序列
给定序列 \(a_1,\dots,a_n\) 和 \(b_1,\dots,b_n\)。你需要对两个序列分别指定恰好 \(K\) 个下标，使得至少有 \(L\) 个下标在两个序列中都被指定。
最大化指定的 \(2K\) 个下标对应的元素总和。
保证 \(n,K,L \le 2 \times 10^5\)，值域 \([1,10^9]\)，\(5\) 组数据。
考虑费用流。首先有 \(s \rightarrow a_i\) 流量为 \(1\)（这里表示向 \(a\) 序列第 \(i\) 个连边，下面同理），费用为 \(a_i\) 的权值；\(b_i \rightarrow t\) 流量为 \(1\)，费用为 \(b_i\) 的权值。
因为下标不相等最多只能有 \(K-L\) 个，于是连边 \(a_i \rightarrow c \rightarrow d \rightarrow b_j\)。其中 \(c \rightarrow d\) 流量上限为 \(K-L\)，其他的为 \(1\)，费用均为 \(0\)。
对于剩余的就默认选一致下标的。 那么有 \(a_i \rightarrow b_i\) 流量为 \(1\) 费用为 \(0\)。
这张图的流量为 \(K\) 的最大费用情况就是答案。当然可以多连一条边表示上限为 \(K\)。然后直接跑。
考虑模拟费用流。
逐一加流量。如果 \(c \rightarrow d\) 没满就优先选这条边。这也就是每次在两边各选一个最大值，然后流 \(c \rightarrow d\)。当然如果刚好下标相等就不流这条。
这边满流后，我们可以选 \(a_i + b_i\) 最大的然后流。或者单选一个没选过的 \(a\) 或者 \(b\)，然后选另一个下标相同的 \(b\) 或 \(a\)，然后这里 \(c \rightarrow d\) 退一流量。
所以我们贪心过程中不需要保证 \(c \rightarrow d\) 是满的，如果出现一对下标相同的情况，可以通过暴力选剩下的最大值让他流满。
用堆维护即可。
「URAL1833」Hope of Rowing
有 \(n\) 个变量 \(x_i \in [0,1]\) 和 \(m\) 个形如 \(x_{u_i} + x_{v_i} \ge 1 (u_i \not= v_i)\) 的约束。
最小化 \(\sum\limits_{i=1}^n x_i\) 并输出方案。
保证 \(n \le 500,m \le 10^5\)。
有一个结论，每个点取值只有 \(0,\frac{1}{2},1\) 三种取值。首先他显然不劣，那么如何证明他不优。假设存在两个点 \(u,v\)，他们之间没有约束，但他们各自分别有其他约束 \(u_i,v_j\)。假设 \(u,v > \frac{1}{2},u_i,v_j < \frac{1}{2}\)。发现这情况显然可调整成 \(u,v = 1,u_i,v_j =0\)，并且约束情况没变；如果 \(u,v < \frac{1}{2},u_i,v_j > \frac{1}{2}\) 也可以调整。
所以把这每个点拆成两个点表示权值 \(0/1\)，对于一个约束 \((u,v)\) 连边 \((u_1,v_2),(u_2,v_1)\)。跑二分图，最后点 \(x\) 的权值就是在匹配中的点取平均值。
「UOJ455」雪灾与外卖
数轴上有 \(n\) 个老鼠和 \(m\) 个洞，第 \(i\) 个洞最多容纳 \(c_i\) 只老鼠。
求让所有老鼠都进洞的最小代价。每只老鼠每移动 \(1\) 的距离会产生 \(1\) 的代价，而第 \(i\) 个洞每容纳一只老鼠会产生 \(w_i\) 的代价。
保证 \(n,m \le 10^5,c_i,w_i \le 10^9\)，坐标范围 \(10^9\)。
建图大概就是建一条链，双向的，流量为 \(+\infty\) 费用为 \(1\)。表示走一格的代价。\(s\) 连向有老鼠的点，所有点连向 \(t\)，流量上限为 \(c_i\)，费用为 \(w_i\)。
洞和老鼠维护堆。里面存代价。从左往右扫就可以知道每个点对应的最小值。
对于一只老鼠，找出一个最小代价的洞钻进去，代价是 \(d+c\)。因为我们是在模拟流量一个一个加的过程，所以如果有退流，那一定是右边的抢占了这老鼠的位置。所以在右边的洞塞一个反悔代价，减去之前花费的同时再减去老鼠的位置 \(-(d+w_i)-d\)。
如果是洞，选择一个老鼠。代价为 \(d+c+w_i\)。反悔同理，选择右边那只，\(-(d+c)-y\)。但因为洞这条边退流后不一定要继续留这条边，所以反悔的时候那个老鼠可以换个洞，老鼠里再塞个 \(-d-c\)。
为了减少重复的代价，可以再记录一个次数值。这样堆内的元素数量就有保证了。
「CF1307G」Cow and Exercise
给出一个 \(n\) 个点 \(m\) 条边的有向图，每条边有边权 \(w_i\)。
有 \(Q\) 次询问，每次询问给出一个 \(x\)。你可以把一条边修改成 \(w_i+a_i\)（ \(a_i\) 不一定是整数），不过需要保证 \(a_i \ge 0\) 且 \(\sum a_i<x\)。
你要通过修改边权使得从 \(1\) 到 \(n\) 的最短路径尽可能长，每次询问之间独立。
数据保证至少存在一条从 \(1\) 到 \(n\) 的路径，无重边自环。
首先我们会想到，每次修改 \(1\) 到 \(n\) 的每组路径的必经之路一定最优。也就是修改最小割。
于是把经过同一个最小割的路径归为一个路径集。
因为要使最短路径最长，我们对于一个 \(x\) ，修改路径集中最小的 \(k\) 条边，并且使他们更改后最短路径一样长即可。假设他们都是 \(L\) ，如果此时又其他路径长度小于 \(L\) ，那肯定是选择修改那些路径集。
考虑 EK 算法，因为每次跑完最短路只会找到一个增广路。
建图时每条边流量为 \(1\) ，费用为 \(w_i\) 。当增光 \(k\) 次后就有流量 \(k\) ，因为这 \(k\) 个路径必然没有交点，就是有 \(k\) 个路径集的最短路。
所以可以把每次增广的结果流量和费用存下来，每组的结果为 \(\dfrac{cost_j+x}{flow_j}\) 。
我们发现这个函数是凸的。假设最优的是 \(k\) ，如果 \(j>k\) 意味着增广了更长的路径，那么结果必然更小。 如果 \(j<k\) ，修改的 \(j\) 个路径会小于 \(k-j\) 个路径的最短路。
于是有答案为 \(\min\{\dfrac{cost_j+x}{flow_j}\}\) 。
「WC2023 Day2」欧洲信息学竞赛题目选讲
「PO-Final 2022」三角形演讲
有 \(n\) 个人，每个人有一个权值 \(a_i\)。将他们分成 \(3\) 组，使得第 \(i\) 组的 \(\max \{ a_j \}\) 均大于第 \(i+1\) 组的人数。若 \(i=3\) 则下一组为 \(1\)。
需要判断是否有解。若有解则构造。
满足 \(n \le 5 \times 10^5, 1 \le a_i \le n\)。
首先显然一定存在一组的最大值是全局最大值。不妨设他为第一组，令 \(b_i\) 表示第 \(i\) 组最大值，\(s_i\) 表示大小。
于是接着考虑枚举第二组的最大值，然后对于第三组，我们贪心的希望他的最大值尽量小。
那么我们把 \(a_i\) 排序，然后从小到大一个一个塞进第三组，直到第三组 \(s_3=b_2\)。接着转身去塞第二组，在保持第二组最大值不变的情况下，一个一个塞数直到 \(s_2=b_1\)。然后再把剩下的全部扔第一组。
如果塞不满，那就是不合法。
「EGOI 2022」玩具设计
见 EGOI2022 day2 校内 vp。？？我原来 Day2 没打吗（什么那天请假了那没事了。
「BOI 2022」信息传递
这是一道通信题。
给定一个数 \(x \in [1,n]\)。每次只能发送 \(0\) 或 \(1\)，但
收到宇宙射线影响信息传递可能有误。每次发送信息后，会得知实际被收到的信息，保证连续两次发送中至少有一次是正确的。接收方需要根据发送的信息，得知 \(x\) 的具体数值。
保证 \(3 \le n \le 10^9,w_{\max}=100\)。其中 \(w\) 表示发送信息的次数限制。
记一个乱搞做法。
首先有一个自然的想法，先不断的发送 \(1\)，如果出现一次被欺骗（即对方接受到一个 \(0\)），那么下一次就传输 \(x\) 的二进制的第一位。然后再不断发送 \(1\)，以此类推。
但这样容易被自适应交互器干烂，于是考虑对于 \(x\) 的每一位都随机一个双方都知道的密码串，然后将不断发送 \(1\) 改成不断发送该位的密码串，如果密码串有一位发送错误，下一位就传输 \(x\) 的对应位置。
但这样对于出错率低的情况效率很低，于是再设一个上界，如果到达某上界依然是正确传输，那么下一位就传 \(x\) 的对应位置。
正经做法。
首先先把 \(x\) 传一遍，得到了一个错误的串 \(x'\)。我们把 \(x'\) 中错误的位找出来，然后我们把这些位再传过去，又得到了这些位置的错误串。再去传这两个错误的位置，再传下去。直到 \(n=3\)。
分析一下，首先 \(x\) 有 \(2^{30}\) 种可能，但因为不存在连续的两个错误，所以对于 \(x'\) 错误的位置最多 \(15\) 个。这相当于每次需要传的错误位置个数都会除以 \(2\)。最终可以满足条件。
然后考虑 \(n=3\) 的情况。我手动列举了一遍，如果一个数用 \(3\) 个位置表示是表示不出来的。于是考虑用 \(4\) 个数表示。
对于每个数找出一个串，如果传输过来的数和这个串至少有两位匹配，那么我们就可以确定他可能代表的数。
其中，\(1:0000,2:0110,3:1111\)。可以发现，每次传来一个串都可以排除一个数，所以我们只要做两边就可以知道我们要传的是哪个数。
「RMI 2018」登山者
Alice 和 Bob 要爬的山可以用一列折线表示，最左端和最右端的高度均为 \(0\)，中间端点的高度均为正整数。
Alice 从山的左端， Bob 从山的右端开始爬山，且保证在任何时刻，必须处于相同的高度。每次改变爬山方向（向上 / 向下）时的高度分别为 \(h_2, h_3, \dots, h_p\)，则爬山的体力值为 \(|h_2 - h_1| + |h_3 - h_2| + \dots + |h_p - h_{p-1}|\)。
求 Alice 和 Bob 为了相遇所需的最小体力值。
保证 \(3 \le n \le 5000,1 \le h_i \le 10^6\)。
首先有一个性质。我们只需要记录其中一个人在端点的，另一个人在端点或者折线的情况。因为如果两个人都在折线上，那么他们接下来一定要走上或走下，直到一个人走到端点。
于是我们记录状态 \((x,y)\) 表示，一个人在第 \(x\) 个人端点，另一个人在第 \(y\) 个折线（若两个人都在端点，一个端点可以取他所在的一条折线上）。
于是对于一个状态 \((x,y)\)，都只有向上，向下两种走法的选择，根据这个连边。得到一个点和边均为 \(\mathcal{O}(n^2)\) 的图。
跑 dijkstra，然后对于所有相遇的状态取 \(\min\)。复杂度 \(\mathcal{O}(n^2 \log (n^2))\)。
「EJOI 2022」寻找树根
这是一个交互题。
给定一棵树，保证不是一条链。每次你可以询问一个点集的 \(\operatorname{LCA}\) 的是否在该集合内。需要找出树的根。
保证 \(n \le 500\)，询问次数 \(k \le 9\)。
首先把度数为 \(1\) 的点叫做叶子节点。剩余的称作中间点。
如果对于一个点 \(r\)，对于所有 \(\{ r,v \}(v\in[1,n])\) 的回答都是 Yes，那么 \(r\) 可以为候选根节点。可以发现，存在一些情况 \(r\) 不只一个，当且仅当根节点是叶子节点时，他和他所连接的唯一那个点均为候选根节点。
另外还可以发现，不是根的候选根节点一定是中间点。因为如果存在多个候选根节点，那么根一定为叶子节点，叶子节点所连的出的那条链下的第一个度数 \(>2\) 的点 \(u\)，他的两个子树内任意两个叶子节点的集合的 \(\text{LCA} = u\)，询问一定为 No。
那我们首先可以选出所有叶子节点做一次询问，他们的 \(\text{LCA}\) 就是根节点，所以如果该询问为 Yes，则根是叶子节点，由于上面的那个性质，意味着只有一个叶子节点是候选根节点，所以可以二分找出那个唯一点；如果询问为 No，那么只有一个候选根节点，我们对所有中间点进行二分，就可以找到那个点。次数为 \(1+9=10\) 次。
考虑舍弃第一部直接开始找，对于所有点按照度数从小到大排序，然后再二分。二分一个 \(k\)，查询前 \(k\) 个的集合。
可以发现，如果是第一种情况，那么最后二分的前 \(k\) 个均为叶子节点；否则就是全部叶子节点和部分中间节点，但因为这种情况叶子节点中不存在候选根节点，所以不影响。
「CEOI 2022」奖品
这是一个交互题。
给出两棵树，均有 \(n\) 个节点，每棵树边都边权，但是初始你并不知道。
给定 \(k\)，初始可以选择一个大小为 \(k\) 的点集 \(S\)，接着你可以询问 \(q\) 次 \((a,b)\)，且 \(a,b \in S\)，交互器回答 \((d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b))\)，其中 \(d_t(x,y)\) 表示在 \(t\) 号树上节点 \(x\) 和节点 \(y\) 的距离，\(l_t\) 表示 \(t\) 号树上 \(a\) 和 \(b\) 的最近公共祖先。
提问结束后，交互器会给你 \(t\) 个询问 \((u,v)\)，且满足 \(u,v \in S\)，你需要回答 \((d_1(u,v),d_2(u,v))\)。
保证 \(2 \le k \le 10^5,1 \le t \le \min(k^2,10^5)\)。对于
Subtask 2满足 \(q=2k-2\)，剩余均满足 \(q=k-1\)。
注意到 \(q=k-1\)。
不妨设 \(d(x)\) 表示点 \(x\) 到根节点的距离，那么一次询问，就可以得到一个 \(d(x)-d(y)=w\) 的方程。然后就有 \(2k-2\) 个方程，未知数有 \(2k-1\) 个未知数。
但如何取点才能保证集合中的所有节点和他们的 \(\text{LCA}\) 都出现在方程中？
选第一棵树的前序遍历的前 \(k\) 个点。这样第一棵树选出来的 \(\text{LCA}\) 一定都在方程中。于是考虑第二课树怎么提问。
将上述编号按照前序遍历一次排序 \(s_1,\dots,s_k\)，然后依次提问 \((s_i,s_{i+1})\)。
接下来，对于每次交互器的询问，求出他们 \(\text{LCA}=r\)，答案即为 \(d(u)+d(v)-2d(r)\)。
「OIE 2022」最大公约数
这是一道交互题。
需要猜的数为 \(x,y\)，每次你可以询问 \(a,b\)，交互器会给出 \(\gcd(|x-a|,|y-b|)\)，约定 \(\gcd(0,0)=0\)。
保证 \(1 \le x,y \le 10^{18},-2 \times 10^{18} \le a,b \le 2 \times 10^{18}\)。最多可以询问 \(125\) 次。
首先有 \(\log_2 10^{18} = 60\)，所以这个答案肯定是 \(\log\) 级别。
我们将 \(x,y\) 写为二进制。可以先询问 \((0,0),(0,1),(1,0),(1,1)\)，然后就确定了最低位，也就是确定了奇偶性。
对于下一位，可以先把上一位减去。具体而言 \((0+a_0,0+b_0),(0+a_0,2+b_0),(2+a_0,0+b_0),(2+a_0,2+b_0)\)。然后一位一位算就能算出来了。\(4 \log = 240\)，过不去。
不妨设 \((1,0)\) 的时候是偶数，那进一步判断他是不是 \(4\) 的倍数。如果不是，下一位就舍弃两个 \((1,0),(3,2)\) 就不用询问了，因为一定不是 \(4\) 的倍数。反之如果是，就是另外两个不用。
所以我们每次找出上一位偶数的那个，通过判断他是不是 \(2^{x+1}\) 的倍数，来舍弃两个选择。这样除了第一位都只要询问 \(2\) 次。次数 \(2\log+2\)。
标签：10,le,WC,一个,可以,Day1,2023,如果,节点 From： https://www.cnblogs.com/Rainy7/p/wc-2023-01-note.html