UER8的那天，uoj管理员群里突然出现一个神圣跳蚤君主国国王！

vfk：我证明了UER 8A的lower bound是1.206n，有没有人给一个match的upper bound啊？

众人：[惊呆]

然后我跑到vfk的寝室，看vfk表演了怎么得出这个lower bound和对应的upper bound。

whx：Orz 在uoj blog里写下这个做法吧！

vfk：太忙了，咕咕咕。

于是只有辣鸡whx来复读一遍了。

Lower bound

首先，我们考虑单轮交互的情况，也就是Bob先发一个信息$x$给Alice，然后Alice发一个信息$y$给Bob。

假设$|x| \leq m, |y| \leq m$，由于$x$只有$2^m$种，那么至少有$\frac{\binom{2n}{n}}{2^m}$个下标集合$I$会导致相同的$x$。

那么Alice要发给Bob这些集合的并，但是Alice发过去的集合最多覆盖$\binom{m}{n}$个集合。

为了解$\frac{\binom{2n}{n}}{2^m} \leq \binom{m}{n}$，我们设$m = n/r$，那么$\binom{m}{n} =\binom{m}{rm}=2^{m(H(r) + o(1))} $，其中$H(p) =plog_2\frac{1}{p}+(1-p)\log_2\frac{1}{1 - p}$是大家熟悉的信息熵。

所以$\frac{2^{2mr}}{2^m \sqrt{2mr}} \leq 2^{mH(r)}$，两边同时取$log$得：$2mr - log(mr) \leq m(H(r) + 1)$

因为我们只关心乘在$n$上的系数，不妨舍去log项，从而得到$2r \leq H(r) + 1$, 如果召唤mathematica，我们很快就知道$m = n / r =1.206n$

这个Bound同样适用于多轮的情况，不严谨的说，因为在多轮交互中，Alice发给Bob的信息只能依赖于Bob之前发过来的信息，以及Alice自己的串，从而在给出了Bob之前发来的串之后，对Bob手里的集合$I$信息量为0。（有人有兴趣用conditional mutual information严谨的证一下吗）所以最后Alice发给Bob的还是至少是$\frac{\binom{2n}{n}}{2^m}$个集合的并。

另外，这个Bound也一样适用于高概率正确的随机化算法，因为它要在趋近于1的比例的下标集合$I$上合法，就必须

Upper bound

Shannon在证明存在一种编码方式可以达到信道容量的时候，所用的方法就是给每个元素随机编码，我们也用一样的思路。

Bob要发给Alice的其实是$I$的一个超集，所以我们现在的问题其实是，我们要从$N=\binom{2n}{m} = \binom{2mr}{m} = 2^{2mr\left(H\left(\frac{1}{2r}\right)+o(1)\right)}$个大小为$m$的集合中，选出不超过$M=2^m$个，使得每个可能的下标集合$I$都是某个集合的子集，我们不妨随机选这$2^m$个集合。

因为一共有$K=\binom{n}{m-n} = \binom{mr}{m(1-r)}=2^{rm(H(\frac{1-r}{r})+o(1))}$个集合覆盖了$I$，其中一个集合都没被选的概率就是： $$ p=\frac{\binom{N-K}{M}}{\binom{N}{M}}=\frac{(N-K)^{\underline M}}{N^{\underline M}}\leq\left(1-\frac{K}N{}\right)^M=(1-2^{rm(H(\frac{1-r}{r})-2H(\frac{1}{2r})+o(1))})^{2^m} $$ 我们做一些简单的计算：

\begin{equation}\begin{split} &H\left(\frac{1-r}{r}\right)-2H\left(\frac{1}{2r}\right)\\ &= \frac{1-r}{r} log\left(\frac{r}{1-r}\right)+\left(1-\frac{1-r}{r}\right)log\left(\frac{1}{1-\frac{1-r}{r}}\right)-2\left(\frac{1}{2r}log\left(\frac{1}{2r}\right)+\left(1-\frac{1}{2r}\right)log\left(\frac{1}{1-\frac{1}{2r}}\right)\right) \\ &=\frac{1-r}{r}(log(r) - log(1-r))+\left(1-\frac{1-r}{r}\right)(log(r) -log(2r-1))+\frac{1}{r}(log(r)+1)-\left(2+\frac{1}{r}\right)(log(r)+1-log(2r-1)) \\ &=\left(\frac{1-r}{r}+1-\frac{1-r}{r}+\frac{1}{r}-2-\frac{1}{r}\right)log(r)-\frac{1-r}{r}log(1-r)+\left( \frac{1-r}{r}-1 +2-\frac{1}{r}\right)log(2r-1)+\frac{1}{r}-2-\frac{1}{r} \\ &=log\left(\frac{1}{r}\right)+\frac{1-r}{r}log(1-r)-2 \\ &=\frac{H(r)-2r}{r} \end{split}\end{equation}

也就有 $$ p \leq (1-2^{m(H(r)-2r)})^{2^m} $$ 因为$H(r)+1-2r\rightarrow 0$，所以$H(r)-2r<0$, $2^{m(H(r)-2r)}\rightarrow 0$，从而 $$ p \leq (1-2^{m(H(r)-2r)})^{2^m} =(1-2^{m(H(r)-2r)})^{2^{m(2r-H(r))+(H(r)-2r+1)m}}=e^{-2^{(H(r)+1-2r)m}} $$ 我们取$H(r)+1-2r> \varepsilon$，那么在$m \rightarrow \infty$的时候，$p \rightarrow 0$，不难发现$\binom{2n}{n}p\rightarrow 0$，我们随机选的集合大概率能覆盖所有这样的$I$。结论就是，我们可以任意逼近我们之前推出的lower bound。

