惨啊。。感觉延续了 UOJ Easy Round 的传统变成 UOJ Super Hard Round 了？

本来这比赛里的一些题是打算出在 UOJ NOI Round 的，但是当时题目数量也比较紧张，类型也不太和 NOI 类似，感觉强行出出来只会被喷，而且当时时间也在二招边上。。所以鸽着鸽着就鸽没了啊。。

欢迎大家给 UOJ 投题啊，感觉管理员缺乏生产能力是真实痛苦啊。。

这个 T1 本来是看了投给 NOI Round 的几个题都有点难不太签到就想换个签到的，然后就去找网友要了个题，网友和我讲了个听起来很真实的做法，听起来也挺 T1 的就安排了上来。然后实现的时候发现。。是个和暴力拍不上的假做法。。

然后稍微修了一下做法，个人感觉难度没有太大增加结果看起来大家并不这么认为？

还有今天的题目背景都是 ztr 小哥哥写的~ 大家觉得题面怎么样呢，虽然主题似乎已经写过一次了。

绝对不鸽

from bulijiojiodibulido, 标程、题解、数据 by whzzt

算法一

当 $a=b=1$ 时，显然答案就是 $max(a_i)+1$。当然如果没看出来的话写个暴力也是可以的~

期望得分 $17$ 分。

算法二

考虑这是一个什么样的问题，实际上我们可以当成我们现在有 $\mathrm{\infty }$ 个数，其中只有 $n$ 个数的值是给定的，其他的数都是 $0$。我们要不断删去最大的 $B$ 个数，并将剩下的前 $n$ 个数的和增加至多 $A$。我们想要最大化历史最大值。

不妨枚举我们要最大化的是哪一个数，如果是第 $k$ 大的数，我们可以贪心求得最后的答案：我们将这 $k$ 个数取出来，在我们整个操作过程中，我们可以保证这些数的大小关系不发生变化(每个数不能加到超过前一个数)。问题变为最大化此时最终序列中剩下的数，也就是最小值。

显然我们每次增加的 $A$ 都一定会增加到最小的若干个数，因此我们可以进行模拟，这样的时间复杂度是 $O(k)$。

当 $n\le 100,A\le 100,a_i\le 100$ 时，可以证明 $k\le 3000$，因此模拟到 $3000$ 即可。期望得分 33 分。

算法三

可以发现这样一个事情：序列中超过 $\lfloor \frac{A-1}{B}\rfloor$ 的数是在不断变少的；而当序列中只存在不超过 $\lfloor \frac{A-1}{B}\rfloor$ 的数时，我们可以轻松将序列变为 $n-B$ 个 $\lfloor \frac{A-1}{B}\rfloor$ 以及 $B$ 个 $0$ 的形式：每次将 $B$ 个 $0$ 均变成该值，我们还能增加其他数。

因此当输入序列全 $0$ 时，问题就相当于是给定一个 $n-B$ 个 $\lfloor \frac{A-1}{B}\rfloor$ 以及 $B$ 个 $0$ 的序列的问题。

而此时我们也无法在每个数都不超过 $\lfloor \frac{A-1}{B}\rfloor$ 的情况下做更多的改进。那么我们仍然考虑算法二中的贪心，显然有 $k=xB+1$，不妨假设 $k_0$ 是第一个满足 $k>n-B$ 的 $k$，考虑贪心的过程，容易证明 $k\le k_0$，因为多一个 block 的操作实际上没有任何意义。

因此我们只需要检查 $O(\frac{n}{B})$ 个 $k$，这样暴力做的时间复杂度是 $O(\frac{n^2}{B})$，期望得分 44 分。

算法四

现在我们有了一个初始序列，但我们同样可以意识到，如果序列中不再存在超过 $\lfloor \frac{A-1}{B}\rfloor$ 的数，接下来的部分就和初始全是 $0$ 一样，我们就可以直接套用算法三来解决了。

不妨假设 $k_1$ 是第一个满足 $k>n$ 的 $k=xB+1$，我们同样可以证明 $k\le k_1$：

