mayaohua的博客还记得我们在 UOJ 征题公告 里承诺的“神秘小福利”吗？它来了！站长 vfleaking 为所有 UOJ 管理员和出题人免费准备了 UOJ 定制充电宝！
在众多出题人的帮助下，UOJ 举办了一场场高质量的比赛，选手们在比赛中相互切磋较量，分享有（du）趣（liu）的 idea。UOJ 的比赛题目都是由管理员和出题人无偿准备，“用爱发电”，大家都被 UOJ 的精神 所感染，为了自己对 OI 的一份热忱，献出自己的力量。
如果你是出题人或管理员，可以用 UOJ 私信或 QQ 联系 UOJ 站长 vfleaking 来领取充电宝。如果你还没有参加过 UOJ 出题工作但希望拿到充电宝，欢迎联系管理员给 UOJ 投题。
祝愿所有出题人和管理员生活和事业一帆风顺，马到成功，也祝愿 UOJ 蒸蒸日上，再创辉煌！
首先作为管理员向大家谢罪，由于我们的准备失误（主要是我的锅），导致 Day2 的比赛准备出现了很大问题，D2T1 的数据甚至在比赛结束前也没有完全准备好，导致延误了评测时间，在此为造成大家不便表示歉意 
from Itst，数据，标程，题解 by Itst
超级良心的签到题！
我会暴力！枚举每次 push 的情况，复杂度 $O(2^kk)$，可以通过子任务一获得 $20$ 分。
$c_r=c_b=k$ 没有任何限制。直接枚举红颜色的元素个数，答案为 $\sum_{i=0}^k \binom{k}{i}i(k-i)^2$，直接计算即可。可以通过子任务六，结合算法一获得 $25$ 分。
对于栈操作序列，我们可以构造一个树结构：初始只有一个节点，且有一个指针指在该节点。遍历每个操作，遍历到 push 操作时在当前指针处新加入一个儿子，并将指针指在该新加入节点处；遍历到 pop 操作时将指针移到当前指的节点的父亲处。可以发现这棵树很好地描述了栈的状态：每个时刻栈里面的元素对应树上从根到某个节点的一条链。那么限制就是每条链上 R 和 B 节点的数量不能超过 $c_r$ 和 $c_b$。注意根节点不需要选择 R 或者 B。
那么显然有暴力 DP：$f_{i,sr,sb,lr,lb}$ 表示处理了点 $i$ 的子树，子树内有 $sr$ 个 R 节点、$sb$ 个 B 节点、向下的链中 R 个数最大是 $lr$、向下的链中 B 个数最大是 $lb$ 的情况下的方案数。
当然直接暴力记录状态和合并是比较难通过的。有一些显然的优化：$lr$ 与 $lb$ 维度可以前缀和优化；最后 $sr+sb=k$ 所以可以省去一个。这样优化以后容易做到 $O(k^5)$ 或 $O(k^4)$，可以通过子任务二或三，结合算法二分别获得 $40$ 和 $55$ 分。
对于上述暴力 DP 有两个优化方向。同时使用两个优化方向则容易做到 $O(k^2)$，而仅使用一个则只能做到 $O(k^3)$。因此题解中不特别标注 $O(k^3)$ 做法。
首先考虑处理每个方案的贡献。设 $\mathrm{col}(i)$ 表示节点 $i$ 的颜色。注意到 $p_rp_b^2 = \sum\limits_{\mathrm{col}(i) = R}1 \sum\limits_{\mathrm{col}(i) = B}1 \sum\limits_{\mathrm{col}(i) = B}1 $，也就是有序的选出 $1$ 个 R 点和 $2$ 个 B 点的方案数。
因此可以把对应 $sr$ 和 $sb$ 的状态删去，改为 $f_{i,lr,lb,0/1,0/1,0/1}$，其中 $lr$ 与 $lb$ 意义不变，三个 $01$ 分别表示一次选 R 和两次选 B 分别是否选中元素，使用背包合并这些维度，并且在每个节点确定颜色的时候确定对应位置的选择是否选它。
第二个优化方向是状态记录维度的翻转。更改 $lr$ 与 $lb$ 的意义为祖先中 R 和 B 节点的数量，合并和单点状态选择的转移都是比较简单的。值得注意的是状态翻转过后，对于 $f_x$ 总有 $lr + lb = dep_x$，因此其中一维可以直接省去，得到一个 $O(k^2)$ 的算法。
最后注意根节点不需要选择 RB 即可。可以通过所有子任务获得 $100$ 分。
from jiqimao & mayaohua，数据，标程，题解 by mayaohua
对于 $n\leq 7$ 的数据，我们可以暴力枚举染色方案，然后树哈希验证是否与之前枚举的方案均不同构（本质不同），树哈希的时候需要把颜色也加进去。
时间复杂度取决于你的树哈希算法，在 $O(n!\cdot n)$ 到 $O(n!\cdot n^3)$ 之间，期望得分 $10$ 分。
对于一条链的数据，容易发现自同构只有翻转一种，因此用 burnside 引理很容易得到答案就是 $\frac{\binom{n}{k}+[k=1 \ \mathbb{and} \ 2\not\mid n]}{2}$。
时间复杂度 $O(n)$，期望得分 $5$ 分。
考虑比较靠谱的做法，注意到两棵带颜色的子树同构，那么它们忽略颜色后也必定同构，这提示我们考虑对子树 DP。
注意到颜色 $1$ 的位置令树变为有根树，那么我们不妨枚举所有作为根树不同构的节点，钦定它们染颜色 $1$ ，以它们为根分别 DP 计算答案。为了方便，我们采用 EGF 描述这个 DP，令 $f_i(x)$ 表示以 $i$ 为根子树关于染颜色点个数的 EGF，那么如果 $i$ 的所有儿子为根子树互不同构，显然有 $f_i(x)=(1+x)\prod\limits_{u\in son_i}f_u(x)$，而对于同构的子树，不妨设单一棵的 EGF 是 $g(x)$，总共有 $k$ 棵，那么我们可以得到总的 EGF 是 $\sum\limits_{i=0}^{k} \frac{(g(x)-1)^i}{i!}$，对这个式子的理解是我们枚举非空的子树个数 $i$ 并填进去，然后当然要除去同构子树带来的影响 $i!$（你也可以考虑子树个数无穷多的情况帮助理解，这时候是 $e^{g(x)-1}$）。
那么我们直接暴力计算上面的 DP，用平方的暴力多项式乘法，用树上合并背包的套路可以分析出单次 DP 是 $O(n^2)$ 的，由于要枚举根总复杂度是 $O(n^3)$，结合算法二期望得分 $35$ 分。
算法三的一个复杂度瓶颈是我们枚举了所有的根，这是因为原来的树是无根树。考虑无根树同构的套路，我们尝试枚举重心来优化。
若树有唯一重心，那么可以直接以 $rt$ 定为根，对有根树进行计算，这样两个同构的方案此时作为有根树仍然是同构的。于是我们可以转成有根树，跑一次算法三的 DP，注意此时我们不假设根染颜色 $1$。
若树有两个重心，一定是一条边的两端，且两边子树大小相等。那么我们可以删去这条边，分别以两个重心为根做一次上面的算法，若两边子树不同构，显然可以直接乘起来，否则令一侧的 EGF 是 $g(x)$，总共就是 $g(x)+\frac{(g(x)-1)^2}{2}$，你也可以理解成是在边中间加了一个虚点，并以虚点作为唯一重心计算。
同样使用暴力多项式乘法，时间复杂度是 $O(n^2)$，结合算法二期望得分 $45$ 分。
考虑对算法四进行优化。注意到算法三时提到的一个重要性质，若对某个点 $i$ 的儿子 $u$ ，不存在另一个 $i$ 的儿子 $v$ 使得它们的子树同构，那么 DP 转移时我们在 $f_i(x)$ 会直接乘上 $f_u(x)$。
那么我们若对有根树做一个特殊的轻重链剖分——只保留严格重儿子，由于每个严格重儿子都不会有另一个儿子子树与它同构，那么转移是直接乘上去的。再考虑优化多棵同构子树的合并，这要求我们对一个 $g(x)$ 和一个 $k$ 快速求出 $\sum\limits_{i=0}^{k}\frac{(g(x)-1)^i}{i!}$，容易发现这个式子可以对指数 $i$ 分治 FFT，令 $deg(g(x))=m$，则单次计算的复杂度为 $O(mk\log (mk)\log k)$。那么我们递归计算，只在链顶处保留真实的 $f_i(x)$，并对链上每个节点，若它有出现次数 $> 1$ 的子树，用上面的方法计算出合并后的 EGF，这样只需要把所有跟这条链相关的 EGF 全部乘起来（链上每个点的 $1+x$ 也要计入）就能得到链顶的 EGF 了，乘起来的时候同样分治 FFT，但这里更优秀的做法是用哈夫曼树计算一个最优合并顺序并乘起来。
考虑这样做的时间复杂度，不难发现这个做法实际上是一个全局平衡二叉树上的分治 FFT（合并多个同构子树时的 $\log k$ 可以理解成子树大小每次加倍），因此总时间复杂度是 $O(n\log^2 n)$，期望得分 $100$ 分，可以通过。理论上在链上把 EGF 乘起来的时候如果直接对下标分治 FFT，最坏时间复杂度是 $O(n\log^3n)$，但常数非常小，同样可以通过。如果你某一步写挂了或处理错了，可能只能得到 $65\sim 85$ 分。
from p_b_p_b，数据，标程，题解 by p_b_p_b
在 UOJ 上出的第一道题！
题面和样例都出了点小锅，不过应该没造成太大影响吧。
哎嘿，出题人没在样例里放无解的情况，暗示一定有解？
直接输出初始树的 dfs 序。
期望得分：$0$。
我会爆搜！
从给出的 $a$ 倒着搜索，复杂度 $O(n!\text{ poly}(n))$。第一个包只有 $n\le 8$，所以应该可以轻松通过。
期望得分：$10$。
考虑倒 Y 的情况，此时 ddm 序只有两种，我们分别判断。
设 $p$ 有两个儿子，分别引出链 $L_1$ 和 $L_2$，且 $L_1$ 的 ddm 序先于 $L_2$。设 $1\sim p$ 的链为 $L$。
因为只能把父亲较小的 $b$ 往下换，所以容易发现 $L_2$ 的 $b$ 一定无法进入 $L_1$ ，最优策略一定是先在 $L\cup L_1$ 上操作，把 $L_1$ 调整为 $a$，然后再操作 $L_2$。
所以一个 ddm 序合法当且仅当 $L_1$ 的 $a$ 全部在 $L\cup L_1$ 的 ddm 序中出现过。
期望得分：$30$。结合算法一期望得分 $40$。
考虑保证合法解是给定 ddm 序的情况。（我只说了合法当且仅当给定 ddm 序合法，没要求 std 也输出给定 ddm 序啊！）
这提示我们必须找到判断一个 ddm 序是否合法的方法。
通过打表手玩找规律 and/or 严谨证明，可以发现：对于每一个 $i$ ，把 $\ge i$ 的数替换为 $1$， $ < i$ 的数替换为 $0$，那么一个 ddm 序合法当且仅当在每个 $i$ 的 $01$ 情况中合法。
如何判断 01 情况是否合法呢？从 $a$ 倒着推，贪心地往下塞就好了。写的好看一点就是合法当且仅当对于每个 $x$， $x$ 子树在 $a$ 中的 $1$ 的个数不超过在 ddm 序中的 $1$ 的个数。
暴力实现复杂度 $O(n^2)$ ，用数据结构优化即可做到 $O(n\log n)$ 。
期望得分： $20\sim 35$。结合算法一 、算法二期望得分 $75$。
我们来胡乱手玩一下。
在草稿纸上随便画一棵树，标一个从左到右的 ddm 序，随便交换一下，然后看自己能否构造出原来 ddm 序交换过来的方法。
无从下手？那就从最左边的叶子开始吧。
我们希望直接把最左边的叶子的 $a$ 得到，所以操作空间很小，只能把祖先里的某一个 $b$ 拉过来。
这时候就会发现，好像我不管怎么交换，也换不出除了祖先的 $b$ 以外的值啊？
随便证明一下：这里是叶子，所以这个位置的 $b$ 在交换过程中单调不增，也就只能变成祖先的 $b$。
我们当然也不希望有无用的交换，所以把某个祖先的 $b$ 拉过来之后仍然保持祖先的 $b$ 有序。发现现在把这个叶子直接删去也不会出什么问题了？
于是就得到一个构造交换顺序的方法：设 $low_x$ 为 $x$ 子树中 ddm 序的最大值，把所有点按 $low$ 从小到大排序，相同的点按深度从大到小排序，然后一个一个做。每次做的时候把祖先的一个 $b$ 拉下来，拉的过程中仍然保持祖先的 $b$ 有序。
仔细分析一下这个构造方法什么时候能构造出解。发现只要对于每个 $x$ 有 $low_x\ge a_x$ ，就一定能构造出来！
而因为子树内的最大值单调不增，所以 $low_x < a_x$ 时必定无解！
于是发现一个 ddm 序合法，当且仅当 $low_x\ge a_x$ 。这也可以用来证明算法三的正确性。（也许算法三能够用某种方法推到这个结论？）
那么唯一的问题就是怎么构造一个合法的 ddm 序了。
考虑 DP ：设 $dp_x$ 表示 $x$ 的 ddm 序至少是多少，才能保证子树内全部合法。显然应该按照 $dp$ 值从小到大的顺序遍历 $x$ 的儿子，所以很容易转移。
最后判断 $dp_1$ 是否等于 $1$ 即可。
复杂度 $O(n\log n)$ ，期望得分：$100$。
from matthew99，标程 by matthew99，数据，题解 by mayaohua
由于长度为 $2$ 的串可以翻转，我们不区分原串和翻转后的串。
考虑先全排列暴力枚举 $p$，得到字符串的顺序。接下来我们需要寻找一个合法的 $q$，考虑从两边往内推逐个确定每位字符，注意到如果当前位置两边至少有一个字符已知，那么能继续推下去，否则可以发现除了两个相同的串外，下一步的方式至多只有一种，而两个相同的串只要不同向即可。
时间复杂度为 $O(n!\cdot n)$，期望得分 $15$ 分。
考虑扩展算法一的思路，同样从两边交替往中间推，这只需要记录一下当前已经用过的串和当前可能多出来的一个字符，可以用状压 DP 实现。
时间复杂度为 $O(2^n\cdot nm)$，期望得分 $35$ 分。
对于 $l_i=2$ 的数据，显然只需要把相同的串不同向对称放就好，但注意有个特殊情况：如果有奇数个串，正中间可以放一个形如 $11$ 的。
时间复杂度为 $O(n)$，期望得分 $10$ 分。
考虑算法一中的确定过程，不难发现除了最后中间的一段以外，我们在两边反复做匹配两个串的过程，即我们构造了两个相同的字符串。注意到这样的一个段，要么是两个长度为 $2$ 的相同串，要么是由长度为 $1$ 的串开始，然后交替扩展直到遇到另一个长度为 $1$ 的串。例如，给定串集合 $\{1,12,23,34,4\}$，我们可以构造出 $1\ 23\ 4$ 和 $12 \ 34$。
由于字符串长度不超过 $2$，我们考虑这样一个建图：建立 $m+1$ 个节点，其中节点 $0$ 为源点，节点 $1\sim m$ 代表 $m$ 个字符，对每个长度为 $1$ 的字符串 $a$，我们连边 $(0,a)$，对每个长度为 $2$ 的字符串 $ab$，我们连边 $(a,b)$。那么发现每个算法一中交替扩展得到的段，对应一条恰好经过 $0$ 一次的边不重复回路。
对于 $L$ 为偶数的数据，答案回文串可能是由两个相同串其中一个翻转后拼起来，也可能在中间有一个形如 $11$ 的串。对于前者，显然是由若干交替扩展得到的串和若干成对出现的长度为 $2$ 的串组成，在图上看，这就是一个包含 $0$ 的欧拉回路和若干出现偶数次的边，因此有解当且仅当 $0$ 所在连通块有欧拉回路（每个点度数为偶数），且其它连通块每条边出过偶数次（包括自环）。对于后者，我们可以选择一个其它连通块的自环放在中间，这只需找到出现奇数次的自环。
对于 $L$ 为奇数的数据，用类似的方法可以发现要求是 $0$ 所在连通块有欧拉道路（即恰有两个奇度点，显然其中一个是 $0$），而此时其它连通块只能每条边都出现偶数次，这时候构造的话就是中间放一条从另一个奇度点到 $0$ 且仅经过 $0$ 一次的路径，这对应一个长度为奇数的回文串，剩余部分构造和偶数类似。
时间复杂度为 $O(n+m)\sim O(n\log n+m)$，期望得分 $100$ 分，需要比较注意细节，如果写挂的话可能只有很低的分数。
Bonus：如果不允许翻转长度为 $2$ 的串，是否存在多项式复杂度算法或可证明 NP 完全性？
from skip2004，数据，标程，题解 by skip2004
为了方便，下文中的 $w = \log v$。
我们用线段树维护这个序列，每个点维护区间最大值与区间的按位或。 一个点最多会被除法改变 $w$ 次，每次改变后可能会有一些与的改变，最多 $w$ 次，因此最多改变次数是 $O(w^2)$，我们在线段树上搜索修改，复杂度毛估估是 $O(nw^2\log n)$。
算一算发现一个大包都过不去，但能过两个特殊性质包：$2, 4$。
仔细分析，对于这两个包，可以发现线段树上锁定区间后的搜索过程，每个线段树节点都最多被搜索 $w$ 次。因此复杂度为 $O(nw + q \log n)$。
我们发现上述算法毫无前途，我们总得把一个修改打标记吧。
容易发现除法打标记还要算和，非常困难，于是我们对与这个操作打标记。与打标记还要算和，我们用经典的方法，开一个 $w$ 长度的数组记录：对于每一位这个区间有多少个数这一位是 $1$。此时线段树上这一个节点的标记下传，信息上传等操作复杂度变为 $O(w)$，总复杂度分析得 $O(nw^2 + q\log n *w)$，看起来还是没救。
我们发现这个算法在搜索过程中，在靠近叶子处最消耗时间，而这些地方我们数组里数都不大，我们考虑进行优化。
我们把这个 $w$ 个数列成一个表格，每行 $\log len$ 个数表示每个数的二进制位。
此时我们发现，我们可以用 $\log len$ 个压位变量来存储这个表格的每一列。至于信息上传，我们可以模拟加法，时间复杂度 $O(\log len)$，对于打标记，我们发现是某些行的数清 $0$，也就是每列与上其标记，也可以 $O(\log len)$ 解决，算带权和也可以轻松解决。
我们再来分析一下复杂度，锁定区间部分复杂度 $O(q \log^2 n)$，搜索过程就是 $\sum \log len * w$，其中 $\sum \log len$ 可以由递归式 $f(n) = 2f(\frac{n}{2}) + \log n$ 使用主定理得出为 $O(n)$，故总时间复杂度为 $O(nw + q \log^2 n)$。
from Itst，数据，标程，题解 by Itst
读懂题意后可以发现图上总共只有 $q+2$ 个点有意义。两两询问出最短路，需要 $\frac{(q+2)(q+1)}{2}$ 次询问。因此在前三个子任务中可以暴力询问求出两两之间的最短路。（谢罪：之前这里算错了导致子任务三 $q$ 大了 $1$。）
接着只需要枚举一个长度为 $q$ 的 $01$ 序列表示每一次紧急事件发生时需要调度哪一架飞机到达对应机场，复杂度 $O(2^q)$，可以通过子任务 $1$ 获得 $10$ 分。
注意到紧急事件序列每个事件的决策只和两架飞机此时所在的机场编号相关，故考虑使用动态规划解决。
设 $f_{i,j,k}$ 表示前 $i$ 个客流紧张事件已经结束，此时一架飞机停留在机场 $j$，一架飞机停留在机场 $k$，满足该条件下的最大调度价值和。转移即枚举哪一架飞机移动到 $P_{i+1}$ 转移到 $f_{i+1,P_{i+1},j}$ 和 $f_{i+1,P_{i+1},k}$。
复杂度 $O(q^3)$，可以通过前两个子任务获得 $25$ 分。
对于上述动态规划，可以注意到处理完第 $i+1$ 个客流紧张事件后，后两维总是有一维等于 $P_{i+1}$。因此可以把这一个确定的维度压掉。
设 $f_{i,j}$ 表示前 $i$ 个客流紧张事件结束时一架飞机在 $P_i$ 另一架飞机在 $j$ 时的最大调度价值和。$f_{i,j}$ 有两个转移：一个是加上 $distance(P_i,P_{i+1})$ 转移到 $f_{i+1,j}$，另一个是加上 $distance(P_{i+1},j)$ 转移到 $f_{i+1,P_i}$。
复杂度 $O(q^2)$，可以通过前三个子任务获得 $40$ 分。
子任务四是留给大家玩玩乱搞的。实际上随机数据的强度非常非常的弱。
一个想法是考虑魔改上面的 DP，可以注意到除了 $f_{i+1,P_i}$ 以外其他部分的转移是全体加一个值。全体加可以滚动数组后打标记处理，所以只需要优化 $f_{i+1,P_i}$ 的转移。很容易得到一些贪心策略，如：
实际上它们都可以通过随机数据可以获得 $10$ 分，结合算法三可以获得 $50$ 分。
为了后文描述方便，我们把编号区间扩充为 $[1,2n]$，其中编号 $n+i(1 \leq i \leq n)$ 对应的机场与编号 $i$ 对应的机场一致。
证明：注意到题目给出的图是平面图，同时编号按照顺时针顺序编号，且所有边都在多边形内部，因此 $distance(u,x)$ 对应的最短路径要么经过 $v$ 或 $y$，要么将多边形分成了两个部分，$v$ 和 $y$ 在不同的部分。这样 $distance(u,x)$ 与 $distance(v,y)$ 对应的两条路径必定有交点，不妨设交点为 $r$。则利用最短路的三角形不等式有
$$\begin{aligned}& distance(u,x)+distance(v,y) \\ = & distance(u,r) + distance(x,r) + distance(v,r) + distance(y,r) \\ = & (distance(u,r) + distance(y,r)) + (distance(x,r) + distance(v,r)) \\ \geq & distance(u,y) + distance(v,x) \end{aligned}$$
利用这个长得像四边形不等式的东西可以做什么呢？
考虑一个长度为 $q$ 的 $01$ 序列 $a_1,a_2,\cdots,a_q$，$a_i$ 表示两架飞机中的哪一架飞到 $P_i$ 机场解决紧急事件。显然这样的每个序列对应着每一个调度方案。对于对应最优调度方案的序列，我们有定理：
证明：对于一个最优序列，若 $\exists j \geq i+1$ 满足 $a_j \neq a_i$，则一定是某一架飞机直接从 $P_i$ 调度到 $P_{i+1}$，另一架飞机直接从 $P_k$ 调度到 $P_j$，此时 $k < i < i+1 < j$，即 $P_k \leq P_i \leq P_{i+1} \leq P_j$。由引理有 $distance(P_k,P_{i+1}) + distance(P_i,P_j) \geq distance(P_k,P_j) + distance(P_i,P_{i+1})$。故将序列中下标 $\geq i+1$ 的所有位置的值反转后可以得到一个不劣的方案。同时容易说明按照某种顺序不断进行翻转总是能得到一个满足定理条件的序列。
这也就说明最优序列一定满足：除了一段后缀都由一架飞机搞定以外，剩余部分一定是 $01$ 交替的。显然这样的序列只有 $O(q)$ 个，且在所有这样的序列中第 $i$ 个事件只会由 $P_{i-1}$ 或 $P_{i-2}$ 调度飞机。因此只需要 $2q$ 次询问，然后枚举后缀长度并动态维护价值和，取最大值即可。复杂度 $O(q)$，可以通过子任务 $5$，结合算法三、四可以获得 $75$ 分。
与此同时，这样的序列性质也说明了为什么把算法四的第二种 DP 乱搞做一些小小的修改即可通过本子任务。（真的不是数据水！）比赛开始一小时后就有选手 900B 怒拿 $75$ 我大为震撼！
注意到上面的引理是一个四边形不等式的性质，自然地想到使用决策单调性优化 DP。
最重要的问题是权值矩阵的设计。如果直接设计权值矩阵 $A = \{a_{i,j} = distance(i,j)\}$，其 DP 转移是不满足决策单调性的。因为使用决策单调性的权值矩阵要求 $\forall u \leq v, x \leq y$ 都有 $a_{u,x} + a_{v,y} \geq a_{u,y} + a_{v,x}$，但是在没有约束 $x$ 与 $v$ 的大小关系的情况下引理并不成立。
解决办法是：在矩阵中填入若干 $-\infty$ 使得 $\forall u \leq v, x \leq y$ 的变量取值条件变为 $\forall u \leq v \leq x \leq y < u + n$ 的条件。
具体考虑 $n \times 2n$ 的权值矩阵 $W = \{w_{i,j}\}$，其中 $w_{i,j}$ 在 $j \in [i,i+n-1]$ 时取值为 $distance(i,j)$，否则为 $-\infty$。可以发现此时在 $v > x$ 或 $y \geq u+n$ 的情况下 $a_{v,x} + a_{u,y} = -\infty$，因此 $a_{u,x} + a_{v,y} \geq a_{u,y} + a_{v,x}$ 不等式总是成立。所以需要判断的只有 $\forall u \leq v \leq x \leq y < u + n$ 的情况，而利用引理不等式也是总是成立的。所以这个矩阵满足四边形不等式。
这样我们对 $f_{i,j}$ 数组的 $i$ 维度滚动数组并维护全体加法标记后，设 $f(y) = \max_{x=1}^n W_{x,y}+f_x$，则 $f_{i+1,P_i} = \max(f(P_{i+1}),f(P_{i+1}+n))$。
同时对于每个 $y$，设 $x_y$ 表示取到 $f(y)$ 的最小行编号 $x$，则 $f$ 固定的情况下 $x_y$ 是随着 $y$ 的增大单调不降的。这意味着我们可以对于 $f$ 直接维护 $x_1,x_2,\cdots,x_{2n}$。其构成了至多 $n$ 个区间，使用 set 维护这些区间。
每一次产生 $f$ 数组的更新（也就是 $f_{i+1,P_i} = \max(f(P_{i+1}),f(P_{i+1}+n))$）时，滚动数组中 $f_{P_i}$ 的值产生了变化且一定不会变小，因此其在 $x_1,x_2,\cdots,x_{2n}$ 序列上会占据一段新的区间，且新占据的区间一定包含之前占据的区间。在 $x_1,x_2,\cdots,x_{2n}$ 上二分出 $P_i$ 占据的区间的新的左端点和右端点即可。注意每一次遇到紧急事件，对于 DP 数组的其他部分都用打标记的方式更新了，所以每一次紧急事件都只需要更新一次该序列。
最终只需要约 $4q \log 2n + 3q$ 次操作即可完成动态规划数组的更新与每次更新之后 $x_1,x_2,\cdots,x_{2n}$ 的维护。可以通过子任务六获得 $75$ 分，结合算法五可以获得满分。
转眼间又是一年 NOI 了，为了帮大家备战 NOI，延续 UOJ 的传统保留项目，UOJ NOI Round #5 将在 7 月 17 号到 7 月 19 号隆重举行！
为了庆祝中国队在 IOI 2021 包揽前四和 UOJ 管理员 peehs_moorhsum AK IOI，这次 UNR 将以大D米参加 UOI 为主题！
笔试模拟将于 7 月 17 日晚 19 点开始，将进行半个小时。
Day 1 的比赛将于 7 月 18 日上午 8 点半开始，将进行五个小时，共三道题。
Day 2 的比赛将于 7 月 19 日上午 8 点半开始，将进行五个小时，共三道题。
比赛的难度将比 NOI2020 略微简单一些，相信对绝大部分选手来说题目是具有一定的挑战性的。
题目中还有着一道提交答案题和一道交互题，大家可以放心食用。
UPD：由于某些原因，提交答案题消失了。
这次拯救 UNR 的出题人有：
Itst,jiqimao,p_b_p_b,matthew99,skip2004
这场比赛除笔试外将计入 rating。
我们相信这场比赛，可以给拼搏于 AK NOI 的逐梦之路上的你，提供一个有力的援助。
这次比赛将会根据三次比赛的总分进行排序（如果存在同分将以两天的罚时总和作为第二关键字），其中比赛的前十五名将成为这次训练的金牌得主，第十六名到第五十名将获得银牌，第五十一名到第一百名将获得铜牌。（得奖人数将根据参赛人数进行调整）
总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。
UPD：比赛结束
恭喜比赛的前五名：
祝贺总分前三名 goodeat,QAQAutoMaton,hehezhou 获得抱枕！
这次UR延续了UR 19的风格，又给大家送上了一场良心的UER难度的UR！
from rushcheyo，数据，标程，题解 by mayaohua
良心送分A题~
我会爆搜！
直接按题目描述的过程 $O(n!)$ 爆搜，可以通过子任务 $1$ ，期望得分 $9$ 分。
我会状压DP！
使用状压DP， $f[S]$ 表示当前点集为 $S$ 的方案数，转移可以预处理一下。
时间复杂度为 $O(2^nn)$ ，可以通过子任务 $1\sim 2$ ，期望得分 $20$ 分。
如果没想到DP，但是很有拼劲的话，你应该可以把深度不超过 $3$ 的数据手玩出公式。
可以通过子任务 $5$ ，期望得分 $14$ 分，结合算法二可以得到 $34$ 分。
考虑靠谱做法。倒着考虑题目的过程，其实就是在一棵树上每次删去一个度为 $1$ 的节点或删去一个度为 $2$ 的节点并合并两个邻接点。
不妨先计算概率，最后再乘回 $(n-1)!$ 。 令 $f_i$ 表示考虑子树 $i$ ，假定节点 $i$ 有一个不可删去的父亲，随机排列能删空子树 $i$ 的概率。那么原来答案显然就是 $(n-1)!\cdot \prod\limits_{i\in son_1}f_i$。
这个DP的转移可以考虑枚举子树 $i$ 中最后一个删去的节点：如果是节点 $i$ ，那么贡献显然是 $\prod\limits_{j\in son_i}f_j$；否则不妨设它是节点 $j\neq i$ ，那么之前需要分别删去两个部分—— $j$ 子树中其它节点及 $i$ 子树中除去 $j$ 子树的部分。第一个部分的贡献显然是 $\prod\limits_{k\in son_j}f_k$，而考虑第二部分，令节点 $i$ 到节点 $j$ 路径上的节点依次是 $a_1=i,a_2,\ldots,a_k=j$ ，那么由于节点 $i$ 的父亲不可删去且节点 $j$ 最后删去，因此删去某个 $a_u$ （ $u < k$ ）时它的度数必定是 $2$ ，且它所有不是 $a_{u+1}$ 的子树都被删空了，那容易看出这部分概率就是 $\prod\limits_{u=1}^{k-1}(\prod\limits_{v\in son_{a_u},v\neq a_{u+1}}f_v\cdot \frac{1}{siz_{a_u}-siz_{a_{u+1}}})$ 。不论哪种情况，因为我们钦定了某个点最后一个删除，最后还要乘上 $\frac{1}{siz_i}$ 。
直接按上面的式子实现，时间复杂度为 $O(n^2)$ ，事实上能通过子任务 $1\sim 5$ ，期望得分 $71$ 分。
冷静一下，发现算法四里面的式子不少部分可以预处理。具体来说，我们可以让 $g_i=f_i\cdot siz_i$ ，并在第二种情况中枚举节点 $j$ 所在的子树，那么容易得到下面的递推式： $g_i=\prod\limits_{j\in son_i}f_j+\sum\limits_{j\in son_i}g_j(\prod\limits_{k\in son_i,k\neq j}f_k\cdot \frac{1}{siz_i-siz_j}),f_i=g_i \cdot \frac{1}{siz_i}$ 。
上面推导的关键是注意到如果我们选择了子树 $j$ 中节点 $k$ ，那么 $k$ 对子树 $i$ 和子树 $j$ 贡献时，唯一区别就是在 $a$ 序列最前面加了一个节点 $i$ ，因此很容易更新贡献。
精细实现时间复杂度为 $O(n\log n)$ 或 $O(n)$ ，可以通过子任务 $1\sim 6$ ，期望得分 $100$ 分。
把算法五的DP式子仔细拆开，事实上能得到一个不用DP的做法： $f_i=\prod\limits_{j \in subtree_i}\frac{1}{siz_j}(1+\sum\limits_{k\in son_j}\frac{siz_k}{siz_j-siz_k})$ 。
这样只需要预处理一下逆元就可以简单计算了，时间复杂度为 $O(n)$ ，可以通过子任务 $1\sim 6$ ，期望得分 $100$ 分。
这题原来是作为B题的，一开始的版本是有 $q\leq 10^5$ 次询问，每次询问一个点集 $S$ （ $\sum |S|\leq 10^5$ ）作为最后保留的节点集合（而不是现在的只有节点 $1$ 被保留），有兴趣的同学可以自己思考下。
from rushcheyo，数据 by nike0good，标程，题解 by mayaohua
感谢matthew99帮助加强。
大家纷纷通过了这题，但是是否记得要证明结论呢？
或许有某些神奇的搜索能通过子任务 $1$ ？期望得分 $9$ 分。
很容易看出这是一个最小链覆盖模型：令子串 $a\leq b$ 当且仅当 $a$ 是 $b$ 的子串，这是一个定义在子串集合上的偏序关系，那么就是选择最小数目的链覆盖所有子串。
直接用网络流来求解DAG最小链覆盖，可以通过子任务 $1\sim 2$ ，期望得分 $27$ 分。
刚刚的做法没有利用题目的特殊性质。根据dilworth定理，最小链覆盖等于最长反链，考虑从这个方向入手。
容易发现我们可以选择某个长度 $len$ 的所有子串作为一个极长反链。可以大胆猜测，对不同的 $len$ 取最大值就是最长反链！
发现这样确实能通过所有样例，让我们来证明一下：
引理1：最长反链长度即为最大的同一长度不同子串个数。
证明：如果存在一个反链中子串长度不全相同，我们下面证明可以得到一个相同长度的串长度全相同的反链。
考虑其中长度最小的串长 $len$ ，如果我们能够找出一个子串 $S[l,l+len-1]$ 在反链中，且 $S[l-1,l+len-2]$ 或 $S[l+1,l+len]$ 不在其中，我们显然可以将 $S[l,l+len-1]$ 换成 $S[l-1,l+len-1]$ 或 $S[l,l+len]$ （这两个串显然都不在原来反链中）而仍然为反链。反复进行这个操作，直到不能调整为止，此时所有长度为 $len$ 的子串均在其中，那显然不可能有其它长度子串，也即此时得到一个串长度全为 $len$ 的相同长度反链。
由上述结论，我们只需要计算出每个长度的不同子串个数，这可以用 SAM 或者 SA 计算。
对每组询问分开构建 SAM 或 SA，时间复杂度为 $O(nq\log n)$ 或 $O(nq)$ ，可以通过子任务 $1\sim 3$ ，期望得分 $48$ 分。
考虑对多组询问加速。
在算法二的基础上尝试一些数据结构乱搞，比如用回滚莫队加线段树可以做到 $O(n\sqrt q\log n)$ 左右的复杂度。
（或许）可以通过子任务 $1\sim 4$ ，期望得分 $65$ 分。
当串随机的时候，算法二中得到的串长 $len$ 不会太大。
考虑取一个阈值 $T$ ，只考虑长度 $\leq T$ 的串。对询问离线并对右端点扫描线，这样每次加入 $O(T)$ 个串，用哈希维护下上一次出现位置，并用树状数组每个左端点维护不同子串个数即可。
时间复杂度为 $O((n+q)T\log n)$ ，取 $T=20$ 即可通过子任务 $5$ ，结合算法三，期望得分 $80$ 分。
基于刚刚的结论优化是很难通过子任务 $6$ 的，我们希望有更强的结论。
通过大胆猜想和用样例验证，我们可以猜测下面的结论：
引理2：最长反链长度 $\geq k$ 当且仅当长度为 $n-k+1$ 的子串两两不同。
证明：充分性是显然的——只需要取所有长度为 $k$ 的子串即可。
考虑证明必要性。根据引理1，我们只需要考虑所有长度为某个固定 $len$ 的子串，那么若最长反链长度 $\geq k$ ，显然有 $len\leq n-k+1$ 。
假设存在两个长度为 $n-k+1$ 的子串 $S[a,a+n-k]$ 和 $S[b,b+n-k]$ （ $a < b$ ）相同，那么 $\forall 0\leq i \leq n-k+1-len$ ，均有 $S[a+i,a+i+len-1]=S[b+i,b+i+len-1]$ 。于是，长度为 $len$ 的不同子串个数不会超过 $(n-len+1)-(n-k+1-len+1)=k-1$ ，矛盾。
故所有长度为 $n-k+1$ 的子串互不相同。
由上述结论，答案即为 $|S|-\max\limits_{1\leq i< j\leq |S|}lcp(S[i,],S[j,])$ 。
直接每组询问分开用 SAM 或 SA 计算，时间复杂度同样为 $O(nq\log n)$ 或 $O(nq)$ ，可以通过子任务 $1\sim 3$ ，期望得分 $48$ 分。
考虑快速解决多组询问，这可以对算法五用数据结构优化。
在后缀树上对后缀集合进行启发式合并，每次合并两个不同子树中的后缀集合 $S_1$ 和 $S_2$ ，提取出后缀对 $(x,y)$ （ $x < y$ ）使得 $x\in S_1,y\in S_2$ 或 $x\in S_2,y\in S_1$ 且 $x,y$ 在 $S_1\cup S_2$ 中相邻。容易发现对询问有用的 $(i,j)$ 一定会是这样提取出的 $(x,y)$ ，而这样的 $(x,y)$ 只会有 $O(n\log n)$ 对。
那么对询问离线，对右端点扫描线加入这些 $(x,y)$ 对，并用线段树维护每个左端点的答案即可。
时间复杂度为 $O(n\log^2n+q\log n)$ ，可以通过子任务 $1\sim 6$ ，期望得分 $100$ 分。如果用 SAM+LCT 代替后缀树上启发式合并，也可以得到相同复杂度做法。
from Infleaking，数据，标程，题解 by Infleaking
肥力第 $i$ 小的当然是 $a_i$ 啦！甚至不用排序，直接输出 $a_i+m/2$ 。
可以通过子任务 $1$ ，期望得分 $3$ 分。
我们知道一个经典结论， $n$ 个 $[0,1]$ 随机实数第 $i$ 小的期望是 $\frac i{n+1}$ ，于是我们套入这个题里面，答案就是 $a+\frac{mi}{n+1}$ 。
可以通过子任务 $2$ ，结合算法一期望得分 $18$ 分。
这个题甚至都没法暴力！
问题来了，现在我推出了一个式子，我要怎么才能知道我没写错呢？测样例！
借助算法二的结论，我们搞到了一个显然正确的暴力：
按照端点分段，枚举每个值在哪一段中，利用算法二，我们就可以得到在这种情况下的答案。把所有情况乘上出现的概率求和就是答案了。
时间复杂度 $O(n^n)$ ，可以通过子任务 $3$ ，结合算法一、二期望得分 $34$ 分。
假设我们知道 $f_i(x)$ 表示第 $i$ 小的数大于$x$的概率，那么显然 $ans_i=\int f_i(x)dx$ 。
通过枚举哪些数是小于 $x$ 的，我们可以得到一个 $f_i(x)$ 的表达式 $f_i(x)=\sum_{|S|=i-1}(\prod P(s_j)\prod (1-P(a_{t_j})))$
（ $T$ 为 $S$ 的补集， $P(i)$ 是关于 $x$ 的函数且 $P(i)(x)=a_i < x$ 的概率）。
这个 $P$ 是一个分段的直线，因此 $f_i(x)$ 会是一个分段的多项式，枚举端点然后直接DP维护 $f_i$ 的每一项系数。
时间复杂度 $O(n^4)$ ，可以通过子任务 $3\sim 4$ ，结合算法一、二期望得分 $55$ 分。
聪明的同学已经发现了，相邻的两个端点之间只有少数的 $P(i)$ 是会变的，我们可以直接利用上一个端点的DP值快速计算出下一个。具体来说就是撤销原来的 $P(i)$ 对于 $f$ 的影响，假装这是最后加入DP的值，然后倒着算一遍把之前的DP值求出来，再加入新的 $P(i)$ 。
时间复杂度 $O(n^3)$ ，可以通过子任务 $3\sim 5$ ，结合算法一、二期望得分 $69$ 分。
瓶颈在于这个积分，这使得我们不得不求出所有的 $f$ 然后一个一个算。
观察最初的式子 $f_i(x)=\sum_{|S|=i-1}(\prod P(s_j)\prod (1-P(a_{t_j})))$ ，我们知道多个函数乘积高阶导数就是尝试将求导分配到每一个乘积里面，然后对每一种方案求和。观察到 $P(i)=\frac {x-a_i}m$ 或者为常数，其一阶导是 $\frac1m$ ，如果我们把后面的尾巴去掉，就可以得到 $g_i(x)=\sum_{|S|=i-1}\prod P(s_j)$ 是 $G(x)=\prod P(i)$ 的高阶导数乘上一个系数。
考虑其组合意义： $f_i$ 是恰好有 $i$ 个数满足条件的情况之和，而 $g_i$ 是枚举有 $i$ 个数满足条件，对其他数没有要求的所有情况之和，因此可以得到其关系 $g_i=\sum \binom{j}{i}f_j$ ，因此我们可以用 $g_i$ 反解出 $f_i$ 。
此时，我们只需要对相邻两个端点，求出 $G(x)$ 的高阶导数在端点处的点值即可，这是一个卷积的形式，可以用FFT解决。而 $G(x)$ 可以通过上一段区间的 $G(x)$ 乘除少量二项式得到。
相邻的两个端点之间需要一次卷积来计算答案，因此时间复杂度是 $O(n^2\log n)$ 的，可以通过子任务 $1\sim 7$ ，期望得分 $100$ 分。如果不幸常数写大了，可能只有 $74$ 分。
UOJ Round #20 将于 4 月 4 日星期日晚上 19：00 举行！比赛将进行 3 个小时，共三道题。
这是 UOJ 第二十场 UOJ Round。UOJ Round 还是一如既往的省选及以上难度，欢迎大家来玩，来玩就能上分。
公元 1948 年 4 月 4 日，美国总统杜鲁门签署了由国会通过的援助欧洲复兴法案，即著名的马歇尔计划。
最近，在经历了与跳晚国长时间的战争后，蛐蛐国百废待兴。于是蛐蛐国王向跳蚤国王请求援助，跳蚤国王欣然应允，派出了得力助手伏特作为特使去援助蛐蛐国。
携带了跳蚤国秘密技术的伏特，究竟能不能拯救处于水深火热中的蛐蛐国呢？
出题人： rushcheyo,Infleaking
这场成绩将计入 rating。
参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 ae1d2e912f3f8a9341abb4e583456c6cd634743df9b28158361891b192fbf168 。比赛结束后将公布条件。
再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。
UPD: 恭喜前五名的选手！
import hashlib
s='非零分数按顺序连成的字符串中逆序对最多的，如有多个取排名最高的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())
#ae1d2e912f3f8a9341abb4e583456c6cd634743df9b28158361891b192fbf168恭喜 Iittle_waxberry 获得 uoj 抱枕！
鄂公网安备 42010202000505 号Server time: 2024-11-21 06:37:14