又来 UOJ 打广告了 $\times 2$

公告链接：公告

比赛链接：Day 1 Day 2

NOIP 将近，为了帮助广大 OIer 准备比赛，也为了改变各位对 LibreOJ 比赛难度的认识，以及实现我们在 β Round 5 中的承诺，是时候举办一场 NOIP 全真模拟赛了！

LibreOJ NOIP Round #1 将于 11 月 4 日至 11 月 5 日举行。这是 LibreOJ 第一场 NOIP Round。

下面介绍比赛的具体情况。

基本信息

• 时间　2017 年 11 月 4 日，星期六，上午 8:30 ~ 12:00 + 5 日，星期日，上午 8:30 ~ 12:00
• 时长　3.5 + 3.5 小时
• 题数　3 + 3
• 赛制　NOI + NOI
• Rated + Rated

出题人

• CommonAnts( @liu_cheng_ao )
• sosusosu( @sosusosu )
• cyand1317( @cyand1317 )
• WerKeyTom_FTD( @WerKeyTom_FTD )
• spj( @WrongAnswer )
• HeRaNO( @HeRaNO )
• qmqmqm( @qmqmqm )

比赛难度

比赛难度将与 NOIP2016 相近。

同时我们确保了较多的部分分，尽力做到了较好的区分度，丰富的思维含量，以及符合 NOIP 的算法知识和代码难度。

可能比 NOIP 还要 NOIP （雾）

比赛奖励

设两天至少参赛一天的人数为 $n$。

考虑到 NOIP 的难度、真实比赛的分省评奖方式以及 LibreOJ 用户在以往比赛中表现的水平，本次比赛不会像 NOI Round 那样按比例评奖，而采取综合考虑成绩分布、题目组成员和若干在以往 OI 系列赛事中发挥稳定的标志性选手的成绩的方法评定分数线。我们将评出基准（相当于 NOIP 中的全国基准线）和最高（相当于 NOIP 中的浙江分数线）两套分数线。

这次比赛将会根据两天的总分进行排序（如果存在同分将以两天的罚时总和作为第二关键字，如果仍同分将不分先后），并评奖。

• 本次比赛未在以往比赛中获得 LOJ T-shirt 的 ID 中排名前 $\max(3,\min(6,\lfloor 0.03 n \rfloor))$ 的将获得 LibreOJ T-shirt 一件。

• 所有选手中将以某些方式选择至多 5 名选手各获得小礼品一件。选择方式的 MD5 为 f7b4c69f242009c56863a14fd6518b3d。

测评方式

比赛采用 NOI 赛制，以每道题目最后一次提交（包括 CE）为准。

为了模拟 NOIP 中选手参加 Day 2 时不知道 Day 1 成绩的情况，本次比赛采用 Day 1 只测第一个样例，两天结束后统一评测的方式。

我们知道，通常的点分治方法都基于重心，删除重心后将每个连通块分别分治。正常情况下寻找重心需要做树DP，需要遍历两次树（即使从上一层传入点数，也得在上一层遍历一次），某些选手就用了一些黑科技：从上一层传入“本层中与上一层重心相连的点”（称为根，记作 $K$）的以“上一层的根”为根的子树大小作为本层总点数。

听起来很拗口，实际上是这么回事：（图中 $K'$ 表示本层的根，$K$ 表示上一层的根）

可以明显发现，当 $K$ 和 $K'$ 处于上一层重心 $O$ 的同一子树时，传入的点数是错误的。

这是否会对时间复杂度造成影响呢？

这与找重心的方式有关。我们讨论两种最常见的找法：

法1

从本层的根开始深度优先遍历，并同时计算出子树大小，以第一个所有子树大小不超过 $\frac{n}{2}$ 的为重心。

结论：算法错误

设传入的点数值为 $n$。

可以举出反例：考虑这样一棵树：由重心和端点与之相连的三条长 $\frac{n-1}{3}$ 的链组成。初始的根位于某个叶子处。

第一层分治，传入到根所在链的大小为 $\frac{2n+4}{3}\geq 2\cdot\frac{n-1}{3}$，因而任何点都符合条件。按照深度优先顺序，这次找的“重心”是第一层的根。

第二层分治，传入到根所在链的大小为 $2<\frac{1}{2}\cdot(\frac{n-1}{3}-1)$（当 $n\geq 16$ 时）。这时不存在符合条件的点，分治无法进行，算法错误。

法2

从本层的根开始深度优先遍历，并同时计算出子树大小，将传入值与以自身为根子树大小之差作为向本层根方向的子树大小，再取最大子树最小的点为重心。

