啊……今年的暂别似乎也鸽到了今天。在过去的一年里，UOJ 的管理员的数量加倍了，在北大集训前的一段时间里，传完了一部分上一届的历史遗留的试题。在年底的时候，和往年一样举办了一场 UOJ 的正式 Round。虽然大家对题目难度是否符合 Easy Round 产生了质疑，但总体来说还是很不错的。

但大家都看到了，猫老师的博客中关于 UOJ 现状的一些看法提到的一些问题，我认为是客观存在的。

是什么导致了现状呢？我认为有以下几个方面。

去年换届的时候，我们分设了出题组和传题组。但实际上到了后来阶段的时候，我们发现出题组的出题能力十分有限、而传题组的传题的很大一部分工作是由出题组的我和 AwD 完成的——我并不打算苛责传题组的同学，我不会苛责任意一名用爱发电、乐意来帮助 UOJ 的同学，但每个人都会有自己的事情要做。事实上，在去年的这个时候，也正是传题组的 LazyJazz 在一天之内上传完毕了 12 道清华集训题，在一定程度上解决了上一届遗留下来的燃眉之急。但，随着和 OI 的渐行渐远，对于枯燥的传题任务，大家会不愿去完成，尤其是在身边出现了许多需要做的事的时候，或是在传题的工作上遇到了一些困难的时候。这些问题是我可以理解的，但也是客观存在的。

另外一方面，去年额外增加的正式管理员人数，实际上成为了 UOJ 的一点负担。在分锅的时候，我会注意让大家的锅平衡一点，不会出现有人锅的重量要显著重于别人的情况。然而，如果有一个人鸽掉了自己的锅，就很容易导致所有人都鸽掉自己的锅。到最后，所有的人都会选择鸽掉自己的锅，因为只要鸽掉了这一次的锅，就可以把这一次的锅留到下一次。

此外最为尴尬的点是，在传题之外，我们这一届的管理员也没有产出一些我们满意的题。这也直接导致了今年的 UOJ NOI Round 真的变成了 UOJ No Round。伴随着 UOJ 以前比赛的出题主力的逐渐离开，在仅有的几个投给 UOJ 的题中，我们很难组出一套令人满意的题。由于今年的 NOI 时间恰好在二招之后，即便是不考虑题目质量，有了足够的题的时候，我们也已经完全来不及准备比赛了。当然，这实际上也可以说是准备不足的一部分。

从我的角度来说，我自己本身也没有资格去批评别人。我对大家的 push 不够紧，同时自己也太鸽(lan)了，这对现状的影响也必然是极大的。以及，在联系沟通出现一些问题的时候，解决不够及时，从而导致事情慢慢就搁置了。

在作为 UOJ 管理员的最后一段时间里，我和 vfk 进行了更多的沟通，解决了 UOJ 本身的一些历史遗留问题，UOJ 变得更好用了。但实际上，当面临 UOJ 系统的问题时，仅仅是管理员的努力往往会无济于事。因此，我也希望在未来，这个问题能够得到解决。

另外，针对猫老师博客中提到的一些，也是反复提到的问题，我想尽我自己的力予以回答。

1. 关于 A+B 的 hack 的问题，反复有人提到建议取消 A+B 的 hack 功能。但是，即便是你关闭了 A+B 的 hack 功能，其他题还会开始出现许多为了测试功能的 hack 堆积，甚至复制 AC 的代码只是为了进行功能测试的新人。而是否要采取高压的封禁政策，目前来看还是存疑的。

2. 关于博客管理的问题，可能还需要一个明确的界限。只能说是看到太过分的就封掉，平时一个新人来了就封掉也未免不近人情。

3. 评测机效率的不公平现象很难解决。UOJ 是部署在阿里云上的，云服务器测评不太稳定，而维护实体机又太麻烦了 ovo (by vfk)。

那么，接下来我们就来迎接我们新一代的管理员吧。希望新的管理员能够对以上的经验教训引以为戒，也希望他们能够一直保持对 UOJ 的热爱，并探索出一条解决以上的一些问题的道路：

peehs_moorhsum, zhouyuyang, AprilGrimoire。

另外，还有一位退役 ACMer nike0good 以及还没有进入大学的上一届的管理员 diamond_duke，仍将协助部分 UOJ 的工作。

这一届新的管理员的统筹管理，将由新一届管理员内部协商决定。

