UOJ NOI Round #3 Day2 题解

白鸽

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;
}