结论：算法正确，递归层数 $O(\log n)$，访问节点的总次数 $O(n\log n)$。

我们来分析时间复杂度：

我们将分治结构稍作改变，只考虑输入点数等于实际点数的问题。显然当点数为 $1$ 时访问节点数 $O(1)$。

初始问题是符合条件的。现在考虑把问题分解前处理一层产生的代价（包括递归但大小错误的部分）：

由于只有本层的根所在的方向递归时会错误，因而只要考虑对于本层重心而言根所在子树即可。

考虑一个问题。设本层实际大小为 $n$，以 $O_1$ 为根时含 $K_1$ 子树的根为 $K_1'$（也有可能 $O_1=K_1$，这时没有出现错误，复杂度正确），以 $K_1$ 为根时子树 $O_1$ 的大小为 $y_1$，以 $K_1'$ 为根时 $K_1$ 所在子树大小为 $x_1$。（均指实际大小）

解决本层的访问节点数为 $O(n)$。现在考虑递归到 $K'$ 的错误部分。该部分的实际点数为 $n-y_1$，传入点数为 $n-x_1$。设该部分处理时与上一层对应的部分用层数下标表示。以此类推直到 $K_i=O_i$ 为止。这一系列问题访问的总点数即为问题处理的代价。

运用归纳法，我们可以知道每一次的实际点数 $N_i$ 分别为 $n,n-y_1,n-y_1-y_2,...,n-\sum_{i=1}^{n-1}y_i$，传入点数 $N'_i$ 分别为 $n,n-y_1,n-x_1-y_2,...,n-\sum_{i=1}^{n-2}x_i-y_{i-1}$。

下面证明 $x_i \leq y_i$。使用归纳法，设对于 $j < i$ 该结论均成立（由重心显然对于第 $1$ 层成立）。实际上，若 $x_i > y_i$ 则对“重心”$O_i$ 而言包含 $K_i$ 的子树为最大子树，并且由于 $x_{i-1} \leq y_{i-1}$，本层的传入点数不小于实际点数。这样，用传入点数减去子树大小算出的点数不小于 $x_i$。故该算法计算出的 $O$ 的最大子树必为 $K_i'$ 且计算出的大小不小于 $x_i$。对 $K_i'$ 而言，除 $O_i$ 外的各子树大小计算值均小于其作为 $O_i$ 子树的计算值。又 $y_i< x_i$，故子树 $O_i$ 也小于该值。这样 $K_i'$ 计算出的最大子树严格小于 $O_i$ 的，与重心的计算定义矛盾。

更进一步地，我们可以证明 $y_i\geq \frac{1}{2}N_i$。证明方法类似：假设 $y_i<\frac{1}{2}N_i$，同上可证其最大子树必为 $K_i'$ 且计算的大小不小于其实际值，$N_i-y_i > y_i$。则对于 $K_i$ 而言，也可以用类似上一段的方法证明其计算出的最大子树严格小于 $O_i$，与重心的计算定义矛盾。

故有 $N_{i+1}\leq \frac{1}{2}N_i$。由于第 $i$ 层的访问点数为 $O(N_i)$，一个规模为 $n$ 的问题处理总点数满足 $T(n)=T(\frac{n}{2})+O(n)$，解得 $T(n)=O(n)$，且这部分递归层数 $O(\log n)$。

故分治时处理一个问题的时间为 $O(n)$。并且其分解出的子问题互不相交且都是正确方法的某个子问题的子集，故递归层数和子问题的时间复杂度不高于一般点分治。证毕。

已知：随机数生成元件等概率返回 $[0,p)$ 中的整数，要构造一个以概率比 $a_0:a_1:...:a_n(\gcd(a_i)=1)$ 返回 $[0,n)$ 中的整数的随机数生成器，求元件的最小期望使用次数。

设第 $i$ 次返回的结果分配了 $K_{i,j}$ 个给返回值 $j$。则：

$$ \begin{array} \forall j ,\sum_i p^{-i}K_{i,j}=\frac{a_j}{\sum a} & (1)\\ \text{minimum.} \sum_{i,j}ip^{-i}K_{i,j} & (2) \end{array} $$

引理1 $\forall i,j ,K_{i,j}\in [0,p) $

证：使用调整法：

若 $\forall i,j ,K_{i,j}\neq p $，由 $(1)$ 有 $i>0$ ，则可令 $K_{i-1,j}$ 增加 $1$，$K_{i,j}$ 减少 $p$，显然 $(1)$ 式仍成立。

$(2)$ 式的改变量为 $(i-1)p^{-i+1}-pip^{-i}=-p^{-i+1} < 0$ ，得到了一个更优解。