Remark

这道题如果优化的目标，变成二者所发信息的和，那么就是一个典型的”通信复杂度“的问题了，但是那样的话，我们的方案$2.412n$还不如直接把整个串发给Bob。事实上直接把整个串发给Bob也最优的复杂度了，因为Bob可以计算出两个串对应的集合有没有交，也就是Set disjointness上。

同时这个方法因为需要uniform的随机取$2^m$个大小为$m$的集合，不能直接用于这道题。有没有同学试一试不严格的随机方法能不能通过？

紧张的二招结束了，难熬的军训过去了，一转眼已经到了开学的季节，也是一年一度uoj传(diu)承(guo)的季节了呢。

我们（WuHongxun，Scape，WrongAnswer），在过去的一年里负(gu)责(gu)了uoj的题目和比赛。这一年里，在叉姐ftiasch、毛爷爷matthew99 、吉老师jiry_2 等等的大力帮助，以及正在读这篇post的你的支持之下，办出了一些质量让人满意的比赛，其中大部分题目都是我愿意推荐给别人的好题。

但是与此同时，在这一年里，一方面因为我们能(tai)力(ge)有(le)限，导致比赛场次和频率非常少。比如UNR差点变成Uoj No Round。另外一方面我们不(tai)够(lan)勤(le)奋，导致比较枯燥的传题任务有许多没有完成。非常惭愧，今天中午在宿舍遇到vfk的时候，vfk说还以为uoj快要凉了，我们没有称职地完成任务，十分对不起大家。在新的一届里，我们吸取了之前的教训。将会分设传题组和比赛组，分别负责比赛和传题的工作。每组会由三名活跃的OIer/ACMer构成，将会按照新任管理员的意愿进行分组。希望新的改变可以带来新的生机与活力。

下面就宣布新的管理员队伍。

出题组：AwD，whzzt，ztr。

传题组：nike0good，diamond_duke，LazyJazz。

会由朱老大whzzt来负责联络和给大家分锅。

再说一点题外话吧。

虽然很长一段时间，我都没有把自己当做一个“典型”的OIer。但当进入了大学，就突然发现自己被打上了OIer的标签，面对问题时的思维方式和习惯都带上了OI的烙印。再回头看去，才发现OI成为了自己重要的一部分，而OI也不断塑造着一批批的OIer。希望在这个进程中，新的管理员能让uoj成为一盏明灯。对新OIer而言，能照亮OI里最有趣的那些部分，对老OIer而言，就像家中的灯光一样，回首就能感到它的温暖。

愿UOJ和OI的明天更加光明，祝新的管理员们一切顺利！

白鸽

from matthew99， 题解 by matthew99

出题经历——为什么这会是A题？

这个题本来idea几乎就一个——射线法的应用，但是我逐渐发现不管怎么出题，都没区分掉依赖于角度的做法（比如说，如果换成小范围的哈密顿路径，实际上对于每个点可能的角度个数也是$O(n)$的，当时这个题说的时候差不多是这个版本然后我也没意识到不用射线法也能做，所以感觉能做A）。但是这个题A题的位置已经占了，到后面为了保证不成为导致这场比赛鸽掉的千古罪人，也因为deadline临近没时间重新再想一个题了，只好抱着“孩子再丑也要生下来”的心态把这个题出完了。当然，这个题出A题，我也不喜欢（其实这个题变成这个样子我也不喜欢了），要是准备更充分应该把这个题和昨天B交换的。如果你们是抱着做好题的心态来做UNR却被这个题翔了一脸我只能真心说声抱歉了。

如果你们有兴趣读完这篇题解，那么你会发现我最后区分掉（或者一定程度上区分掉，取决于是否还有不用射线法的做法存在）直接用角度的做法的方法就是利用费用流的代价只有0或者1的性质，而当出题走到这一步的时候，除了出一个看起来玄学的复杂度然，写一个长得荒唐的高效费用流并使用非常复杂的方法证明一个丑陋的复杂度下界，没有任何别的路可走了。

总之，在出题方面这个题的教训还是很多的，首先最显然的是一定要趁早，如果比赛临近了还在准备题目再发下出各种问题，那么很可能要么只能鸽（显然，UNR不能再往后拖任何一天），要么最后出出来的题变成怪胎。其次就是，我出题的习惯一般是想到一个题目再想做法，而不是想到一个做法再去强行凑题。这个题刚开始还是先想到的题，而不是先想到的做法，但是我后面发现我非常喜欢这个射线法的思路（其实这个思路非常显然，只是自己卡了很久就觉得很神奇），于是走上了对着做法凑题的弯路。

当然，可喜之处是这个题最后还是没有出很基础的问题的，差评是可以预料的，好评才反而是奇迹，哪怕换做我是考试选手我也会想差评的，这个题的档次也完全不及我以前出的任何一个题。但是怎么说呢，这场UNR办的非常紧急（这个当然也有我自己的责任），差评题也胜过没有题。说不定你们NOI还会遇到更奇怪的题？

角度法

容易发现，顺时针方向走过的圈数可以通过将每次走的边的极角加起来再除以$2\pi$，即180°，得到。

射线法

容易发现，如果从原点任意引出一条射线，你所找出的欧拉回路在顺时针方向经过这条射线的次数减去逆时针方向的次数是一个常量，这个常量就是顺时针方向绕原点旋转的次数。

subtask1

这一个subtask就是直接暴力,枚举边的访问顺序并计算答案。时间复杂度是$O(m!poly(n, m))$。

subtask2

