祝大家新年快乐，场场ak！

新年的XOR

出题人 jiry_2

数据和题解 jiry_2

这道题可能并没有那么有趣..本来有一道很棒的 A，但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

算法一

既然 $n$ 那么小，相信 $L$ 和 $R$ 肯定也不是很大，直接枚举 $L$ 和 $R$ 然后暴力算异或和！

时间复杂度 $O(n^3)$，期望得分 $20$ 分。

算法二

暴力算异或和太蠢了，直接预处理个前缀异或和 $w_n$ 然后 $O(1)$ 用 $w_{l-1}\oplus w_r$ 算，岂不美哉。

时间复杂度 $O(n^2)$，期望得分 $40$ 分。

算法三

好像预处理完前缀异或和之后左端点都不用枚举了，直接枚举右端点然后查表看看有没有能用的左端点就好了。

时间复杂度 $O(n)$，期望得分 $60$ 分。

算法四

好像所有合法的区间左端点都很小。那么就在 $[n-100,n+100]$ 枚举右端点，然后在 $[1,100]$ 枚举左端点试试。

怎么算前缀异或和呢？不难发现 $2i\oplus (2i+1)=1$，所以如果 $n$ 为奇数，那么 $w_n$ 就是 $\frac{n+1}{2}\mathrm{mod}2$，如果 $n$ 为偶数，那么 $w_n$ 就是 $n+(\frac{n+1}{2}\mathrm{mod}2)$。

时间复杂度 $O(1)$，期望得分 $100$ 分。

算法五

诶好像算法四直接 A 掉了。不难发现 $w_n\oplus n\in [0,1]$，而 $w_0=0,w_1=1$，所以只要取 $l\in [1,2]$ 来微调一下个位就可以啦。

因为要求区间的两端都是正数以及区间长度大于 $1$，所以对于 $n=0,1,2$ 要特判一下。

时间复杂度 $O(1)$，期望得分 $100$ 分。

新年的叶子

出题人 liu_runda

数据和题解 Scape。

算法一

我们先来考虑一下有关直径的一些性质。

我们这里定义直径的长度是直径上边的条数。

显然一棵树可能会有多条直径，但是这些直径的中点显然应该是重合（对于直径长度是偶数）或者相邻（对于直径长度是奇数）。

否则的话我们可以从直径的一个端点出发，走到直径的中点，再走到另一条直径的中点后走到另直径的一个端点，这样可以得到一个更长的直径。

所以我们可以找到任意一条直径的中点，然后把所有叶子按照它位于这个中点的哪个儿子的子树中分成若干个集合，并且以该中点为根计算出每个叶子的深度。

令叶子的深度最大值是$Max$。

对于直径长度为偶数的情况，直径会变小 当且仅当 所有没有被染黑的且深度为$Max$的叶子 都在同一个集合里。

对于直径长度为奇数的情况，直径会变小 当且仅当 深度为$Max$的叶子都被染黑 或者 深度为$Max-1$的叶子都被染黑。那么我们把深度为$Max-1$的叶子全部放在同一个集合里，奇数的情况就变成了和偶数一样。我们可以一起解决。

接下来我们就要考虑这样一个问题，我们有若干个集合，每个集合里都有若干个叶子。我们每次会随机染黑一个叶子，问期望多久后只剩下一个集合里的叶子不是全黑。

令叶子总数是$m$。

我们可以先转化一下，把“每次随机染黑一个叶子（可能会重复染黑）”改成“每次随机染黑一个还没有被染黑的叶子”。这样转化后，假设还剩下$k$个叶子没有被染黑，那么要染黑一个还没有被染黑的叶子的代价就是$\frac{m}{k}$。

接下来我们只要暴力枚举删除叶子的顺序，就可以计算了。

时间复杂度$O(n!)$。期望得到$12$分。

算法二

我们考虑枚举哪个集合最终剩下了。

令$f[i][j]$表示当且集合还剩下$i$个，其他集合还剩下$j$个时期望的删除时间。直接按照定义转移就可以了。

时间复杂度$O(n^2)$。期望得到$30$分。

算法三

我们考虑枚举哪个集合最终剩下了，设当前集合大小为$k$。

设所有集合大小的和为$n$。

我们枚举当其他所有集合都染黑时，当前集合还剩下$i$个没有被染黑，那么这样的情况对答案的贡献为

$$\frac{(\genfrac{}{}{0ex}{}{k}{i})\times (\genfrac{}{}{0ex}{}{n-i-1}{n-k-1})\times (\genfrac{}{}{0ex}{}{n-k}{1})\times (k-i)!\times (n-k-1)!\times (i)!}{n!}\times (\sum _{j=i+1}^n\frac{m}{j})$$

线性预处理阶乘，阶乘逆元与逆元的前缀和就可以做到$O(n)$的时间复杂度。