证毕。

现在来构造 $K$。考虑返回值为 $j$ 的情况，取出 $K$ 的第 $j$ 列向量，设为 $\vec{k}$。

则 $\vec{k}$ 是 $p$ 进制的 $\frac{a_j}{\sum a}$ 的位向量。当 $\sum a$ 是 $p$ 的幂时有两解，取最后为 $0$ 循环的一解；否则 $\vec{k}$ 是唯一的。证明从略。

至此找到了一个下界 $K$。在决策树上第 $i$ 层给 $j$ 分配 $K_{i,j}$ 个点，用归纳法可以证明方案是存在的。

另外可得推论：

推论1 “$a$ 是有理数”与“存在一个有 $n$ 个终态，字符集为 $[0,p)$ ，按随机数生成元件的结果转移，返回终止的状态的DFA满足条件。”是等价的。

证明从略。解释说明：由于 DFA 是有限状态的，因而对应的概率是循环小数（有理数）。反之则可用上述方法构造。

又来 UOJ 打广告了

正式公告链接

比赛链接

大家好，我是 LCR，一个 OI 的传说的美丽影子。

LibreOJ NOI Round #1 将于 7 月 6 日至 7 月 9 日举行。这是 LibreOJ 第一场 NOI Round。

为什么要搞这个 LNR 呢？当然是因为马上就要 NOI 啦，我们就来一次 NOI 全真模拟吧！

下面为大家介绍本次比赛的相关情况。

比赛时间

笔试模拟将在 7 月 6 日（星期四） 19:30 ~ 20:30 进行，共一小时。

Day 1 的比赛将于 7 月 7 日（星期五） 8:30 ~ 13:30 进行，共五小时、三道题。

Day 2 的比赛将于 7 月 9 日（星期日） 8:30 ~ 13:30 进行，共五小时、三道题。

出题人

这次比赛的出题人分别是：

Q：我需要注册吗？

A：直接参与就行啦！

比赛难度

比赛的难度将与 NOI2016 相近，相信对绝大部分选手来说是具有一定的挑战性的。

同时我们确保了较多的部分分；尽力做到了较好的区分度、考察内容的全面性、思维含量、以及代码难度的均衡性，题目中还有着一道十分清真的提交答案题，大家可以放心食用。

比赛奖励

设总参赛人数为 $n$。

这次比赛将会根据三次比赛的总分进行排序（如果存在同分将以两天的罚时总和作为第二关键字，如果仍同分将不分先后），其中比赛的前 $\lfloor 0.15 n \rfloor$ 名将成为这次训练的金牌得主，没有获得金牌但在前 $\lfloor 0.4 n \rfloor$ 名的选手将获得银牌，没有获得金银牌但在前 $\lfloor 0.7 n \rfloor$ 名的选手将获得铜牌。

总分前 $\max(3,\min(10,\lfloor 0.05 n \rfloor))$ 名将获得 LibreOJ T-shirt 一件，其它选手中将以某种方式随机选择五名选手将获得 LibreOJ T-shirt 一件。

随机方式的 MD5 为 b67cfd33175e92f5a687aa10c951216d，SHA-1 为 9d83cb24ecda8668b89475291dbdc202276c7395。

UPD

Day 1 和 Day 2 将分别计算 rating（笔试不计算）。如果在比赛时 rating 功能开发尚未完成，我们将在 rating 功能开发完成后重算本场比赛的 rating。

LibreOJ 链接：https://loj.ac/

6 月 16 号，星期五，晚上 19:05 ~ 22:05 进行公测赛！

就要迈出第一步了！欢迎大家来捧场！

虽然是公测，有测 Bug 的目的，但是我们还是有新题给大家捉的！尽管放心，不可能是原题大战 ……

本场比赛是三小时 7 道题的 ACM 赛制，难度 …… 被各位出题人（Menci：这里不包括我）称作 Easy Round！恩就是这样。

赛后我们会有详细的题解。

出题 / 选题人为：ZQC ( @samzhang )、Menci ( @Menci )、CommonAnts ( @liu_cheng_ao )、MedalPluS ( @mps2000 )、Dicint ( @tniciD )、Rapiz ( @rapiz )

2017 年 4 月 10 日，某 OJ 再次遭遇攻击，UOJ 群人心惶惶，暗流涌动 ……
这时，有一位人称 ZQC 的神犇建立了一个神秘的讨论组 ……
当时也许没有人想到，日后这个讨论组的名字会叫做 ……

为了纪念第一个用行动提出 LibreOJ 的伟大神犇 ZQC，本次比赛将以 ZQC 为主题。

有什么问题请在下面留言。