这一个subtask的做法是基于状态压缩的动态规划，记录一下当前已经访问的边和当前所在点，以及当前走过的角度和，或者当前顺时针时间方向经过射线的次数减去逆时针方向的次数，如果你使用射线法的话。复杂度是$O(2 ^ mn)$。注意不要记录当前所在边因为这将使时间复杂度退化为$O(2 ^ mn ^ 2)$(当然你很可能也能通过这个subtask)

判断一个图是否存在欧拉回路

这一步相信大家都会做，每个点的度数必须是偶数。且每一条边都必须和$1$号点连通。注意孤立点可以不与$1$号点连通。

subtask3

这个subtask就是最基础的费用流，同时也是给基于角度法的算法的。我们可以将原图转化为一个可以跑费用流的图：首先任意找一条欧拉回路然后计算答案，然后对于每一条边我们可以将其反向，我们可以反向连两条边，流量均为1，费用为角度或者顺时针穿过射线的次数。然而，直接连两条边会存在一个问题，你有可能只增广了一条边而没有增广另一条，这种情况下你相当于一条边没有经过。解决方案是将两条边合成一条流量和费用一样的边，然后将答案乘以二。由于原图存在负权，这个时候你只能用消圈做法，这大概没法过后面两个subtask。

另外一个思路是先任意定向并贡献答案，，新建源和汇，然后对于入度大于出度的点，从源向它连一条流量为入度减去出度的边；对于出度大于入度的点，从它向汇连一条流量为出度减去入度的边。由于前面我们将整张图的流量和会用都除以了$2$，这些流量也要除以$2$。容易发现如果存在欧拉回路的话，这些流量都是偶数，所以这个操作不会导致非整数的出现。然而这样建成的图还是有负权，这意味着我们必须用Bellman-Ford或者SPFA来做最短路，这个算法是平方级别的，乘上线性的增广的次数，总时间复杂度是$O(n ^ 2(n + m))$难以通过subtask4。

subtask4

接下来的算法都基于射线法。

对于一条权值为负数的边,我们可以通过将其反向来干掉负权。这样的话，开始的图不会有负权，我们可以用Dijkstra算法计算最短路，由于路径长度是$O(n)$以内的整数，可以用桶做到线性。

对于后面的图，负权边是难免的。考虑在做Dijkstra的时候每次选距离增加量最小的点而不是距离最小的点，可以证明基于增加量的图是没有负权的，于是我们可以在线性时间内更新最短路。

总时间复杂度为$O(n(n + m))$。

subtask5

在每次做完最短路之后，我们可以用dinic算法来增广掉当前残余网络上所有的流量。可以证明这样最短路长度将会增大。

容易证明在单位容量网络上做dinic的复杂度是$O((n + m)\sqrt{n})$的。

对于长度不超过$O(n ^ {\frac{1}{4}})$的最短路，做dinic的总时间复杂度为$O(n ^ {\frac{3}{4}}(n + m))$;由于答案不超过$O(n)$，长度超过这个值的最短路不超过$O(n ^ {\frac{3}{4}})$条，总时间复杂度也是$O(n ^ {\frac{3}{4}}(n + m))$。因此总时间复杂度不超过$O(n ^ {\frac{3}{4}}(n + m))$，可以通过本题。当然这个界感觉还是有点松，如果你发现了更优秀的下界请告诉我。

如果你常逛炉石相关论坛，你可能会遇到一些和这题模型一致的问题，如火山喷发概率求解。

网友们往往给出一些错误解法（如算法零）、多次随机模拟法（在这题中没有用）或是复杂度为指数级的解法（如算法一），然而事实上是可以在多项式时间内求出精确解的。

百鸽笼

from ztr， 题解 by ztr

算法零

每个鸽笼空着的概率相等，所以每列有空鸽笼的概率和这列的鸽笼数成正比（雾），且总和为$1$，容易求解。

期望得分：$0$。

算法一

我们令$m=max\{a_i\}$，并在接下来的算法描述中都有这个约定。

状态压缩DP，考虑计算每列鸽笼最后有空鸽笼的概率，记录每列鸽笼还剩余几个空鸽笼为状态，并枚举转移，复杂度$O((m+1)^nn^2)$。

期望得分：$10$。

算法二

注意到如果只是交换两列鸽笼的空鸽笼数量，得到的状态是等价的。对状态进行去重，复杂度$O(C_{n+m}^nn^2)$。

期望得分：$20$。

算法三

前面的算法已经没有什么优化的余地了。

我们可以考虑有$N$个管理员要住，每列鸽笼最后一个住满的概率。

最后一个住满就是在其他$n-1$列鸽笼住满后住满，考虑容斥，通过计算要在某些列鸽笼住满前住满的概率（其他列鸽笼先后任意）来求得答案。

假设选定了要在某$m$列鸽笼住满前住满，其余$n-m-1$列鸽笼什么时候有管理员进对你要算的概率已经没有影响了，于是考虑$m+1$列有关鸽笼的进入序列（每个管理员依次进入哪列）。

这个序列应当包含$a_i$个$i$（第$i$列是被计算概率的一列），少于$a_j$个$j$（第$j$列在选定的$m$列中），且以$i$结尾，且若其长度为$L$，则会产生$(\frac{1}{m+1})^L$的贡献。

这部分很容易使用背包DP来完成，记录用了前几个有关列和当前的总长度是多少为状态，枚举这一列要用掉多少个来转移，复杂度$O(n^2m^2)$。

由于拼在一起后可以任意排列，用掉$L_0$个的贡献要附带系数$\frac{1}{L_0!}$，最后长度为$L$的贡献要附带$L!$。

算上枚举容斥，总复杂度$O(2^nn^2m^2)$。

期望得分：$30$。

算法四

判断数据范围，结合算法二和算法三。

期望得分：$40$。

算法五