最后祝新一届的管理员，一切顺利！希望 UOJ 的精神能够，一点一点传承下去！

惨啊。。感觉延续了 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分。

UOJ Round #18 将于 8 月 11 日星期日晚上 19:00 举行！比赛将进行 3 个小时，共三道题。

这是 UOJ 第十八场 UOJ Round。由于这一届管理员贡献不出好的 idea，UOJ 已经很久很久没有比赛了 :(

本次 UOJ Round 的难度和以往的一些 UOJ Round 难度相近，欢迎大家来玩，来玩就能上分。由于已经很久没有比赛了所以还希望大家互相转告一下 UOJ 活了（

公元 2016 年 8 月 11 日，中国选手马龙获得 2016 年里约奥运会乒乓球男子单打冠军。

2019 年 8 月 11 日，跳蚤国奥运会鸽王大赛经过数次延期后，如期举行。作为跳蚤国的全国最鸽跳蚤的码农同学，自然会为了捍卫这一宝座而继续奋斗。鸽了一个小时后，码农同学到达了赛场。然而，他仍然是他所有队友中最早到的。事实上，他所有的队友都鸽了，因此他只能独立面对接下来的挑战。

因此，本次 UR 将以码农接下来参赛的经历为主题。

出题人：bulijiojiodibulido, djq_cpp, peehs_moorhsum

这场成绩将计入 rating。

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 a927266c42a71c44137bb33ebf86f392c9d90b9b0f9d872a02a752b52f9468c7 。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

UPD: 比赛好像已经结束好几天了= =，恭喜前五名的选手！

1. pink_rabbit
2. supy
3. JOHNKRAM
4. Infleaking
5. luoyuchu

话说…感觉这次的抱枕条件不太有趣啊，感觉已经没有有趣的想法了= =

import hashlib
s='每题罚时的秒数的乘积在模998244353意义下以3为底取离散对数后值最小的，如有多个取罚时最多的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())

a927266c42a71c44137bb33ebf86f392c9d90b9b0f9d872a02a752b52f9468c7

恭喜 supy 获得 uoj 抱枕！

由于一些…我也不知道是什么原因吧，似乎 UOJ 现在干活的管理员只剩我和 AwD 了o(╥﹏╥)o，这次正好过年离 WC 比较近，我到家的时候离过年也没几天了，比赛这么鸽还是要道歉 = =

感谢本次救 UOJ 于题不全办不出比赛之中的各位出题人 laofu, matthew99, zhouyuyang, WuHongxun, Picks！

特别感谢将 E 题从 WC 的课件中移到 UOJ 的比赛中的 Picks 老师，牺牲了 WC 第一课堂上大家冬眠的时间，换来了一个超有趣的 E 题！

同时感谢 AwD 一天写出约 1 sdn (1 sdn = 11.7KB, 关于这一单位的来源见【集训队作业2018】蜀道难) 代码的精彩表演！

接下来是这场比赛的题解，这次的 A 题比往常的 Goodbye Round 的 A 题更难一点，这是因为 ABC 三个题都觉得挺好的有点舍不得扔，在 A 前面再加一个题又和传统不太符合。一直担心大家 A 题会出现惨案，不过从比赛中大家通过了 40 人并且大多数人都拿到了可观的分数(>0)这一点来看还是比较成功的！

新年的拯救计划

from laofu, 标程、数据和题解 by whzzt

最早AC: ridiculos (0:14:21)

最短提交: luhong 提交代码

算法一

手玩 $n=5,6$ 即可通过第一个子任务，期望得分 17 分。

算法二

直接套用求最多边不相交生成树的方法(见李煜东“图连通性若干问题探讨.pptx”)，时间复杂度 $O(n^4)$，期望得分 27 分。

算法三

显然我们会发现构造出的树的数量不超过 $\lfloor \frac{n}{2}\rfloor$，因为一棵树有 $n-1$ 条边。

咦这个 A 题怎么这么难？咦怎么有个 Subtask 部分分这么多？肯定是用来平衡题目难度造成的平均分下降的，总之就是这个部分分肯定很水！

容易发现，当 $n$ 是素数时，$\mathrm{\forall }0\le k<n,\mathrm{\exists }0,k,2k,3k\dots (n-1)k$ 在$modn$ 意义下互不相同。我们可以构造 $\lfloor \frac{n}{2}\rfloor$ 棵树，第 $i$ 棵树只考虑满足 $|u-v|=k$ 或 $|u-v|=n-k$ 的边 $(u,v)$，这样我们可以构造出 $\lfloor \frac{n}{2}\rfloor$ 棵树，达到上界。

期望得分 44 分，结合之前的算法可以获得更高分数。

算法四

我们尝试构造一种恰好为 $\lfloor \frac{n}{2}\rfloor$ 的方案，这意味着当 $n$ 是偶数时所有边都会被用上。

如何构造 $\lfloor \frac{n}{2}\rfloor$ 棵树？可以尝试先构造一棵树 $T_0$。接下来对于 $T_0$ 中的每条边 $(u,v)$，我们向 $T_i$ 中添加边 $((u+i)modn,(v+i)modn)$。我们定义一条边 $(u,v)(u<v)$ 的长度为 $min(v-u,u-v+n)$，那么在 $T_0$ 中一定恰好包含了 $2$ 条长为 $1$ 至 $\frac{n}{2}-1$ 的边和一条长为 $\frac{n}{2}$ 的边。

考虑提出那条长为 $\frac{n}{2}$ 的边，不妨假设其端点为 $1$ 和 $\frac{n}{2}+1$，我们只要让 $1$ 和 $2$ 至 $\frac{n}{2}$ 之间的点连边，$\frac{n}{2}+1$ 和 $\frac{n}{2}+2$ 至 $n$ 之间的点连边即可。

当 $n$ 是奇数，我们可以采用同样的构造，容易发现是合法的。

当然本题的构造方法有多种，一些不同的方法也可以通过 = =

新年的Dog划分

from matthew99, 标程和数据 by matthew99, 题解 by whzzt

最早AC: peehs_moorhsum (1:23:44)

算法一

注意到图是二分图时，若我们将图划分成两个非空部分 $A$ 和 $B$，只保留图中 $A$ 和 $B$ 之间的边并进行询问，一定有至少一组这样的 $A$ 和 $B$ 返回的结果是联通。

考虑返回值为联通的情况。不妨假设最终二分图两侧的点集分别为 $S$ 和 $T$，其中 $S\cap A\ne \mathrm{\varnothing }$，若 $T\cap A\ne \mathrm{\varnothing }$，那么 $S\cap A$ 和 $T\cap A$ 不可能联通。因此会有 $T\cap A=\mathrm{\varnothing }$，同理 $S\cap B=\mathrm{\varnothing }$，于是有 $S=A,T=B$。

因此当图是二分图时，我们只要枚举点集进行询问即可。

询问次数 $2^n$，期望得分 13 分。

算法二

为了获得最终二分图的两部分，我们尝试获得原图的一棵生成树。

我们可以考虑尝试删掉二分图中所有的边，如果一条可能的边删除后连通性发生了改变，我们就保留这条边，否则删去这条边。最终图中一定会剩下恰好 $n-1$ 条边，它们构成了一个生成树。

于是我们只要将生成树黑白染色就可以得到二分图的一个部分了。

询问次数 $\frac{n(n-1)}{2}$，期望得分 37 分。

算法三

刚刚的寻找生成树的方法实在是太暴力了，我们可以对刚刚的方法进行一些优化：二分查找下一次保留边会发生在什么时候。由于这样的事件只会发生 $n-1$ 次，我们只需要进行这么多次二分。

注意到我们找到了原图的一个生成树，只靠这个生成树是可以让原图联通的。那么我们可以保留生成树上的边，删去其它连接二分图两侧的边。如果图不是二分图，那么图中一定存在环，于是一定存在剩余的某条树边删去后仍然连通。

每次二分需要 $\log (n^2)=2\log n$ 左右次查询，因此询问次数 $2n\log n$，期望得分 67 分。

算法四

为了去掉 2 的常数，我们需要将对边二分优化为对点二分。

考虑从 1 号点开始，使用 BFS 进行上述过程，就只要对点二分了。

询问次数 $n\log n$，期望得分 100 分。

新年的小黄鸭

from zhouyuyang, 标程、数据和题解 by zhouyuyang

最早AC: supy (3:06:13)

算法负二

大胆猜想直接树剖答案最优。

获得$0-5$分好成绩。

算法负一

大胆猜想在子树size过大的时候可以钦定重儿子。

获得$0-20$分好成绩。

算法零

大胆猜想在子树深度和过大的时候可以钦定重儿子。

获得$0-20$分好成绩。

算法一

直接暴力枚举哪些是重边。

时间复杂度$O(2^n\times n^2)$或$O(2^n\times n)$

算法二

假设我们已经知道了你的轻重边划分方案$T$,考虑如何计算答案。

显然如果一条边是轻边我们直接把它扔进$f(x)$里是没有问题的。

如果遇到了轻边，那么在这个轻边父亲节点向上的重链长度显然不会改变，也可以扔进$f(x)$里面

设$h(x,v1,v2)$表示在$x$号节点,已经确定在$f(x)$里的权值为$v1$,向上的连续重链长度为$v2$，子树内的最优解。

转移直接枚举重儿子，并且更新当前状态。

时间复杂度$O(n^4)$或$O(n^3)$

空间复杂度$O(n^3)$

算法三

观察DP状态，我们发现我们可以使用某些技巧干掉$v1$这一维。

我们考虑在产生$v1$贡献的时候，直接在这个节点将他的贡献算进答案，而不是在子树上每个节点上计算答案。

这样子直接设$h(x,v2)$表示在$x$号节点，向上的连续重链长度为$v2$，子树内的最优解。

转移仍然直接枚举重儿子。

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

空间复杂度$O(n^2)$

算法四

继续观察DP状态，我们发现我们可以尝试只存下来$lo{g}_{2}v2$的值，这样子状态就变成$O(nlogn)$了。

转移我们枚举在$x$所在重链上第一个满足$f$的值不同于他的父亲节点的点,或者是叶节点,设其为$y$

观察算法三中的DP转移方程，不难发现在钦定重儿子的时候转移方程形如$h(y,v2+1)+\mathrm{\Sigma }h(x\mathrm{到}y\mathrm{路}\mathrm{径}\mathrm{上}\mathrm{所}\mathrm{有}\mathrm{的}\mathrm{轻}\mathrm{儿}\mathrm{子},0)+\mathrm{自}\mathrm{己}\mathrm{的}\mathrm{权}\mathrm{值}\to h(x,v2)$

因为在转移的重链上的点$f(x)$相同，所以我们可以假设这些点有点权,为$v(x)=\sum h(x\mathrm{父}\mathrm{亲}\mathrm{除}\mathrm{了}x\mathrm{之}\mathrm{外}\mathrm{的}\mathrm{所}\mathrm{有}\mathrm{儿}\mathrm{子})+\mathrm{自}\mathrm{己}\mathrm{附}\mathrm{带}\mathrm{的}\mathrm{权}\mathrm{值}$

此时转移方程就可以看成路径点权和加上$y$子树的权值(如果$y$不是叶节点，否则为$0$)

对于叶节点的情况，我们可以维护$logn$颗动态开点线段树维护深度在某一范围内的叶节点的点权和最大值。

对于非叶节点的情况，不难发现合法转移只有$O(nlogn)$种，直接找到所有可能出现的情况，暴力转移。

非叶节点的点权和可以在确定$dfn$序之后使用树状数组维护。

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

空间复杂度$O(n{\log }^{2}n)$

算法五

出题人卡内存怎么办？？？

考虑通过一些操作把$lo{g}_{2}v2$拆开，使得他在他的$1$代祖先，$2$代祖先，$\dots$ ，$2^k$代祖先的地方恰好被算一次。

此时我们每个点的点权就唯一了，线段树就只需要一颗了。

其于基本同算法四。

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

空间复杂度$O(n\log n)$

算法六

from: matthew99

算法四，五我听不懂怎么办？

考虑对于每一个节点x维护一个分段函数表示$f[x]$

我们可以发现分段函数的段数的上界是$O(\mathrm{子}\mathrm{树}\mathrm{大}\mathrm{小}\times \log n)$的。

直接启发式合并维护即可。

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

空间复杂度$O(n\log n)$

算法七

from: matthew99

在审题的时候@whzzt说分段函数段数$O(\mathrm{子}\mathrm{树}\mathrm{深}\mathrm{度}\times \log n)$的。

此时在算法六的基础上套长链剖分,暴力合并,时间复杂度可以做到$O(n\log n)$

但是因为出题人 zhouyuyang和审题人whzzt太咕咕咕了,没有实现过这个算法，也没有想过算法细节。

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

空间复杂度$O(n\log n)$

新年的族谱树

from WuHongXun, 标程和题解 by AwD, 数据 by whzzt

whzzt: (；´д｀)ゞ因为懒得写 spj 加了个权值，为了让问题描述看起来更合理一点加了一大堆废话= = 似乎大家没怎么看懂的样子

算法一

枚举族谱树所有的形态，找一个字典序最大的输出来。

时间复杂度不明。

算法二

怎样的老家族集合是合法的？

最终选择的集合确定了一棵有根树，选出的集合作为有根树的子树，两两之间要么是包含的，要么是分离的。

要求字典序最大的方案，也就是要尽量选择权值大的老家族的集合。

按照套路，显然可以得到一个简单的贪心：沿权值降序依次考虑每个集合，若它与之前选择的集合没有冲突，则选择该集合。

一共有 $O(nk)$ 个集合，每次判断合法性的时间复杂度为 $O(n^2)$ 。

使用 bitset 可以将判断合法性的复杂度优化至 $O(\frac{n^2}{w})$

时间复杂度为 $O(n^{3}k)$ 或 $O(\frac{n^{3}k}{w})$。

算法三

在后文中，我们将会把一类有根树称作族谱树 —— 族谱树的叶子节点都是元素，非叶节点都是一个包含了其子树中的元素的集合，每个非叶节点至少有两个孩子。

由于族谱树它真的是一棵树，因此并不用依次检测当前集合 $S$ 与树上的所有集合是否有冲突 —— 当 $S$ 合法时，考虑族谱树上最小的包含它的集合 $T$， $T$ 的每个孩子 $W_i$ 要么是 $S$ 的子集，要么与 $S$ 分离，并且是 $S$ 子集的孩子的并恰好是 $S$。

于是就可以提高判断合法性的效率了：

首先，找到包含 $S$ 的最小集合 $T$ —— 找到 $S$ 中的任意一个节点 $a$，考虑节点 $a$ 到根的链，一定是一串 $S$ 包含的集合接着一串包含 $S$ 的集合，因此可以简单的二分出 $T$。

对于 $S$ 中的每个元素 $a$，找到是它祖先也是 $T$ 的孩子的集合。这些集合显然就是 $W_i$ 了，由于这些集合两两不交，因此只需要看看它们的大小之和是否为 $|S|$，就知道它们的并是否为 $S$ 了。

于是就可以在 $O(n\log n)$ 的时间复杂度下检测一个集合是否合法。（使用长链剖分可以做到 $O(n)$，然而并没有什么卵用）。

当合法的时候，大力重建族谱树。

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

算法四

在上一个算法中，第一步的时间复杂度可以做到 $O(\log n)$ —— 可以直接以集合大小作为关键字二分。瓶颈在第二步上。显然，通过枚举 $S$ 中每个元素的方法得到 $W_i$ 过于缓慢，我们需要更快的做法。

在静态的树上维护动态的树是很困难的，不妨在动态的树上维护静态的树。

不失一般性的假设 $S$ 来源于老族谱树 $a$ 上的子树 $b$ ，对于子树 $W_i$ ，如果 $W_i$ 是 $S$ 的子集，$W_i$ 中所有节点在树 $a$ 中的 LCA 就是节点 $b$ 的孩子了。显然，只有当所有 $W_i$ 要么是 $S$ 的子集要么与 $S$ 分离时，LCA 是节点 $b$ 的孩子的 $W_i$ 的大小之和才恰好为 $|S|$，不然一定会小于 $|S|$，因为那些不合法的元素并不会被统计到。我们可以通过这个来判断 $S$ 是否合法。

具体来说，对于每个族谱树中的集合 $T$，按子树的 LCA 的 DFS 序号，一共以 $k$ 种顺序维护 $T$ 的孩子。当询问老族谱树 $a$ 上子树 $b$ 构成的集合 $S$ 的合法性时，只需要先找到 $T$，再看看 LCA 是 $T$ 的孩子的大小之和是否为 $|S|$ 即可。这些孩子在第 $a$ 个顺序上是一个区间，二分找到这个区间即可。

于是检测一个集合是否合法的复杂度就降到了 $O(\log n)$。

瓶颈成了每次修改族谱树，理论上应该能做到 $O(nk)$。

时间复杂度为 $O(n^2{k}^2)$。（好像变慢了 …… ）

算法五

考虑修改族谱树的过程 —— 我们只是增加了一个节点，并将该节点父节点的一些孩子移动给了它。这个操作在第 $a$ 个顺序上是很容易完成的，需要移动的孩子是个区间（就是算法四中判断合法性的区间），只需要将这个区间 split 出来就行了。然而对于其他顺序来说，需要移动的节点是无序的。

平衡树启发式合并 $n$ 个元素的时间复杂度是 $O(n\log n)$ 的，类似的，平衡树启发式分离 $n$ 个元素的时间复杂度也是 $O(n\log n)$ 的。于是可以直接跑个启发式分离 —— 如果需要移出来元素少于一半，则直接依次删除并把删掉的元素重新建一棵树，不然就依次删除不需要移出来的元素同样建棵树就行了。

这个东西实现出来就是 $k$ 棵 LCT 上套 splay。（$k$ 棵 toptree ？）

插入节点的时候需要知道集合的 LCA 的序号，因此在 toptree 上还需要维护一个子树的 LCA。当然，这里并不需要强上一个 $O(1)$ LCA，可以仅仅维护子树 DFS 序的最小值与最大值。当真的需要 LCA 的序号时，再去通过最小值与最大值计算 LCA，这样常数应该会小一点 ？

时间复杂度为 $O(nk\log n)$。

为什么 $k$ 这么小？动态开空间多麻烦啊 ……

新年的A+C Problem

from Picks, 标程和数据 by whzzt, 题解 by Picks

本题中的模型其实是来源于量子计算的模型。题中可使用的门是三元可逆逻辑门，而在真实的量子计算中是Hilbert空间中的线性变换，其中可逆逻辑门可以在量子计算中实现。

题目的任务是求对于长度为l的输入整数a进行加常数c的可逆电路，其中可利用的资源有三类额外位：

1. 泄露位：初始为0，输出可以为任意值的位。由于可逆运算中信息是守恒的，当输出为任意值时，输入的信息会泄露到这些额外位中。当有人获取了额外位的输出，是可能获得额外位的信息的。
2. 干净位：初始为0，输出时也为0的位。这些位可以视为一个资源池，从中取出时是0，放回时也是0。
3. 脏位：初始时不知，输出时需要还原为初始状态的位。这些位可以从系统的任意无关位置取出，在过程中利用完之后放回原位。

显然这三类额外位存在支配关系，泄露位的利用严格容易于干净位，干净位的利用严格容易于脏位。

子任务一、二

有许多泄露位可以利用时，有很多种做法都可以解决这个问题。

最简单的方法是从低到高枚举每一位，用一位存下当前的进位。但由于 $0+1=1+0$ 会造成不是一个一一映射，我们可以利用一个泄露位(值一定是0)来解决这个问题。

根据实现的不同需要 l 左右个泄露位。

子任务三

当我们有 $2l$ 个干净位可以利用时，我们考虑实现一个加法器 $(A,B,q)\to (A+B+q,B,q)$，其中 $q$ 是一个干净位，我们用来向后传递信息。

注意到我们无法绕开进位，我们不妨使用 $q$ 位置来传递进位信息。对于 $A,B$ 的对应位 $a,b$ ，我们设计可逆门 $\mathrm{MAJORITY}：(i,j,k)\to (i\oplus k,j\oplus k,\mathrm{MAJ}(i,j,k))$，其中 $\mathrm{MAJ}(i,j,k)$ 表示的是 $i,j,k$ 中存在至少两个的逻辑值，逻辑关系为 $\mathrm{MAJ}(i,j,k)=(i\mathrm{and}j)\mathrm{or}(i\mathrm{and}k)\mathrm{or}(j\mathrm{and}k)$，可以验证这是一个可逆门。

同时，当我们用 $a,b,q$ 表达当前位与进位时，它们的多数值即为进位。使用一个依此从低位到高位的操作序列，我们可以在过程中获得临时进位，并将临时进位信息递归传给后方变量操作。当递归结束时，我们可以将之前的门取反（即输入输出对调）来将操作取消，额外添加 $\mathrm{TRIXOR}$ 门 $(i,j,k)\to (i\oplus j\oplus k,j,k)$，来得到当前位的答案。

即如下过程：

fixpoint adder(a[i], b[i], q) :=
    MAJORITY(a[i], b[i], q);
    adder(a[i+1], b[i + 1], q);
    reverse(MAJORITY)(a[i], b[i], q);
    TRIXOR(a[i], b[i], q).

回到问题，我们一开始将常数 $c$ 写入变量 $b$ 中，调用加法器，再将变量 $b$ 中的 $c$ 擦除即可。

子任务四

此时我们只有 $l$ 个额外干净位，不过好在 $c=1$，我们仍能比较简单地解决。

在上一个子任务中，我们发现最关键的问题即是进位问题，我们考虑如何比较好地解决进位问题。注意到 $c=1$，则第 $i$ 位的进位实际上是输入变量前 $i$ 位进行与操作的结果。我们只需要利用额外的 $l$ 个干净位依此计算逻辑与 $(i,j,k)\to (i,j,k\oplus (i\mathrm{and}j))$ 即可。实际上我们只需要 $l-2$ 个额外位来存储每一位的进位信息，因为最后一位无作用，第一位无需存储。计算出进位之后我们可以利用 $(i,k)\to (i\oplus k,k)$ 来获得答案，之后将计算逻辑与的过程取消掉即可。

子任务五

该子任务中我们仅有 $l$ 个额外脏位，此时难度显著上升了。

这时我们需要利用一个补码的性质：在模 $2^l$ 的意义下，整数 $b$ 逐位取反的结果即是 $-b-1$。

我们利用一个技巧来处理加 $1$ 操作。考虑加法器 $(A,B,q)\to (A+B+q,B,q)$，如果我们将 $B$ 取反，我们可以计算得到 $(A,B,q)\to (A-B-1+q,-B-1,q)$。将之串在一起并将B还原，可以得到 $(A,B,q)\to (A+2q-1,B,q)$ 过程。但 $q$ 同样是脏位，如果 $q=1$，则我们计算完成。如果 $q=0$，我们实际上计算了 $A-1$ 的结果，那此时我们预先将 $A$ 取反，在其后再次将 $A$ 取反，则实际完成的仍是 $A+1$ 的计算。那么我们只需要在上述过程前后均加上由 $q$ 操控的 $A$ 取反过程。对应到位上即是门 $(a,q)\to (a\oplus q\oplus 1,q)$。

粗略观察，此时我们使用了 $l+1$个额外脏位。但是注意到 $B$ 的最高位其实可以不使用，将其取出用作进位 $q$ 即可。

子任务六

现在我们仅有一个额外位了。我们先考虑一些可能的子任务。

你需要对利用计算过程 $P:(A,y)\to (A,y\oplus f(A))$ 的一位结果 $f(A)$ 来控制一个对 $B$ 变量的操作 $O:B\to g(B)$，其中$g(g(B))=B$，但除 $A,B$ 外你仅有 $1$ 个额外脏位 $q$ 。

我们可以构造如下过程：

Definition dirtyControl(P, O, A, B, q) :=
    controlled(O)(q, B);
    P(A, q);
    controlled(O)(q, B);
    reverse(P)(A, q).

注意到当 $f(A)$ 是 $1$ 时，$\mathrm{controlled}(O)(q,B)$ 仅作用了一次。反之，则作用了 $0$ 次或 $2$ 次，均不影响变量 $B$ 的值。

当你有 $l$ 个额外脏位，还有一个输入位 $p$ 存有 $0$ 或者 $1$，你需要计算 $a+p$。

这个与子任务五非常相似。我们提供两种方法来完成。

一种是非常粗暴的方法，即使用 $p$ 作为控制变量去控制是否进行子任务 $5$ 的加 $1$ 操作。只需要将子任务 $5$ 中的所有门额外加一个控制变量 $p$，当且仅当 $p=1$ 时执行门操作即可。对于二元门，扩展成三元门是容易的。对于三元门，添加额外控制变量变为四元门之后需要将三元门进行分解。分解方法是取一个额外的脏位（随意找一个无关位即可），将前两位的信息利用小问题1中的方法存储在脏位中，再将后两位与脏位一起运算得到结果。

另一种是灵巧一点的方法，我们考虑子任务五中 $1$ 的来源，实际上是 $B$ 的取反操作。那我们使用输入位 $p$ 控制 $B$ 的取反操作，当 $p=1$ 时才进行该取反即可。

当你有 $l-1$ 个额外脏位 $Q$ ，你要获得 $a+c$ 的最高进位，输出在干净位 $s$ 中。

还是利用小问题1中的方法，我们用第 $i$ 个脏位来储存第 $i$ 个进位的信息（即若第 $i$ 位进位为1，则对应脏位取反）。逻辑形式为：

Fixpoint dirtyAdd(a[i], c[i], q[i]) :=
    If c[i]=1 then ( (controlled(NOT)(a[i], q[i])); NOT a[i]. )
    controlled(controlled(NOT))(q[i-1], a[i], q[i]);
    dirtyAdd(a[i-1], c[i-1], q[i-1]);
    controlled(controlled(NOT))(q[i-1], a[i], q[i]);

即当更低位的脏位不变时，该位进位由 $a[i],c[i]$ 控制，否则联合控制。同样的，最高位不需要存储进位，故只需要 $l-1$ 个脏位。注意最低位和最高位需要特殊处理，最低位不需要低位进位的控制，最高位运算的结果存入 $s$ 中。

现在我们利用一个额外干净位 $s$ 来计算 $a+c$。首先我们将输入 $a$ 均分成两半 $p,q$，若总长度是奇数则使 $p$ 比 $q$ 长。

我们先利用小问题3，视 $q$ 为脏位，计算出 $p$ 部分加上对应的部分 $c$，结果的最高进位，存储在额外干净位 $s$ 中。然后我们利用小问题2，视 $p$ 为脏位，将 $s$ 中的值加到 $q$ 中去。最后重复第一步，将 $s$ 中信息擦除。此时我们发现，输入的两部分不再产生关联了，只需要递归下去分别解决 $p$ 和 $q$ 的计算问题即可。

子任务七

此时额外位是一个脏位g。我们再次利用小问题1中的方法来解决这个问题。 最终的方法为：

Fixpoint addC(a, g) :=
    Let p, q as described;
    P2(g, q, p);
    controlled(allNOT)(g, q);
    P3(g, p, q);
    P2(g, q, p);
    P3(g, p, q);
    controlled(allNOT)(g, q);
    addC(p, g);
    addC(q, g);

扩展

如果我们不局限于三元逻辑门，而是可以使用量子门，则额外的一个脏位也是可以省去的。参见参考资料【3】。

参考资料

1. Craig Gidney. Constructing Large Increment Gates. http://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html
2. Thomas Häner, Martin Roetteler, Krysta M. Svore. Factoring using 2n+2 qubits with Toffoli based modular multiplication.
3. Craig Gidney. Trouble Adding Constants into Qubit Registers. http://algassert.com/post/1701

再见，戊戌!

转眼间 2018 年也已经过去了，在去年的大战中 SingleDog 击败了 AlphaGo，夺回了狗群的控制权。然而它们并没有达成主要目标——狗群的公母比仍然堪忧！但没有了 AlphaGo 这样的共同敌人，狗群已经难以拧成一股绳，也丧失了再进行改革的能力。

然而，狗群面临着更大的挑战：由于没有共同的敌人，狗群社会欣欣向荣，社会福利不断提升。然而众多 SingleDog 因为无所事事逐渐变懒，已经变成 SinglePig 了，而足不出户的 SinglePig 们甚至丧失了辨别种群的能力！

新的一年即将来临，狗群中的战斗狗——DoubleDog 们正力主改变这一现状！然而 SinglePig 们足不出户，因此 DoubleDog 们需要主动出击！为了改变狗群的现状，DoubleDog 需要再次请求它们的跳蚤朋友的帮助！

这场变革将会在大年初四的下午 13:00 到 18:00 正式启动！

即 2 月 8 日下午 13:00 到 18:00 会举办 Goodbye Wuxu 比赛，比赛时间5个小时，一共五题，祝大家玩的开心！

再次提醒大家比赛中途只测样例，最后会进行最终测试，把所有提交记录重测。

赛制采取OI赛制，这也意味着只计入最后一次提交结果。这场比赛有很多有意思的题目，大家一定不要错过！

出题人：laofu, matthew99, zhouyuyang, WuHongxun, Picks

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕！获奖条件的 SHA256 码是 27c87d04e69de78a6be9a0889f4530547cbdce78a7952ce2c6f02248dd503853 。比赛结束后将公布条件。

UPD1: 比赛结束啦，恭喜前五名的选手！

1. peehs_moorhsum
2. supy
3. fjzzq2002
4. tqyaaaaang
5. zx2003

import hashlib
s='罚时的秒数模2019的值最大的，如有多个取得分最高的，如仍有多个取罚时最小的'
m=hashlib.sha256()
m.update(s.encode('utf-8'))
print(m.hexdigest())

27c87d04e69de78a6be9a0889f4530547cbdce78a7952ce2c6f02248dd503853

恭喜 Bartholomew 获得 uoj 抱枕！

UPD2: 题解