算法四

from WuHongxun

什么，那么上面复杂的贡献你不知道怎么回事？不要急，这个题之所以在B题而不是C题，就是因为有算法四。

考虑我们每次枚举一个集合$x$，然后不管它，计算剩下的集合被全部染黑所需要的期望时间，然后把这些时间加起来。

这个期望时间当然非常好算，如果一共有$n$个叶子，我们关心的有$m$个叶子，那么我们第一步需要期望$\frac{n}{m}$步染黑一个关心的叶子，显然答案就是$\sum _{i=1}^m\frac{n}{i}$，只要预处理$h_n=\sum _i\frac{1}{i}$就可以$O(1)$计算了。

算出来这个有什么用呢？

考虑任何一个方案里我们染黑到所有集合都变黑了为止，它对答案的贡献是多少呢？如果$x$是这个方案里最后被染黑的集合，那么是倒数第二个被染黑的时间，反之则是最后一个集合被染黑的时间，假设有$L$个集合，那么全部染黑被算了恰好$L-1$次。

所以只要每次枚举一个集合，算剩下集合全部染黑的期望时间加到答案中，最后在答案里扣掉$L-1$倍把所有集合全部染黑的期望时间，就可以啦！

是不是非常简单呢？

新年的五维几何

出题人 ftiasch

数据和题解 WrongAnswer

算法一

当 $n=1$ 时，满足约束的条件是 $x_1-x_1\ge a_{1,1}$ 即 $a_{1,1}\le 0$，因此当 $a_{1,1}\le 0$ 时输出 $1$，当 $a_{1,1}>0$ 时输出 $0$。

可以通过子任务1，期望得分5分。

算法二

注意到如果有一个 $a_{i,i}>0$，答案一定是 $0$，否则不用考虑 $a_{i,i}$ 的约束。以下算法均假设所有 $a_{i,i}\le 0$。

当 $n=2$ 且 $l_1=r_1$ 时，恒有 $x_1=l_1$，实际上只有 $x_2$ 一个变量。

若 $l_2=r_2$，仿照算法一判断四个约束是否同时满足即可，同时满足则输出 $1$，否则输出 $0$。

若 $l_2<r_2$，则约束 $x_1-x_2\ge a_{1,2}$ 等价于 $x_2\le l_1-a_{1,2}$，约束 $x_2-x_1\ge a_{2,1}$ 等价于 $x_2\ge l_1+a_{2,1}$，求出两个约束和 $l_2\le x_2\le r_2$ 的交集长度，除以 $r_2-l_2$ 就是答案。

结合上述算法，可以通过子任务1,2，期望得分15分。

算法三

当 $n=2$ 时，如果 $l_2=r_2$，交换两个变量即可用算法二解决，故以下假设 $l_1<r_1$ 且 $l_2<r_2$。

用 $x,y$ 表示变量 $x_1,x_2$，则在平面直角坐标系 $xOy$ 中，变量的定义域是一个矩形 $l_1\le x\le r_1$，$l_2\le y\le r_2$，而约束的区域是该矩形和半平面 $x-y\ge a_{1,2}$ 及 $y-x\ge a_{2,1}$ 的交集。

考虑只有一个约束 $x-y\ge a_{1,2}$，则约束对应的区域为矩形位于直线 $y=x-a_{1,2}$ 下方的部分。当直线不穿过矩形时，答案为 $0$ 或 $1$，否则该区域可能是直角三角形、直角梯形或者矩形去掉一个直角三角形，根据点 $(l_1,r_1),(l_2,r_2)$ 在直线的上、下方分四类情况讨论计算区域面积即可，答案为该区域面积除以矩形面积 $(r_1-l_1)(r_2-l_2)$。

当有两个约束 $x-y\ge a_{1,2}$ 和 $y-x\ge a_{2,1}$ 时，将 $y-x\ge a_{2,1}$ 变形为 $x-y\le -a_{2,1}$，可得答案为约束 $x-y\ge a_{1,2}$ 的答案与约束 $x-y\ge -a_{2,1}$ 的答案之差（如果差为负数，答案为 $0$）。

结合上述算法，可以通过子任务1,2,3,4，期望得分50分。如果你只考虑了 $a_{1,2}$ 一个约束，则只能得到35分。

算法四

对于当 $j\ne i+1$ 时 $a_{i,j}=-10$ 的子任务，只需考虑相邻变量的约束。

设 $f_i(x)$ 为变量 $x_i,x_{i+1},\cdots ,x_n$ 满足约束且 $x_i\le x$ 的概率，显然 $f_{n+1}(x)=1$。

当 $x<l_i$ 时，有 $f_i(x)=0$；当 $x>r_i$ 时，有 $f_i(x)=f_i(r_i)$。