我在浏览选手代码时还发现了一种玄妙的DP（其中之一），大概是记录已进入管理员总数和那些列仍有空鸽笼（而没有记录每列具体空鸽笼数量），就能直接转移，复杂度$O(2^nn^2m)$。

期望得分：$30$

算法六

观察算法三的容斥过程，发现一个进入序列的贡献只和$L与m$有关，因此可以加一维状态表示当前选定的有关列数量，枚举这一列要不要被选定与如果要选定的话用掉多少个，这样就能去掉指数上的$n$，复杂度$O(n^3m^2)$。

由于每个都要算一遍，总复杂度$O(n^4m^2)$。

期望得分：$60-100$。

算法七

最后这步其实挺没意思的，算法五仍然是一个背包状DP，算第$i$列的答案的复杂度瓶颈是在把其他$n-1$个东西卷在一起，如果先全部卷起来然后每次退掉一个，复杂度即可优化到$O(n^3m^2)$。

期望得分：$100$。

算法八

事实上指数型生成函数爆推也是可以的。

首先参照PKUSC2018 狼人杀，可以认为已满的鸽笼列照样可以塞管理员（只是不产生效果），那么同样考虑入住序列，应当包含$a_i$个$i$（第$i$列是被计算概率的一列）和不少于$a_j$个$j$（第$j$列是其他列），且以$i$结尾，且若其长度为$L$，则会产生$(\frac{1}{n})^L$的贡献。

从指数型生成函数的角度来思考，对于单列鸽笼，如果其可以被入住$t$次，应当有$G(t)=\frac{x^t}{n^tt!}$的贡献。每列鸽笼可以被入住那些次数是独立的，因此目标函数$F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i}\sum_{t\geq a_j}G(t)$，且若$F=\sum c_ix^i$，则该列答案$Ans(i)=\sum c_ii!$。

又注意到$\sum_{t\geq 0}G(t)=e^{\frac{x}{n}}$，故若设$S(t)=\sum_{0\leq s\leq t}G(s)$，则$F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i}(e^{\frac{x}{n}}-S(a_i-1))$

考虑展开后每个$e^{\frac{mx}{n}}x^t=\sum_{s\geq0}\frac{m^s}{n^ss!}x^{t+s}$，现欲求其贡献$\sum_{s\geq0}(\frac{m}{n})^s\times\frac{(t+s)!}{s!}$，容易化得此式为$(\frac{n}{n-m})^{t+1}t!$。

因此只需要求出这些可能展开项的系数即可，不难发现在代码实现上，该做法与容斥做法几乎完全一致。

鸽举选仕

from whzzt， 题解 by whzzt 首先作为出题人给大家道个歉……准备时间有点紧张，没有来得及对每个子任务进行认真的检查和加强，对UOJ系统不熟悉、赛中又出了若干口大小不等的锅，实在是有点难受啊……都怪*鸽普太鸽了(甩锅)

今天这题的源代码已经提供给选手了，因此卡这些乱搞就会显得容易很多。出这题也算是让大家感受一下出题人的不易？

子任务一

我们观察一下下发的代码：

#include <stdio.h>
int a, b;
int ADD(int a, int b){ return (a ^ b) | (a & b) << 1; }
int main(){
    scanf("%d%d", &a, &b);
    printf("%d\n", ADD(a ^ b, (a & b) << 1));
    return 0;
}

显然将函数 $ \texttt{ADD} $ 中的 $ \texttt{|} $ 改为 $ \texttt{+} $ 就是正确的，否则错误率有点高。

所以我们随便手输几组 $ a, b $ 就好啦！

子任务二

我们可以发现这位选手的代码中分成了两个部分：当边数 $ m $ 很少时跑 $ O(m) $ 的暴力，边数较多时跑 $ O(n^2) $ 的 BFS。

在小数据的时候显然这份代码不会超时，所以我们可以先拿出 $ 10^3 $ 左右个节点连成一个完全图，然后再挂出去一条链，每次询问链的端点到图上一点即可。

代码:

#include<stdio.h>
int main(){
    int i;
    puts("5000 10000");
    for(i=2;i<=1000;i++)printf("1 1 %d\n",i);
    puts("1 1000 5000");
    for(i=4999;i>=1001;i--)printf("1 %d %d\n",i+1,i);
    for(i=1;i<=5001;i++)printf("2 %d %d\n",i%1000+1,1001+i/1000);
}

子任务三

咦这个乱搞怎么似曾相识？这么困难，怎么做？

我们考虑我们的目标是什么：不妨考虑构造两棵形态相同的树，假设答案点对为 $ (x, y) $，那么最终的答案就是 $ d_1(x) + d_1(y) - d_1(lca(x,y)) - d_2(lca(x, y)) $。

我们想要钦定一对这样的 $ x $ 和 $ y $，那么什么能够让我们完成这个任务？当然是让 $ d_2(lca(x, y)) $ 尽量小，同时不存在其他点对 $ p, q $ 使得 $ lca(p, q) = lca(x, y) $。

这显然是不可能的，例如 $ p = lca(x, y) $ 时只需选择一个子树中的点。但是我们可以钦定 $ d_1(lca(x, y)) $ 也很小，这样我们就不能选择 $ lca(x, y) $ 这个点啦。

如此一来我们保证了答案的唯一性，并且在过程中只用了 $ 3 $ 个节点，接下来的任务就是使得在迭代过程中如果碰到的不是 $ x, y, lca(x, y) $，就一定无法迭代到最优解。

这就非常容易了，因为点 $ x $ 和点 $ y $ 间存在一个 % d_2(lca(x, y)) 的天然优势，接下来我们只要用另外的一些点引诱你过去就可以了。

一种构造大致如下：