如果我们在 $k_1$ 之后再补一个 block，那么在我们不断给较小的数增加 $A$，删去较大的数的过程中，总会到达一个数字被填平的时刻：即和 $S$ 被均匀地分给 $n$ 个数。考虑最终的 $\frac{S}{n}$ 的值，显然必有 $\frac{S}{n}>\lfloor \frac{A-1}{B}\rfloor$，否则其答案不会比初始全 $0$ 的情况更优。

但我们多的这个 block 只会让我们在达到同一长度时多增加 $A$ 的值，首先考虑 $\lfloor \frac{S}{n}\rfloor >\lfloor \frac{A-1}{B}\rfloor$，在这样的情况下我们增加的 $A$ 还不够填平的耗费，因此均值减小，填平时间推迟，答案变小。而在 $\lfloor \frac{S}{n}\rfloor >\lfloor \frac{A-1}{B}\rfloor$ 的情况下，由于我们要多删去 $B$ 个数，因此这多余的不超过 $B$ 的收益也会被删去，均值不会增大，答案也不会增大。

有了 $k\le k_1$，我们就可以同样 $O(\frac{n^2}{B})$ 解决问题了，期望得分 71 分。

算法五

接下来问题变成了，如何对一个序列，维护每次将较小的数增加上总和不超过 $A$，并删去最大的 $B$ 个数的过程。我们可以二分求出在什么时候序列被填平了，即和 $S$ 被均匀分给 $n$ 个数的情况。而对于这样被填平的情况，我们可以再二分答案 $T$，并求出 $f_i$ 表示序列长度为 $i$ 时最小的满足条件的 $S$。

总时间复杂度 $O(n\log n\log A)$，期望得分 100 分。

没这种事

from djq_cpp, 标程、题解 by djq_cpp，数据 by whzzt

这个题的idea来源是这样的：某个名为 MagicSpark 的初一小朋友问我一道他看错的题，然后我发现可以数数，然后就变成现在这个题了。

接下来我们不妨假设 $n<m$。

算法一

暴力整个矩阵。时间复杂度 $O(2^{nm})$。

期望得分 0 分。

算法二

观察发现每个元素只会出现在四个位置上：原位置、沿中间一列对称、沿中间一行对称、沿中心对称。n, m 为奇数时中轴线上的元素单独处理。

直接对满足【每四个对称位置构成的 multiset 都相同的 $(S,T)$】计数，再乘上中轴线的贡献。

看起来很不靠谱，但是发现居然过了 subtask 1 和 2。

期望得分 13 分。

算法三

冷静一下，分析存在一种方案从 S 变成 T 的条件。

先假定 $n,m$ 均为偶数。

既然每个元素只会出现在四个位置上，那就可以把它们单独提取出来，并只考虑与它们有关的行/列 reverse 操作。

注意到每次行/列 reverse 都会使得这四个位置元素逆时针排列构成的置换奇偶性取反。那么，对于固定的 S, T，可以根据每四个对称位置元素置换的奇偶性列出一个有关【每行 reverse 操作奇偶性】和【每列 reverse 操作奇偶性】异或方程组作为存在操作序列的必要条件。（另外，当这四个元素有重复时，不会产生任何约束。）

与此同时，该方程组有解也是充分条件：把对应变量为 1 的行和列 reverse 之后，会发现每四个对称位置都构成一个偶置换。手动构造可以说明：通过行列 reverse 操作，一定可以在不影响其它位置的情况下对某四个对称位置作用任意偶置换。

另外，对称的两行（列）的变量可以合并。由此，每个异或方程只有两个未知数。联想到构建一张二分图。

枚举连边情况再计算答案。时间复杂度 $O\left(2^{\frac{nm}{4}}\right)$ 。

结合算法二，期望得分 23 分。

（上述推导也解释了算法二的正确性。）

算法四

算法三最后一步明显可以不暴力。