否则，因为 $x_i-x_{i+1}\ge a_{i,i+1}$ 等价于 $x_{i+1}\le x_i-a_{i,i+1}$，所以当 $x_i=x$（$x\in [l_i,r_i]$）时，$x_i,x_{i+1},\cdots ,x_n$ 满足约束的概率为 $f_{i+1}(x-a_{i,i+1})$，于是，当 $l_i=r_i$ 时，有$$f_i(x)=f_{i+1}(l_i-a_{i,i+1})$$

当 $l_i<r_i$ 时，有$$f_i(x)=\frac{1}{r_i-l_i}{\int }_{l_i}^x{f}_{i+1}(y-a_{i,i+1})\mathrm{d}y$$

注意到 $f_i(x)$ 是一个段数 $O(n)$ 的分段多项式，维护每个分段多项式，用定积分进行转移即可。

结合上述算法，可以通过子任务1,2,3,4,7，期望得分70分。

算法五

注意到 $l_i,r_i,a_{i,j}$ 都是整数且 $l_i,r_i$ 范围很小，不妨枚举每个 $x_i$ 的整数部分。

当 $l_i=r_i$ 时，$x_i$ 是确定的，无需枚举；否则，记 $x_i=p_i+q_i$，其中 $p_i$ 在 $[l_i,r_i)$ 的整数中均匀随机，$q_i$ 在 $[0,1)$ 的实数中均匀随机，我们枚举每个 $p_i$，计算随机生成 $q_i$ 有多少的概率满足所有约束，每组 $p_i$ 下概率的平均值就是答案。

因为 $x_i-x_j\ge a_{i,j}$ 等价于 $q_i-q_j\ge a_{i,j}+p_j-p_i$：

1. 当 $a_{i,j}+p_j-p_i\le -1$ 时，约束总能满足，不考虑该约束；
2. 当 $a_{i,j}+p_j-p_i\ge 1$ 时，约束不可能满足，该情况的概率直接返回 $0$；
3. 当 $a_{i,j}+p_j-p_i=0$ 时，约束等价于 $q_i\ge q_j$。

现在只要考虑若干个形如 $q_i\ge q_j$ 的约束同时被满足的条件。

注意到如果所有的 $q_i$ 均匀随机生成，那么有两个 $q_i$ 相等的概率为 $0$，$q_i$ 可能出现的 $n!$ 大小顺序是等概率的，每种的概率均为 $\frac{1}{n!}$。因此对每个 $l_i<r_i$ 的变量建一个点 $i$，每个约束 $q_i\ge q_j$ 连一条边 $j\to i$，设该图的拓扑序有 $T$ 个，则满足所有约束的概率为 $\frac{T}{n!}$。

直接枚举排列或者状压DP均可计算拓扑序个数。

时间复杂度 $O((r_i-l_i{)}^{n}n!\cdot n)$ 或 $O([2(r_i-l_i){]}^{n}n)$，期望得分100分。

新年的代码

出题人 Glaceon08, worse

数据 worse

题解 WuHongxun

算法一

$n\le 10$？

当然是$O(3^n)$状压爆搜啦！

算法二

我们大力猜结论！

每个位置只会不连续的变化两段！

dp就只需要$f_{i,j,k}$表示前$i$位处理完了，第$i$位先变成$j$让我们来继续操作后面的位，然后操作完后面的位之后我们把第$i$位从$S_i$变成了$k$，我们再回来用前面的位把它变成$T_i$的最小步数。

交一发，100分。

其实是有道理的啦...

myy（matthew99）丢给了我一个他猜完结论后的这题代码，虽然我没看懂：https://paste.ubuntu.com/p/6P7XZ6zT2W/

算法三

我们任意给$R,G,B$编号$0,1,2$，考虑我们每次操作，其实每次都是给相邻两位在模$3$意义下，一个$+1$，一个$-1$。（当然反过来不是每个$+1$,$-1$都能对应到我们的操作)

我们定义$s{a}_i=s{a}_{i-1}+a_i,s{b}_i=s{b}_{i-1}+b_i$，然后按照$s{a}_i=s{b}_i$的每个位置分段，那么每段在$mod3$意义下相等。

首先长度为$n$的每个段，至少需要$n-1$步操作才能完成，因为每个中间位置我们都需要把它左边和右边移成一样。

事实上我们可以构造出一个只需要$n$步的方案。考虑每次都至少复原一个字母，如果$S$开头两个是$GG$，那么无论$T$开头是$G$（第一个字母直接一样了），还是开头是$R,B$（一步操作之后可以复原第一个字母），显然都可以递归下去。

否则不妨假设$S$开头是$RG$，那么如果$T$第一个字母是$B$，那么一步操作即可。如果$T$的第一个字母是$R$可以直接递归下去。