#include<bits/stdc++.h>
using namespace std;
int rnd(){return rand()<<15|rand();}
int rnd(int l,int r){return rnd()%(r-l+1)+l;}
const int N=100005,inf=2e9;
int n=100000,m,p[N],fa[N],fd1[N],fd2[N];
int main(){
    int i;
    for(i=1;i<=n;i++)p[i]=i;
    for(i=1;i<=n;i++)swap(p[i],p[rnd(i,n)]);
    m=n-100;
    for(i=2;i<=m;i++)fa[i]=rnd(1,i-1),fd1[i]=rnd(-10,10),fd2[i]=rnd(-10,10);
    fa[m+1]=1;fd1[m+1]=-inf;fd2[m+1]=-inf;
    fa[m+2]=m+1;fd1[m+2]=inf;fd2[m+2]=rnd(1,10);
    fa[m+3]=m+1;fd1[m+3]=inf;fd2[m+3]=rnd(1,10);
    fa[m+4]=m;fd1[m+4]=-inf;fd2[m+4]=-inf;
    for(i=m+5;i<=n;i++)fa[i]=i-1,fd1[i]=-inf+rnd(-10,10),fd2[i]=-inf+rnd(-10,10);
    //best solution: m+2, m+3
    printf("%d\n",n);
    for(i=2;i<=n;i++)printf("%d %d %d\n",p[fa[i]],p[i],fd1[i]);
    for(i=2;i<=n;i++)printf("%d %d %d\n",p[fa[i]],p[i],fd2[i]);
}

好像因为时限太小大大降低了难度。

子任务四

感谢@Foolmike提供该子任务。

咦这个子任务真的错了吗？

撕烤一下我们可以发现，这份代码的主要思想是维护 $ f_i = \max(f_j + \max(w_{j + 1} \ldots w_i)) $ 的最大的 $ j $，并使用单调队列维护。但是我们可以发现可行的 $ j $ 并不是单调的。

因此我们只要随便手动构造一下就可以得到这个子任务的分数啦，怎么样，是不是很开心呢！

示例：

12 4
0 0 0 70 80 90 1000 1000 1000 200 180 199

子任务五

题面中忘记写 $ k \ge 2 $ 了嘤嘤嘤。

容易发现只有 $ k = 2 $ 时有用，正确的做法是将点拆成两边表示成矩形面积的形式，这样有决策单调性。

咦这个做法怎么有三个错误做法套在一起还加了卡时？这一看就卡不掉嘛。

容易发现第一个随机两个产生贡献就是来搞笑的，有用的只有后面两个做法。

后面的两个做法实际上是套在一起的，你只需要保证最优解的两个区间一定不在 $ 1 $ 中最大的若干个即可。

这就非常容易啦！我们只要硬点最优解是选择第 $ n - 1 $ 个区间和第 $ n $ 个区间，然后在前面安排 $ 99990 $ 个区间理性愉悦一下就好啦！

#include<bits/stdc++.h>
using namespace std;
const int N=100005,B=1e7,Q=1e8,R=Q-1,inf=1e9;
int n=100000,m=99990,l[N],r[N];
int main(){
    int i;
    for(i=1;i<=m;i++)l[i]=i,r[i]=i+R;
    l[n]=inf-Q;r[n]=inf;l[n-1]=inf-Q-1;r[n-1]=inf-1;
    for(i=m+1;i<=n-2;i++)l[i]=l[n]-B*(n-i),r[i]=l[n]+i;
    printf("%d\n",n);
    for(i=1;i<=n;i++)printf("%d %d\n",l[i],r[i]);
    return 0;
}

子任务六

老师，我的旋转卡壳就是这么写的！我觉得这份代码没有问题！

我们重新审视一下这样写旋转卡壳为什么会GG，容易证明对于一个凸包上的一个点来说，最远点在凸包上是决策单调的。那么这个做法的唯一问题就在于距离函数不一定是单峰的。

如上图所示，我们只有恰好走到两端才能使得被困住的铁蹄继续前进，这种情况下上述算法显然是错误的。

这份代码好像写错了一点啊，如果j > n 本应该更新 ret[j - n] 的。

子任务七

分值这么小一定是送分点！

可以发现这份代码实际上就是将相同的数缩起来，并且实现也非常普通。

因此随便随一组只有区间加没有区间覆盖数据就可以过惹！这告诉我们出数据结构题数据不能在不同操作间均匀随机。

实现比较简单就不贴了。

子任务八

无论是观察代码还是观察题面都可以发现，只有最小生成树上的边有用！因此我们只要求平面欧几里得最小生成树就好啦！

可以发现这份代码是将点在 $ x $ 轴和 $ y $ 轴上分别投影，找到最近的若干个点并连边。

那么我们只要让两个必连的点连不上就好啦！

构造实现比较简单，代码略去。

思考：如何卡掉在更多条过原点的随机直线上投影的算法？

感谢@vfleaking提供该subtask的std。

鸽子固定器

from AprilGrimoire， 题解 by AprilGrimoire

这次的题目顺序真是十分抱歉QwQ A题可能是三道题中AC人数最少的了……

然而这题std才50行，放B和C显得不太合适哇QwQ

子任务一

$n$的范围只有$10$，所以随便怎么暴力都可以哇QwQ

时间复杂度：$\Omega(poly(n))$

期望得分：$5$

子任务二

容易发现，如果我们确定了选择的固定器大小的范围，那么一定会选择这些固定器中牢固度最大的至多$m$个。所以我们可以把固定器按大小排序，枚举选择的右端点，然后将左端点向左扫一遍。在扫的过程中，用一个小根堆来维护选择的固定器的牢固度。

时间复杂度：$O(n^2 log m)$

期望得分：$10$