长度为 4 的奇偶置换数量是相同的，所以对于每一种连边情况，贡献就是【每条边填上 0 1 的方案数】乘上【异或方程构图与这张图相同且边上全填 0 的方案数】。前者就是 $2^{n+m-\text{联通块个数}}$, 后者则是 $F_0(k{)}^{\text{边数}}\ast F_1(k{)}^{nm–\text{边数}}$，其中 $F_0$, $F_1$ 分别是的有约束和无约束（即有重复） pair(四元组, 四元组) 个数。

令 $d{p}_{i,j}$ 表示 $n=i,m=j$ 时的答案。转移减法原理，复杂度 $O(nm)$。总复杂度 $O(n^2{m}^2)$ 。

结合算法二，期望得分 45 分。

算法五

当 $n$ 很小时，可以枚举 $n$，对 $m$ 那一维进行多项式优化。

时间复杂度 $O(n^{2}m\log m)$。

结合算法二、四，期望得分 65 分。

算法六

把算法四贡献中的 $F_1^{nm}$ 除掉（最后再乘），再令 $F_2=\frac{F_0}{F_1}$。

注意到算法四的本质，是对【所有 $n-m$ 二分图的 $F_2(k{)}^{\text{边数}}$】关于 $n,m$ 的二元生成函数取 $\ln$, 除以 $2$ 再取 $\exp$。

这其实就是开方。

关于二元多项式开方：

方法一：直接牛顿迭代，像一维一样。需要二元多项式乘法。时间复杂度 $O(nm\log (n+m))$, 常数巨大。主元并二维牛顿迭代同理。

方法二：主元 $x[0,n)$，使用 $O(n^2)$ 的暴力 $\text{sqrt}$。看作一个关于多项式的 $dp$，发现转移需要 $O(n)$ 次 $m$ 次多项式乘法。记录这些多项式在 $[0,2m)$ 的点值可以做到 $O(n^{2}m+nm\log (m))=O(n^{2}m)$。

虽然方法一复杂度较小，但其实被方法二吊打（也许真实原因是我常数太大 →_→）。 其实我一开始没有考虑方法二。多谢 _rqy 神仙提(diao)醒(da)（

时间复杂度 $O(nm\log (n+m))$，期望得分 100 分。

在路上了

from peehs_moorhsum, 标程、题解 by peehs_moorhsum，数据、交互库 by whzzt

在路上了。

啊呜..这题其实是..IMO培训题魔改的

我对这题还比较满意。emmm..可能因为我觉得，算法竞赛更应当是思维竞赛，而非码力或知识竞赛？

而这大概算比较纯粹的思维题了？希望这种题在CNOI中能多一点

算法一

询问全图，用各种暴力找最长链

期望得分 0 分

（因为许多点问不了全图，能问到的图 $n$ 太大了）

但由于我们造数据时，默认 $n$ 为 $\frac{3k}{2}$ 上取整，所以这个做法过了subtask 1

算法二

想到出题人很菜，你开始冷静分析

假如不考虑 $\frac{3k}{2}\le n$ 的条件，那你可以一直调用find_longer_path，直到找到最长链

所以你会了一个多项式求最长链的算法！

尽管图有特殊性质，但这看上去很不科学？

所以你大胆猜结论，当 $\frac{3k}{2}\le n$ 的时候，一定有长为 $k$ 的同色链

于是你只读入前 $\lceil \frac{3k}{2}\rceil$ 个点内部的连边，然后用dp求最长链，即可有理有据地通过subtask1

期望得分：13分

算法三

由于你是未来的图灵奖得主，你求最长链的水平十分高超

在算法二的基础上，加入一些奥妙重重的最长链算法（比如搜索），可以通过subtask2

期望得分：20分

算法四

考虑 $n=2k$ 的部分分

假如你能知道每条边的颜色，你可以用红边构造出一个生成森林，每个联通块是一棵dfs树，且满足$1$是$2$的父亲，$2$是$3$的父亲，……，$k-1$是$k$的父亲，$1$是根

如果有某棵树的深度大于等于$k$，已经结束 （根节点深度为$0$）