于是剩下的唯一问题就是$T$的第一个字母是$G$的情况了，如果是$GR$，那么两步复原两个字母递归下去即可。

如果是$GG$，我们考虑处理剩下的位的时候把第二位变成$B$，然后前两位就是$RB$，最后一步变成$GG$

如果是$GB$，我们处理剩下的位的时候把第二位变成$R$，前两位就是$RR$，最后一步变成$GB$

这样我们就构造出了一段只需要$n$步的方案。

我们还需要证明两端之间是独立的，在上一个结论的基础上，这也不难。我们考虑每次在两端之间操作一下，相当于合并了两端。

假如本来两端长度是$a,b$，需要的次数在$[a+b-2,a+b]$之中，那么现在长度是$a+b$，至少需要$1+a+b-1=a+b$次，不会变成更优。

合并多段的情况一样可以这么证明。

接下来只需要检查$n-1$步是否合法了，因为这里每个位置都不会被操作超过两次，我们可以这么dp：

$f_{i,a,b}$表示dp完了前$i$个位置，在操作$i..n$位的过程中，需要第$i$个位置从$a$变成$b$的最小步数。

对于长度为$n$的段，如果这么dp之后存在一个答案为$n-1$的解，那么就加上$n-1$，否则加上$n$即可。

这样就可以有理有据的获得100分啦。

新年的投票

出题人 WuHongxun

数据和题解 WuHongxun

算法一

老师，我会爆搜！

先假设所有人不带标号，然后所有决策一共有$O(2^n)$种，爆搜每种情况，暴力取最好的情况，就会发现自己得了22分！

这是什么道理呢，如果所有人不带标号，那么我们可以这么构造：

如果多数掌握在$1$的人手里，所有人都应该投看到的奇偶性取反。

如果多数掌握在$0$的人手里，所有人都应该投看到的奇偶性。

唯一的问题是如果看到的$0$和$1$一样多怎么投，这时候可以按照多数是0投。

这样一来只有$\frac{n+1}{2}$的时候会导致错误，由斯特林公式易得总的正确率是$1-O(\frac{1}{\sqrt{n}})$

这样就可以过任务一啦！

此时得分$22$分。

算法二

如果不带编号的爆搜少女已经gg了...

那么我们就一定要利用上标号才行，任务二太难不会，任务三分数最低肯定最简单，我们先来看看任务三吧。

第$i$个人看看自己前面如果有人头上是$1$那么就投$0$票，否则就假设自己头上是$1$，然后投$2^i$票。

既然前面加起来只有$2^i-1$票，显然只有最后一个投的人有效。

这样就有$1-O(2^{-n})$的正确率了。

任务三就轻易解决了，果然是个送分提答呀。

此时得分$40$分。

算法三

我们再回头看看任务二。

我们把它所有人分成$1,2,4,...,2^{k-1}$的k组

从第一组开始，如果他之前没有$xor=1$的组，就按照自己$xor=1$来投。

如果前面有$xor=1$的组，就一半投0一半投1，把自己抵消掉。

这样只有全部xor = 1的时候会gg，这样的概率是$2^{-logn}=O(\frac{1}{n})$

所以做到了$1-O(\frac{1}{n})$的正确率。

此时得分$64$分。

算法四

现在就只剩下任务四了，看起来应该是需要一个对于任意的$k$都成立的做法。

每个人可以看到一个$(x_1,x_2,...,x_k)$的向量，那么他投票方案可以写成一个$k$次多项式，他在$(1-y_1,1-y_2,...,1-y_k)$的投票方案是$a_i$。那么这一项就是$(-1{)}^{\sum y_i}{a}_i(x_1-y_1)(x_2-y_2)...(x_k-y_k)$。

所有人的策略加起来也是一个k次多项式，最后的结果就是这个多项式带$x$进去之后值的符号。

反过来如果有一个k次多项式，那么我们把它的每一项分配给对应的人作为他们的投票策略，也是可行的策略。所以这两个问题完全等价。

我们如何找到一个这样的$k$次多项式呢？如果有$s$个1，由于$s$符合二项分布，我们可以试着把$[\frac{n-k}{2},\frac{n+k}{2}]$这个区间做对。(方便起见假设$n$和$k$同奇偶)

设$sgn(x)=-1/0/1$表示$x$的符号，$sgn(x+1/2-s)=(-1{)}^{[s>x]}$，所以用总的多项式取$p(s)=(-1{)}^{\frac{n-k}{2}}\prod _{i=0}^{k-1}(\frac{n-k}{2}+i+\frac{1}{2}-s)$即可

显然把$\sum x_i$带入$s$之后是一个$k$次多项式。这个策略在$[\frac{n-k}{2},\frac{n+k}{2}]$的区间内完全正确，在区间外也有一半的正确率。

此时得分$100$分。