子任务三

当$d_s=d_v=1$的时候，首先把鸽子固定器按照大小排序。设$f_{i,j}$表示在前$i$个固定器中选择$j$个，且必须选择第$j$个的价值的最大值。则 $$f_{i,1}=v_i$$ $$f_{i,j}=\max\limits_{1 \leq k < j}f_{k,j-1}-(s_i-s_k)+v_i\\=v_i-s_i+\max\limits_{1 \leq k < j}f_{k,j-1} + s_k$$ 只要记录前缀最大值进行DP，就可以在$O(nm)$的时间内解决子任务三。

时间复杂度：$O(nm)$

期望得分：$10$

结合子任务二的做法可以获得$20$分。

子任务四

考虑子任务二的一个优化：在扫描过程中，如果发现右端点被出堆了就终止扫描。这样做显然是对的，因为右端点被出堆后的方案可以通过简单地左移右端点来使答案变优，一定不是最优值。然而，对于构造的数据，这个优化可能并没有什么用：

200000 50 2 2
1 1
2 2
3 3
...

对于这样的数据，这个优化并没有什么用。然而对于随机数据，它还是跑得挺快的。让我们进行一波有理有据的分析：对于第$i$大的固定器，随机找另一个固定器，有大约$\frac{i}{n}$的概率找到一个比它大的固定器。也就是说，期望扫描$\frac{n * m}{i}$个固定器，它就会被出堆。对于所有固定器，扫描所需要的总期望时间是 $$\sum\limits_{i=1}^{n}\frac{n * m}{i} = O(nm\log{n})$$

时间复杂度：$O(nm\log{n})$

期望得分：$25$

结合前三个子任务的做法可以获得$45$分。

子任务五

假设以$i$为右端点向左扫描时，$j$号点始终没有被入堆，那么以$i+1$为右端点时，它肯定也不会被入堆。这启示我们大胆猜想：对于右端点来说，左端点有决策单调性！取区间上前m大的点可以用主席树在$O(\log n)$的时间内完成，再算上决策单调性二分的$O(\log n)$，我们就可以在$O(n\log^2n)$的时间内解决

.

.

.

$d_v \neq 2$的情况。为什么当$d_v = 2$时没有决策单调性呢？考虑这样的数据：

200000 50 2 2
1 5000
2 1
3 1
...
199999 1
200000 10000000

对于中间的大部分点，最优决策都是选连续的$m$个固定器。而对于最后一个点，最优策略是选择最后一个点，第一个点和中间任意48个点。非线性的东西往往能够破坏决策单调性。

这个做法实际上可以通过前五个子任务，因为小数据不太好卡，对于随机数据正确性又很高。

实际上冷静一下就能发现决策单调性是假的：如果复杂度和$m$无关，为啥$m$这么小呢？

时间复杂度：$O(n \log^2 n)$

期望得分：$70$

子任务六

考虑优化子任务四的做法。这个做法会被价值递增的数据给卡掉。那么，如果我们二分ST表来找下一个会被入堆的点呢？事实上，这个算法是能通过全部数据的。

证明：假设在以$i$为右端点向左扫描时$j$被入堆了，就记录有序对$(j, i)$。我们把有序对$(a, b)$分成两类：$v_b \geq v_a$的叫做第一类有序对，$v_b < v_a$的叫做第二类有序对。 1. 对于第一类有序对$(a, b)$，一个$b$最多对应$m$个$a$。（否则$b$会被出堆） 2. 对于第二类有序对$(a, b)$，一个$a$最多对应$m$个$b$。（否则在扫描到$a$的时候，堆里至少有$m$个比$a$大的数，也就是说，$a$不会被入堆）

入堆操作最多会被执行$O(nm)$次，每次需要$\log n$的时间来二分ST表和$\log m$的时间来入堆，因此，这个做法能够在$nm \log n$的时间内通过所有子任务。

时间复杂度：$O(nm \log n)$

期望得分：$100$

神奇的做法

在比赛时，发现了这样一种神奇的做法： 按照坚固度从小到大考虑所有固定器。 1. 如果当前固定器被选中了，那么选中的固定器集合一定是一个区间。（否则可以把当前固定器换掉来获得更优的答案。） 2. 如果当前固定器没被选中，我们可以把它删掉。

用链表维护剩下的固定器。包含当前最小固定器的区间最多只有$m$个，所以这个算法的复杂度是$O(nm)$的。

子任务六的两个优化

1. 用链表维护当前可能被入堆的点集。如果在从右往左扫的过程中一个点没有被入堆，那么我们可以把它从点集里删掉，因为它以后也永远不会入堆。这样就能避免二分ST表，只有$O(nm \log m)$的复杂度。（$\log m$是因为需要用堆维护当前被选的固定器。）
2. 堆也不是必要的，因为每次可能入堆的点只会增加一个，所以可以线性维护当前被选中的点集。这样就能做到$O(nm)$。

To Do Tree

对于大多数OIer来说，这题应该是个大胆猜结论题。

算法零：构造

看过题的同学就知道，subtask3就是送分的，每星期只能肝一个ddl，搞什么都行嘛……只要输出格式没有问题，大家应该都能得到这$6$分。

算法一：搜索

直接枚举每星期肝的ddl集合搜索，期望得分$30$，可以通过subtask1。

结合算法零可以得到$36$分。

算法二：子集dp

设$dp_{S}$表示肝掉集合$S$中的所有ddl所需要的最少的时间，然后枚举下一次肝的集合转移即可。

时间复杂度$O(3^{n})$，期望得分$60$分，可以通过subtask1，subtask2。

结合算法零可以得到$66$分。

算法三：构造