否则将其他所有点按深度分成$r$组（未出现在树上视作深度为0），设为$S_1$到$S_r$，其中$S_i$的深度是$A_i$

则你考虑序列 ($S_1$中所有点)，($A_1+1$号点)，($S_2$中所有点），（$A_2+1$）号点，……

由dfs树的性质，容易发现这是一条长度 >= k 的蓝色路径

可以通过subtask 3

期望得分：15分

算法五

结合算法三、四，可以得到40分

在算法四的基础上，假如有特殊的方法，不需要询问所有边便可构建出类似dfs树的东西，那么可以通过subtask 4

算法六

称 $2$ 到 $k-1$ 为红点（注意，不是 1 到 k ）

称 $k+1$ 到 $3n$ 为蓝点

定义“交错路径”为一条全蓝的简单路径，满足第一个点和最后一个点都是蓝点，且红蓝点交错 （单个蓝点也算）

交错路径的大小为路径上蓝点数目

我们维护两条交错路径 $u,v$

初始时，各取一个蓝点即可

任何时刻，记$u,v$大小分别为$a,b$

(1)如果 $2(a+b)\ge k$

则 $1ukv$ 构成一个大小为$2(a+b)$ 的蓝圈，称为 $s$

如果 $2(a+b)>k$ 已经结束

否则 $2(a+b)=k$

考虑$1$到$k$中相邻两个不属于$u,v$的点 $i,i+1$

考察他们到$s$上同一蓝点r连边，容易构造出长为$k$的蓝路 或者 $1\dots iri+1\dots k$的红路

这一部分的询问次数是 $2$

(2)如果 $2(a+b)<k$

我们试图让 $a+b$ 变得更大

利用 $(a+b)<k/2$ 容易发现，存在 $1\sim k$ 中的相邻两点，均未在$uv$中出现过 记作$ii+1$

取不在$uv$里的蓝点 $r$ （由于$a+b+k<\frac{2k}{3}$，这可以做到）

一种暴力的想法是，检验 $r$ 到 $1,k$ 的连边

记$uv$的一个端点为$xy$，检验$r,x,y$到$i,i+1$的六条连边

如果有某个蓝点 $g$ 到 $ii+1$连边都是红色 则 $12\dots igi+1\dots k$为长度为$k$的红色路径

故不妨 $rxy$ 到 $ii+1$ 均连至少一条蓝边 故有其中两个点向同一个点 $s$ ($s$ 为 $i$ 或 $i+1$）连蓝边

如果这两个点是 $xy$ 则 $u,v$ 可通过 $s$ 串联起来 取新的 $u$ 为串联后的路径，新的 $v$ 为 单点 $r$，则$a+b$增加$1$

如果这两个点是 $rx$ 则 $r$ 可加入到 $u$ 中

如果这两个点是 $ry$ 则 $r$ 可加入到 $v$ 中

总询问次数是 $8(k/2-2)+4+2$

可以通过subtask 1 至 subtask 5

期望得分：70分

算法七

容易发现，算法六的瓶颈在于扩大u v链时询问过多

我们试图精细一些。

我们默认 $r$ 到 $1k$ 连边为蓝色，默认$rxy$到$i,i+1$均连至少一条蓝边（求出最后的蓝圈时，检验一遍所有边均为蓝色即可）

先询问$xy$ 到 $i$ 的连边颜色

如果均为红色，将$uv$通过$i+1$串联，取新的$v$为$r$即可

如果均为蓝色，将$uv$通过$i$串联，取新的$v$为$r$即可

这两种情况下，均只询问了两次。

如果一红一蓝，不妨$x$红 $y$蓝

我们询问$r$到$i+1$的颜色

若为红色，将$r$ 通过 $i$ 与 $y$ 连在一起

若为蓝色，将$r$ 通过 $i+1$ 与 $x$ 连在一起

这两种情况下均询问了三次，但蓝圈上均有一条边不用被验证

故总询问次数不超过 $k+(k/2-2)\ast 2+2=2k-2$，可以获得100分。