这个题看起来不可做又看起来很可做，有哪些选手能证明一下自己的算法是最优的呢？

先说出题人Mike给出的一种构造算法和证明。

首先对把依赖关系翻转一下，对于任意一个任务$i$，执行$i$之前必须先完成$i$的所有子节点。这个问题的最优解把执行顺序反转一下就是原问题的最优解了。

直接说结论：每次选择最深的叶节点执行，若有多个则随意执行一个即可。

证明如下：

考虑答案的两个显然的下界，$t \geq max_{i \in T}(dep_{i})$，$t \geq \frac{n}{m}$。

显然前面那个是机器数较多的情况，后面那个是机器数较少的情况。

然后将节点按深度分两块，任取一个深度$\alpha$，有

$$t \geq \alpha - 1 + \frac{\sum_{i = \alpha}^{n}p_{i}}{m}$$

显然最早在时刻$\frac{\sum_{i = \alpha}^{n}p_{i}}{m}$时深度不小于$\alpha$的节点才能被处理完，此时至少会剩下一个深度为$\alpha - 1$的节点，至少还需要$\alpha - 1$时间才能完成，因此这是总用时的一个下界。(显然对于$\alpha = 1$时也成立，但上面的叙述有问题)

下面证明$t \geq max_{\alpha}(\alpha - 1 + \frac{\sum_{i = \alpha}^{n}p_{i}}{m})$是一个紧下界。

考虑最大值时$\alpha$取到的$\beta$，如果有多个则取最小的，则有

$$\forall d < \beta, \frac{\sum_{i=d}^{\beta - 1}p_{i}}{\beta - d} < m$$

上式显然成立，否则$\alpha$取$d$的函数值不比$\alpha$取$\beta$时小。

根据当前树的深度是否小于$\beta$，我们按时间序将算法分为前半部分和后半部分。

下面证明，假设深度不小于$\beta$的节点全部被完成后，剩下的节点只需要$\beta - 1$时间就能完成。

首先归纳证明，算法执行过程中，任意时刻树中深度最大的任意$k$层节点，每层的节点均值都小于$m$。

形式化的表述是，设树的深度为$h$，则有$\frac{\sum_{i = d}^{h}p_{i}}{h - d + 1} < m$。$(1)$

也就是和上面一样的形式。

采用归纳法，反证，假设经过了$1$时间后深度至少为$d$的部分不满足条件，取最大的$d$。

根据假设，显然有$p_{d} \geq m$，否则深度至少为$d + 1$的部分也满足条件，与$d$最大矛盾。

考虑此时深度为$d$的这些点构成的子树，显然每个子树至少有一个叶节点，因此当前深度不小于$d$的叶节点有至少$m$个。

删掉一个节点后，深度不小于$d$的节点个数单调不减，因此上一次深度不小于$d$的叶节点个数不小于$m$，根据算法流程可知上次删掉的节点深度至少为$d$。

则上次深度不小于$d$的节点有$\sum_{i = d}^{h}p_{i} + m$个，$h$是当前树的深度，$p_{i}$是当前树中深度为$i$的节点个数。

$$\sum_{i = d}^{h}p_{i} \geq m(h - d + 1)$$

$$\sum_{i = d}^{h}p_{i} + m \geq m(h - d + 2)$$

即上次深度不小于$d$的部分也不满足条件，与归纳条件矛盾，因此命题$(1)$得证。

由命题$(1)$可得，算法执行后半部分的任意时刻，深度最大的节点个数不超过$m$，因此只需要树的深度时间就能够执行完所有深度小于$\beta$的节点。

下面证明删掉深度不小于$\beta$的节点只需要$\lceil \frac{\sum_{i = \beta}^{n}p_{i}}{m} \rceil$时间。

由$\beta$的定义，可以得到如下结论：

$$\forall d \geq \beta, \frac{\sum_{i = \beta}^{d}p_{i}}{d - \beta + 1} \geq m$$

否则$\alpha$取$d$的函数值比$\alpha$取$\beta$时大。

下面证明，算法执行前半部分的任意时刻，设当前树的高度为$h$，深度为$i$的节点有$p_{i}$个，则对于任意的$\beta \leq d < h$，满足上述条件

$$\forall \beta \leq d < h \frac{\sum_{i = \beta}^{d}p_{i}}{d - \beta + 1} \geq m(2)$$

使用归纳法，反证，假设经过$1$时间后深度为$\beta$到$d$的部分不满足条件，取满足条件最小的$d$。

这个单位时间内显然删掉了至少一个深度为$d$的节点。(上一时刻时这一部分还满足条件)

这说明之前深度大于$d$的部分叶节点不足$m$个。

若$d \geq h$，则当前的$d$不在定义域中，自然不影响成立性。

若$d < h$，则此时这一时刻内一定删掉了所有深度为$h + 1$的点。

由于深度大于$d$的叶节点个数随时间单调不减，且上一时刻深度大于$d$叶节点个数不足$m$，所以只需要$h - d$时间就能将所有深度大于$d$的部分删去，因此在上一时刻有

$$\sum_{i = \beta}^{d}p_{i} < (d - \beta + 1)m + D$$

其中$D$为删掉的深度为$d$的节点个数。

深度不少于$d + 1$的叶节点至少有$p_{d + 1}$个，因此$D \leq m - p_{d + 1}$。

因此得到

$$\sum_{i = \beta}^{d + 1}p_{i} < (d - \beta + 2)m$$

又$d < h$，因此上一时刻取$d = d + 1$时条件不满足，与归纳基础矛盾，因此命题$(2)$得证。

因此当深度大于$\beta$时恒有$p_{\beta} \geq m$，即深度不小于$\beta$的叶节点个数$\geq m$，每次都能取满$m$个。在深度为$\beta$处至多一次取不满$m$，因此前半部分可以在$\lceil \frac{\sum_{i = \beta}^{n}p_{i}}{m} \rceil$内完成。

综上，算法正确性和用时下界都得到了证明。

这个算法可以做到$O(n)$的，想必大家都会，也不是重点，于是就没设分。

按深度贪心也是正确的，证明主要思路采用调整法；按大小贪心也是正确的，证明主要思路采用反证法。证明繁杂赛后我在uoj博客发一下证明。

配对树

from C_SUNSHINE， 题解 by C_SUNSHINE

子任务 1

我们可以暴力枚举ddl区间，然后在树上做树形DP来计算最小匹配的大小，如何DP呢？

令 $f_{i,j}$ 表示 $i$ 的子树内还有 $j$ 个点没匹配的匹配大小，然后计算转移边需要被覆盖几次。这个想法明显太傻了，我们不可能让子树内的点拉到子树外面配对的，如果存在两个点 $x, y$ 他们在子树内都没有配对，那么假设他们分别和 $x', y'$ 配对，显然 改为 $x, y$ 配对 $x', y'$ 配对更优，所以 $j$ 只能是 $0$ 或1。

接着发现其实 $j$ 的奇偶性和子树内ddl数目的奇偶性相同，于是直接dp即可。

时间复杂度 $O(m^2n)$。

子任务 2

我们接着观察，对于一个确定的ddl区间，一条树边被匹配包含了当且仅当把它删去后树被分成两个包含奇数个ddl的块。若我们令 $1$ 为根做dfs，则一个非根点父向边被包含当且仅当其子树内有奇数个ddl。

我们可以换一种方式思考，计算一条树边被多少个偶区间覆盖。

枚举一条树边，把它子树内的ddl全部在序列上标为 $1$ 其余标为 $0$，来把序列转成 $01$ 串，于是问题变成了统计 $01$ 串中包含偶数个 $1$ 的子串数目。

对 $01$ 串做前缀和得到 $s_i$，则一个区间 $[l,r]$ 要被统计当且仅当 $s_r-s_{l-1} \equiv 1 \pmod 2$ 由于 $l-1 \equiv r \pmod 2$，我们可以对 $s_i(0 \leq i \leq m)$ 按照下标奇偶性分别维护，维护对 $i \mod 2 = k = 0$ 或 $1$ 分别计算 $s_i$ 中奇数的数目 $cnt_{k,1}$ 和偶数的数目 $cnt_{k,0}$。那么包含这条树边的区间数目就是 $cnt_{0,0} \cdot cnt_{0,1} + cnt_{1,0} \cdot cnt_{1,1}$。

把序列转化成 $01$ 串需要 $n+m$ 的时间，统计 $cnt$ 需要 $O(m)$ 的时间，于是时间复杂度为 $O(n^2+nm)$。

子任务 3

这个直接把不超过 $100$ 个点的虚树建出来之后暴力即可。

子任务 4

我们可以考虑使用线段树来维护序列转化成的 $01$ 串，可以发现，我们只需要在线段树区间上维护区间内的 $cnt_{k,0/1}$，通过左半边内 $1$ 的数目来决定是否对右边进行反转，就可以 $O(1)$ 时间合并左右区间，最终需要的 $cnt$ 的值会统计在根节点上。

既然单次修改 $01$ 序列是 $O(\log m)$ 的，我们可以枚举每条边，然后只加入其子树，总修改次数为 $O(n^2)$，于是复杂度为 $O(n^2 \log m)$。

子任务 5

这条件其实没什么特别的用处，只是让点的分步均匀一些。

子任务 6

树是随机的，我们依旧暴力枚举树边然后只添加子树，可以发现每个点会被添加恰好深度次，而深度的期望是 $O(\log n)$ 的，所以总修改次数的期望也是 $O(m \log n)$ 的，总复杂度就是 $O(m \log n \log m)$ 的。

子任务 7

在本来的做法中，我们对子树做完后，清空线段树再吧子树内的 ddl 重新加入，可以发现这个过程中有重复计算。考虑对于每个点 $x$ 我们在 dfs 完其最后一个孩子之后，不清空 dfs 时的修改，而是把其他孩子子树内的 ddl 直接补上，令 $x$ 的最后一个孩子为 $son_x$， $x$ 到 $son_x$ 的边称为特殊边，可以发现，一个 ddl 被添加次数为其到跟的路径上非特殊边的数目。

到这里其实算法已经很显然了，对树轻重链剖分，$son_x$ 就是 $x$ 的重孩子，一个 ddl 被添加的次数就是其到根的路径上轻边的数目是 $O(\log n)$ 的，采用线段树维护的话复杂度就是 $O(m \log n \log m)$，这个算法可以通过本题。提交记录点这里

因为NOI之前信心赛大家开心就好，所以两个 $\log$ 是可以通过的。

这题我本来出出来准备当个前两题的难度的，但不知道哪个管理员就把它挂到 C 题上了，我给他题解的时候还把这段话删了，所以两个 $\log$ 是可以通过的。

想到用线段树维护后，本题有个较为直接的做法即采用线段树合并，每个点的线段树可以看成其所有子树并起来再插入其上的 ddl，我们知道 $m$ 个只有一个元素的线段树合并的复杂度为 $m \log m$，所以直接采用线段树合并可以做到 $O(n + m \log m)$ 的复杂度，只不过空间是 $\Theta(m \log m)$ 的。提交记录点这里 不过采用 Splay 做合并的话，空间可以做到 $O(n)$。

你要问我为啥就是个 Splay 合并却写这么长题解，我只能说……既然管理员钦点了，得装的像个 C 题的样子（逃