前几天做了做今年 PA 的题. 因为难题都不会做，所以把简单题的题解写了:

Round 1

[C] Koszulki

签到题. 排序以后找到对应位置把相等的元素都取了即可.

[B] Oranżada

注意到我们肯定是取前 $k$ 个不同的元素交换过去, 因为取后面的元素的话交换序列就会有交叉, 一定是不优的.

[A] Od deski do deski

首先注意到序列可以删除当且仅当序列可以划分成若干个长度 $\geq 2$ 的子序列使得端点元素的值相同.

注意若到此时的序列是 $S$, 假设我们当前可以通过在 $S$ 后添加元素 $x$ 使得序列变得合法, 那么 $S+x$ 也可以通过添加 $x$ 使得序列变得合法. 所以, 我们不妨设 $dp_{i,0/1,j}$ 表示考虑到 $i$, 当前序列合法/不合法, 最后有 $j$ 个 $x$ 使得 $S+x$ 变得合法. 转移为:

1. 若当前序列合法, 则如果我们添加了 $j$ 个 $x$ 中的一个, 则转移到一个合法的序列; 否则, 我们转移到一个不合法的序列. 如果我们此时在后面接着接上上述 $j$ 个 $x$, 那么我们其实可以无视最后一个元素, 合法的选法仍然合法. 同时, 我们也可以选择直接接上一个上一次我们选的元素, 所以总的选法有 $j+1$ 个
   • $dp_{i,j,0} \cdot j \mapsto dp_{i+1,j,0}$
   • $dp_{i,j,0} \cdot (n-j) \mapsto dp_{i+1,j+1,1}$
2. 若当前序列不合法, 则我们如果接了一个合法的序列, 显然会转移到一个合法的序列, 同时根据上文我们也有接下来合法选法有 $j$ 种. 否则, 相当于我们接了个没用的元素过来, 选法是不变的.
   • $dp_{i,j,1} \cdot j \mapsto dp_{i+1,j,0}$
   • $dp_{i,j,1} \cdot (n-j) \mapsto dp_{i+1,j+1,1}$

因此直接 DP 即可. 时间复杂度为 $O(n^2)$

Round 2

[C] Zakłócenia

我们暴力预处理一下最小和最大的popcount是多少, 然后只要保证填完以后仍然在取值范围里即可. 时间复杂度为 $O(n \log |\Sigma|)$

[B] Pandemia

首先, 如果我们不考虑第一段和最后一段的话, 那么相当于是这样一个问题:

有 $n$ 个数, 第 $i$ 个数为 $x_i$. 每天白天你可以选择一个数并获得它的大小的收益, 随后每天晚上每个数的大小减 $2$. 问你可能的最大收益是多少.

容易发现我们直接把 $x_i$ 从大到小排序后贪心选择是最优的. 这是因为我们相当于是每天除了已经被选走和已经小于 $0$ 的数以外, 每个数使得收益减了 $2$. 由于较小的数更快小于零, 所以我们留着它们是最优的.

对于有开头和结尾的情况, 我们可以将除了开头和结尾以外的每个连续段 $x$ 看成 $2$ 个 $x/2$, 这样一定是最优的. 因为我们注意到一个长度为 $l$ 的段, 我们是不可能堵住了一边, 然后另一边跨过了中线的 - 当我们堵住一部分的时候, 我们肯定会立刻堵住另一部分, 否则堵住左边没有意义.

[A] Poborcy podatkowi

我们考虑一个暴力 dp. 设 $f[x][i]$ 表示考虑以 $x$ 为根的子树, 且它往上贡献一个长为 $i$ 的链, 最大收益是多少. 转移时, 我们做一个背包, 记 $g[b][c][d]$ 表示选了 $b$ 个 $1$, $c$ 个 $2$, $d$ 个 $3$ 的最大收益, 那么我们可以获得一个高达 $O(n^4)$ 的做法.

注意到我们一定是1和3匹配,2和自己匹配. 所以我们只需要知道 $b-d$ 的值 $\Delta$ 和 $c$ 的奇偶性 $o$, 这样背包数组就是 $g[\Delta][0/1]$, 总的时间复杂度是 $O(n^2)$ 的.

注意到我们其实只需要知道 $g[-1/0/1][0/1]$ 的值, 而我们知道, 对于一个有 $n$ 个 +1 和 $n$ 个 -1 的序列, 将其 shuffle 后, 前缀和绝对值的最大值是 $O(\sqrt n)$ 级别的. 所以我们直接 shuffle 一下所有儿子, 然后第二维强制要求过程中不能超过 $O(\sqrt n)$ 的 bound 即可.

讨论区里有两个不同的 $O(n \log n)$ 的做法, 留坑待填.

Round 3

[C] Sumy

注意到答案肯定是一段后缀合法, 所以二分一下即可.

[B] Mopadulo

记 $S_i = \left(\sum_{k=1}^i A_i\right) \bmod P$, 那么有以下显然的转移: $$ f_i = \sum_{j < i} [(S_i-S_j) \equiv 2 \pmod P] f_j $$ 根据 $S_j$ 与 $S_i$ 的大小关系即可知道会不会多加一个 $P$, 开两个树状数组维护一下就好了. 时间复杂度为 $O(n \log n)$

[A] Wystawa

首先, 我们先令每个 $i$ 取 $\min (a_i,b_i)$, 这样肯定会得到一组最优的方案, 但这个方案不满足恰好选了 $k$ 个 $a$ 的限制.

因此, 问题转化成了, 有 $n$ 个整数 $a_i,b_i$, 且 $\mathbf{a_i \leq b_i}$, 需要恰好选 $k'$ 个 $a_i$ 换成 $b_i$, 最小化最大子段和.

考虑以下求最大子段和的算法:

• 初始时 $ans \leftarrow 0, sum \leftarrow 0$
• 对 $i=1, 2, \cdots, n$:
  • $sum\leftarrow \max(0, sum + a_i)$
  • $ans \leftarrow \max(ans, sum)$

我们考虑对着这个过程 dp. 我们需要知道的信息有 $(i,j,sum,ans)$ - 其中 $i$ 表示现在考虑到哪一个数, $j$ 表示已经替换了多少个数. 注意到我们可以通过二分答案去掉 $ans$ 这一维度 - 只要保证他不超过我们当前二分的值 $mid$ 即可.

因此, 我们不妨设 $f_{i,j}$ 表示若当前考虑到第 $i$ 个数, 已经换了 $j$ 个 $b_*$, 且此时最大子段和不超过 $mid$ 的情况下, $sum$ 的值最小能是多少. 转移时秩序枚举这个数换还是不换, 并判定是否仍满足条件即可. 时间复杂度与空间复杂度均为 $O(n^2)$.

注意到整个问题是个费用流, 所以显然 $f_{i,*}$ 是凸的, 我们直接使用 std::set / std::priority_queue 来维护差分数组, 每次转移时会改头部的元素并删掉所有的负数. 容易发现只要我们把相同的一段 $0$ 缩起来那么复杂度就是对的. 在维护的过程中记录一下是怎么转移过来的即可构造出方案.

代码写了一年.jpeg

Round 4

[C] Ranking sklepów internetowych

首先注意到, 如果我们单独选出 $n$ 这个元素, 那么我们会得到的答案为 $2n+1$. 容易发现我们肯定不能比这个更优, 这是因为长为 $2l+1$ 的区间中位数最大也只能是 $n-l$.

对于计数, 我们直接枚举区间长度, 维护一下区间端点的合法区间即可.

[B] Skrzyżowania

考虑一个固定的起点 $s$, 假设我们在某个时刻 $T_0$ 中暴力 BFS 出所有可达的点, 记 $A_{x,y}$ 表示 $(x,y)$ 是否可达, 那么我们注意到如果 $(x,y)$ 可达, 那么我们考虑 $A_{x,y},A_{x+1,y},A_{x,y+1},A_{x+1,y+1}$, 一定长成以下三种矩阵之一: $$ \left[\begin{matrix} 1 & 1\\ 0 & 0\\ \end{matrix}\right],\left[\begin{matrix} 1 & 0\\ 1 & 0\\ \end{matrix}\right],\left[\begin{matrix} 1 & 1\\ 1 & 1\\ \end{matrix}\right] $$ 这是因为任意时刻任意路口水平线路与竖直线路至少有一条能走. 这便意味着, 我们合法的可行区间一定是一个矩形, 且这个矩形要么水平方向无限延伸, 要么竖直方向无限延伸.

考虑一次询问 $(x_1,y_1) \to (x_2,y_2)$, 我们将会说明, 其答案要么是从第 $x_1$ 行任意一点走到 $x_2$ 行任意一点的时间, 要么是从第 $y_1$ 列任意一点走到 $y_2$ 列任意一点的时间.

为什么呢? 以第一个 Case 为例, 假设初始时起点可达的点是延水平方向无限延申的, 那么我们考虑任意一个 $R_{x_1} \to R_{x_2}$ 的方案, 我们在第一步肯定可以直接走到起点(因为水平方向的点均可达). 随后, 如果我们走到终点的时候仍然是水平延申, 那么我们可以直接走到正确的终点. 否则, 此时可达区域必定是竖直延申. 那么注意到整个平面一定是被若干个这样竖直方向无限延伸的矩形划分了, 在这之前, 我们一定可以选择进入哪一个竖直划分的区域, 且无论走到哪里都是立刻走到终点, 所以这一定是一种合法的方案.

这告诉我们两个维度是独立的, 我们只需要解决一维的问题. 不妨假设我们考虑如何解决水平方向的问题. 注意到整个地图的周期是 $k=\operatorname{lcm}(1,2,3,\cdots, t) (t=8)$, 那么首先我们对于每个 $i$, 我们可以 $O(n \cdot \frac{k}{w})$ 算出这两行之间什么时候可达, 建图的时间复杂度为 $O(nmk/w)$. 随后, 我们用点 $f_{i,j}$ 表示目前在第 $i$ 行, 时间模 $k$ 为 $j$ 的一个状态. 由于我们肯定会贪心地往右走, 所以如果一个点有往右的边, 那么就一定不会走往下的边. 把这样的边去掉后, 图显然是无环的, 所以我们直接对森林中的每一棵树 dfs 即可维护出需要的信息. 询问时只需要找到对应点的深度大力差分以下即可.

第一步的过程比较慢, 可以优化: 我们直接爆搜出所有可能的红绿灯 bitset 的状态, 预处理它们 and 的结果即可. 复杂度是 $O(4^t \cdot k/w + nm)$ 的.

[A] Areny

Unsolved.

Round 5

[C] Butelki

状态总数是线性的, 所以直接 BFS 即可.

[C] Drzewo czerwono-czarne

首先特判掉以下平凡 Case:

• $c\equiv c'$, 输出 Yes
• $c$ 中只有一种颜色, 输出 No
• $c'$ 中, 任意 $(u,v) \in E$ 都有 $c'_u \ne c'_v$, 输出 No

前两个 Case 显然, 第三个 Case 是因为我们最后一次操作的时候肯定会造出来两个相同颜色的点, 所以不可能没有这样的点.

否则, 我们分类讨论:

1. 若存在某个度数 $\geq 3$ 的点, 输出 Yes
   1. 不妨假设这个点是 $x$, 且 $(x,a) \in E, (x,b) \in E, (x,c) \in E$
   2. WLOG 设 $c_x = 0$, 我们先证明一定可以转化成 $c_a=0,c_b=c_c=1$ 的 Case:
      1. 如果初始就满足, 显然合法.
      2. 若 $c_a=c_b=c_c=1$, 那么我们直接一次操作改 $c_a$ 为 $0$ 即可.
      3. 若 $c_a=c_b=0,c_c=1$, 那么我们一次操作改 $c_x$ 为 $1$ 即可.
      4. 否则, 任取一个有 $1$ 的点然过去即可.
   3. 从上可知, 只要我们想, 我们就可以造出这种特殊的结构. 现在我们的目标是让最后答案中这四个点的结构也长成这个样子.
   4. 如果在最后答案中, $c'_x = c'_a $ (或 $c'_b, c'_c$), 那么我们只要调一下颜色就正确了.
   5. 因此, 需要解决的 Case 为 $c'_x \ne c'_* (* \in \{a,b,c\})$. 根据平凡 Case 3, 我们肯定能找到 $(u,v)$ 使得 $c'_u = c'_v$. 不妨设 $u$ 是离根较近的一个点, 那么我们将 $u$ 到根路径上的点按顺序写下来: $\lambda_1, \lambda_2, \cdots, \lambda_t$
      • WLOG, $\lambda_1 = u, \lambda_{t-1} = a,\lambda_t = x$
      • 我们令 $c''_{\lambda_1} = c'_{\lambda_2}, c''_{\lambda_2} = c'_{\lambda_3}, \cdots, c''_{\lambda_{t-1}} = c'_{\lambda_t}$. 其余点仍满足 $c''_i = c_i$
      • 注意到如果 $c''$ 有解, 那么 $c'$ 立刻有解, 只要从底向上把这条链复原回去即可.
   6. 所以我们把 5 的情况都转化成了 4. 对于 4 的情况, 我们直接从底向上依次修每个叶子即可, 同样讨论一下颜色是怎么传的, 发现我们总是可以在不破坏这四个特殊点的结构的前提下把答案传过去.
2. 否则, 转化成了序列上的问题.
   1. 如果序列开头的元素不一样, 那么我们只能把头给删掉, 因为我们只能merge两个连续段, 不能swap或split
   2. 如果删掉以后, $c$ 的连续段数目 $<$ $c'$ 的连续段数目就是 No, 否则就是 Yes
   3. 证明仍然是类似的调整. 注意到我们总是有一段的长度 $\geq 2$, 所以我们一定可以通过伸缩一段让前面一段自由.

总的时间复杂度为 $O(n)$

[B] Autostrada

Unsolved

[B] Desant 2

我们建一张图:

• $i \to i+1$, 边权为 $0$
• $i\to i+k$, 边权为 $\sum_{j=i}^{i+k-1} a_j$

那么一组询问的答案就是 $u \to v$ 的最长路. 注意到如果我们把每个数表示成 $x=ik+j (0 \leq j < k)$ 的形式, 那么这张图基本是一个网格图. 仿照 ZJOI 旅行者那一道题目分治即可. 注意到比较恶心的是 $(i,k-1) \to (i+1,0)$ 的边, 所以我们在分治的时候需要看一下, 如果这是第一次沿着 $i$ 这一维切的话, 需要把第一行的贡献也跑出来.

直接写的话可能会得到一个跑40秒的垃圾做法, 所以不要建图BFS, 直接手动算一下每一类边的贡献, 这样可以快 10 倍.

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

[A] Zbiory niezależne

~~ GF 题狗都不做。~~

这个题之前我搬了个一模一样的, 视频题解里讲了, 暂时先不写了, 以后补一个(

[A] Fiolki

我们回顾一下这一道题: https://qoj.ac/problem/61

发现这道题与这个题基本一样, 我们同样对前 $k$ 个点取一个单位向量, 后面每个点都是其入边对应点的随机线性组合. 那么区间 $[l, r]$ 的答案就是 $\vec v_l, \vec v_{l+1}, \cdots, \vec v_{r}$ 张成线性空间的秩.

我们枚举 $r$, 并尝试将向量插入线性基中. 插入时, 我们在消元之前看一下这个元的编号是不是比它小, 如果小的话就swap以下, 这样保留出来的就是最大的一个线性基. 求出线性基以后维护一下对应的区间即可.

时间复杂度为 $O(md+nd^2)$. 有点卡常数, 需要精细实现一下.

https://codeforces.com/blog/entry/98200

同上, 组队的哥哥可以 PM 一下.

A. ABC Legacy

记 $c_A, c_B, c_C$ 分别表示每个字母的出现次数, $f_{AB}, f_{AC}, f_{BC}$ 表示每种匹配的出现次数, 那么显然有 $$ \begin{cases} c_A = f_{AB}+f_{AC}\\ c_B = f_{AB}+f_{BC}\\ c_C = f_{AC}+f_{BC}\\ c_A+c_B+c_C = 2n \end{cases} $$ 于是显然可以解出 $f_{AB}=n-c_C, f_{AC}=n-c_B, f_{BC}=n-c{A}$, 即每种匹配的数量是固定的. 考虑所有含有 B 的匹配, 注意到最后还要匹配 AC 型的pattern, 所以我们在选择匹配 B* 的时候, 肯定会尽量选择后缀一段 A 和前缀一段 C, 那么匹配的时候找到第一个能匹配的 B 显然是最优的. 如果最后配不出来, 就是无解.

B. New Queries On Segment Deluxe

留坑

C. Counting Phenomenal Arrays

首先说一下我们在现场的做法: 不妨设 $a_1\leq a_2 \leq \cdots \leq a_n$, 只计数有序的序列数量, 乘上对应的系数即可.

注意到 $a_1a_2\cdots a_n = a_1+a_2+\cdots+a_n \leq na_n $, 所以我们有 $a_1a_2\cdots a_{n-1} \leq n$, 即我们选出的数中, 去掉最大的数, 乘积不能超过 $n$.

而另一方面, 当我们确定了前 $n-1$ 个数后, 我们可以通过解方程 $Px = S + x$ 来求出 $x$ 的值, 因此我们不难设计出一个 dp: 设 $f_{i,j,\pi,\sigma}$ 表示已经填了 $i$ 个数, 上一次填的是 $j$, 目前乘积是 $\pi$, 总和是 $\sigma$ 的贡献总和.

但上述 dp 的复杂度过高, 我们完全无法接受. 但是注意到大多数状态是完全不可达的, 因此我们不妨将上述过程写成一个搜索的形式, 只搜索可能达到的状态. 通过暴力实现搜索, 我们可以轻松通过 $n \leq 1000$ 的数据, 但仍然无法通过本题.

注意到我们可以添加许多剪枝. 其中最重要的一个是, 我们考察当前填出来的状态, 并通过解方程解出此时最后一个数能填啥. 如果这个解出来的值已经小于目前的 $j$, 那么再填下去就没有意义了, 我们直接认为不合法. 同时, 再添加若干个不同的优化(例如不需要去枚举1的数量,最后算答案再计算), 我们便可以轻松通过本题.

上述算法看起来不太科学, 通过地比较侥幸, 那么有没有更靠谱的算法? 当然是有的. 我们还是计算有序序列的数量, 但这次我们规定 $a_1>1$. 我们不妨设 $\varphi(a) = \sum(a) - \prod(a)$, 则我们最终要求 $\varphi(a)=0$. 但注意到, 若 $b_i > 2$, 则必有 $\varphi(a_1 \cdots a_k) \leq \varphi(a_1 \cdots a_{k+1})$, 而初始时我们有 $\varphi(a_1)=0$, 因此我们只要开始填数, $\varphi$ 值就恒小于等于 $0$, 只能在最后填 $1$ 来补救.

由于一个 $1$ 只能恰好将 $\varphi$ 值加 $1$, 所以显然 $\varphi$ 值不能超过 $n$. 我们仿照上述过程实现一个 dfs, 当我们搜出一个 $b_1,b_2,\cdots,b_k(b_1>2, b_i \leq b_{i+1})$, 其积为 $\pi$, 和为 $\sigma$ 时, 我们有 $\varphi(b) = \pi - \sigma$, 显然我们只有在最后填恰好 $-\varphi(b)$ 个 $1$ 才能让他有可能有贡献, 所以我们任取一个不含 1 的序列, 其只有不超过 1 种方法使得其有贡献. 最后我们添加 $k$ 个 $1$ 的方案数即为 $\binom{k-\varphi(b)}{-\varphi(b)}$, 乘上对应贡献的系数即可.

所有元素大于 1, 且乘积不超过 $n$ 的序列非常的少, 通过暴力打表我们可以验证总的可能状态数可以接受, 且我们每次递归都能找到一个对应的解, 故整个过程的复杂度是有保证的.

D. LIS Counting

留坑

E. Flood Fill

首先注意到, 如果两个块 $A,B$ 是相邻的, 那么我们不可能同时将 $A,B$ 均反色. 因此, 我们的操作相当于选一个互不相邻的联通块集合 $S$, 使得最小化 $\sum_{i\in S}f(i) + \sum_{i \notin S}g(i) = \sum g(n) + \sum_{i \in S} (f(i)-g(i))$, 这是一个二分图最大权独立集问题, 所以直接写个网络流就好了.

F. to Pay Respects

首先注意到, 我们的操作可以分为两类, 一类减小 $r$, 另一类不减小.

对于不减小的那一类, 我们考虑最后一次这样的操作在时刻 $T$, 如果存在 $T_0 < T$ 且 $T_0$ 你没有操作, 那么你把这次操作转移到 $T_0$ 显然更优, 这是因为反正你也不能减小了, 不如先操作让对面增长地慢一些.这说明我们第二类操作一定占据了所有操作的一个前缀. 存在一个显然的贪心, 即考虑每个时刻 $i$ 对答案的贡献 $\Delta_i$, 如果这个时刻你操作, 那么如果对面操作, 你的贡献就是 $(n-i+1) \cdot (p+r)$, 否则是 $(n-i+1) \cdot p$, 这是因为你显然不会让对面有值的时候放过它到后面再操作, 所以只有对面是 $1$ 的时候才有可能减小. 这样我们直接排序并取前 $K$ 大, 时间复杂度为 $O(n \log n+K)$.

事实上, 根据进一步分析, 我们显然会从间断点后取一个 $1$ 的前缀操作, 所以我们可以直接做一个类似双指针一样的操作, 一开始取前 $k$ 个, 每次取后面第一个调整即可. 时间复杂度为 $O(n+K)$.

G. Replace Sort

首先将 $B$ 排序, 随后发现我们替换的时候位置显然是单调的. 设 $f_{i}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数不变的最小代价, $g_{i,j}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数替换成了 $B_j$ 的最小代价, $p(x)$ 表示最大的一个 $k$ 使得 $B_k \leq x$.

转移时, 对于 $f$ 直接枚举前面放没放:

• $f_{i} \leftarrow f_{i-1} (A_{i-1} \leq A_i)$
• $f_i \leftarrow \min_{1 \leq j \leq p(A_i)} g_{i,j}$

对于 $g$, 我们注意到如果前面替换成了 $B_k$, 那么这次一定替换成 $B_{k+1}$, 因为填更大的只会让后面的限制变得更严格, 所以:

• $g_{i,j} \leftarrow f_{i-1} + 1 (A_{i-1} \leq B_j)$
• $g_{i,j} \leftarrow g_{i-1,j-1} + 1$

直接做复杂度显然是 $O(n^2)$ 的, 注意到我们可以使用线段树来优化 $g$ 对 $g$ 的转移与 $g$ 对 $f$ 的转移 (只需要区间取min, 区间求min即可. 平移操作没什么用, 加的1全都是全局加). 总的时间复杂度为 $O(n \log n)$.

H. Werewolves

注意到如果一个联通块有贡献, 那么造成贡献的颜色只有恰好一种, 所以我们可以枚举这种颜色, 然后数有多少个有贡献的联通块, 这可以通过一个简单的树上背包 ( $dp_{i,\delta}$ 表示考虑以 $i$ 为根的子树, $i$ 必须选, 出现次数最多的元素减去总元素为 $\delta$ 的方案数 ), 总的时间复杂度为 $O(n^3)$.

注意到 $\sum_{i=1}^n c_i = n$, 而我们枚举颜色 $i$ 做树上背包的时候, size 显然是不超过 $c_i$ 的, 所以我们只需要做大小不超过 $k$ 的树上背包, 它的时间复杂度是 $O(nk)$ 的, 具体之前我讲杂题的时候讲了就跳过了.jpeg

综上, 总的时间复杂度为 $O(n^2)$

I. Colourful Permutation Sorting

留坑

J. Jason ABC

注意到两次操作是一定够的, 我们设 $f_{c,i}$ 表示 $\sum_{i=1}^n [s_i=c]$, 求最小的 $j$ 使得 $\max_{i \in \Sigma} f_{i,j} \geq n$, 随后两次操作把剩下两种不够的字符补齐即可.

所以只需要特判零次和一次操作. 零次操作显然, 一次操作的话, 我们枚举这种操作的是什么字符, 然后在枚举左端点, 右端点显然是单调的, 于是就稍微维护一下就做完了. 时间复杂度 $O(n)$

K. Amazing Tree

首先注意到第一个元素一定是某一个叶子, 不妨设编号最小的叶子为 $x$, 则我们序列的第一个元素必定为 $x$.

不妨设我们 dfs 时的根为 $r$, $x$ 的唯一邻居为 $y$

1. 若 $r = y$, 则我们在访问完 $x$ 后, 相当于从 $y$ 开始依次遍历每一个子树(除了 $x$), 显然我们还是会走到最小的叶子所在的子树内, 就变成了一个根确定的子问题.
2. 若 $r \ne y$, 则相当于要选择一个 $y$ 的子树, 当作根所在的联通块, 显然我们取最小叶子最大的那个子树当根是最优的, 随后 dfs 的时候, 非最大子树的相当于根已确定, 直接走完所有的子树, 剩下的那一个还是需要做类似的过程确定最优的 $r$

L. Primes and XOR? Nonsense

留坑

M. Many LCS

留坑

N. Max Pair Matching

不妨设 $a_i \leq b_i$, 那么 $w(i,j) = \max(b_i-a_j,a_i-b_j)$. 那么最大匹配的权值就是选出恰好 $n$ 个点当作 $b_i$, 另外 $n$ 个点当作 $a_i$, 最大化他们相减的值. 我们可以假设 $2n$ 个点全都选 $b_i$, 那么把一个 $b_i$ 改为 $a_i$ 的代价即为 $a_i+b_i$, 按照代价排序选 $n$ 个最小的减去就是答案.

http://blog.qingyu.us/2021/11/moscow-international-workshops-2021.-day-1./

Warning: 这场比赛可能会被用作 XXII Open Cup 的 GP of Poland, 如果你到时候想参赛的话就别看这篇博客了~

A. AMPPZ in the times of disease

首先注意到, 如果我们对每个 $S_1,S_2, \cdots, S_k$ 都确定了一个元素, 那么其余点显然只能选择距离其最近的一个关键点, 并加入这个集合(若有多个则显然无解).

令 $P_1 \in S_1$, 随后我们考虑距离 $P_1$ 最远的点, 不妨假设其为 $P_2$. (若有多个, 我们随便取一个即可)

那么, 如果 $P_2 \in S_1$, 那么 $f(S_1) \geq \mathrm{dist} (P_1,P_2)$, 但另一方面, 限制要求我们有 $f(S_1) \leq \min _{x \in S_1, y \notin S_1} \mathrm{dist}(x, y)$, 因此除非 $U \setminus S_1 = \varnothing$, 否则一定无解.

不妨设 $P_2 \in S_2$, 那么我们同样找到一个 $P_3$, 使得 $\min(\mathrm{dist}(P_1,P_3), \mathrm{dist}(P_2,P_3))$ 最小, 同样我们有 $P_3 \in S_3$.

这样重复 $k$ 轮, 我们就为每个集合都找到了一个关键元素. 时间复杂度为 $O(nk)$.

B. Babushka and her pierogi

留坑.

C. Cake

这个旋转操作看起来比较强大, 但是注意到旋转前后两维的奇偶性都会改变, 所以如果设 $b_{i,0} = a_{i,i \; \bmod 2}, b_{i,1} = a_{i,(i+1)\;\bmod 2}$, 那么旋转操作等价于交换两个相邻的 pair, 问题转化成给你一个序列, 问最少交换相邻元素多少次变成目标序列. 在没有相同元素的时候就是逆序对数, 而有相同元素时, 容易发现我们直接按顺序匹配就是最优的. 时间复杂度 $O(n \log n)$.

D. Divided Mechanism

直接暴力模拟即可, 难度全在读题上. 时间复杂度 $O(\sum nmq)$.

实现的时候如果直接维护整个图形可能有点难写, 直接记一下差分了多少即可.

E. Epidemic

留坑

F. Fence

首先注意到, 对于一个 $(a_i,b)$ 的二元组, 我们可以 $O(1)$ 求出其生成序列的奇数位置和与偶数位置和.

注意到当我们将 $b$ 变为 $b+1$ 时, 只有 $a_i \geq b$ 的位置的值变化了, 而这样的变化总数是不超过 $\sum_{b \geq 0}\sum_{i=1}^n [a_i \geq b] = \sum_{i=1}^n a_i = S$ 的, 所以我们可以直接暴力修改.

由于修改一个位置会影响后面位置的贡献, 我们可以开一棵线段树, 支持一下单点修改和区间换标记即可, 由于只有两种标记, 直接暴力存两个区间和即可. 时间复杂度为 $O(n + S \log n)$, 足够通过.

注意到我们修改的时候, 凡是这一轮没修改过的位置, 以后都不会再改了, 所以我们其实没必要线段树, 直接暴力维护即可. 对于删除操作, 直接使用链表维护即可, 时间复杂度为 $O(n+S)$.

G. Gebyte's Grind

如果我们将每个点看作一个映射 $f: \mathbb Z \mapsto \mathbb Z$ 的话, 那么这三类节点分别相当于:

1. $f(z) = \begin{cases}z-b & z > b\\ -\infty & \mathrm{otherwise}\end{cases}$
2. $f(z) = \begin{cases} c & z \geq c \\ -\infty & \mathrm{otherwise} \end{cases}$
3. $f(z) = \max (z, c)$

首先注意到第三类节点可以写成 $f(z) = \begin{cases} z & z \geq c \\ c & \mathrm{otherwise} \end{cases}$, 那么注意到, 我们任意取出若干个映射, 他们的复合一定可以写成 $(f \circ \cdots \circ f_*)(z) = \begin{cases} -\infty & z \leq a \\ c & a < z \leq b & \\ z + d & \mathrm{otherwise} \end{cases}$的形式(更特殊的, 其实一定有 $d=c-b$), 所以我们可以开一棵线段树, 每个节点维护这个区间的复合对应的映射长什么样. 容易发现我们可以 $O(1)$ 求两个映射的复合, 所以我们可以轻松合并标记. 对于修改操作, 我们直接做即可. 对于查询操作, 我们先从 $l_i$ 往上 jump, jump 的时候把 parent 对应的右儿子复合起来, 如果发现此时 $f(z)$ 已经是 $-\infty$ 了, 就代表需要左拐, 直接进去右儿子并不断往左跳即可(整个过程类似线段树二分). 总的时间复杂度为 $O((n+q) \log n)$.

H. Hidden Password

签到题.

I. Interesting Numbers

不妨假设 $a_i \in [0,2^b)$.

1. 如果 $k < 2^{b-1}$, 那么显然选出的数的最高位必须全都相同, 我们将最高位为 $0$ 和为 $1$ 的分开做即可, 转化为 $a_i \in [0,2^{b-1})$ 的子问题.
2. 如果 $k \geq 2^{b-1}$, 那么我们考虑建出一张图, 如果两个数异或小于等于 $k$ 连一条边, 答案即为图 $G$ 的最大团. 注意到最高位相同的 $a_i$ 之间一定会连边, 因此图事实上是两个团之间连了一些边, 求最大团.
   • 注意到 $G$ 的补图为二分图, 所以可以直接跑二分图最大匹配, 如果使用 Dinic 算法, 总的时间复杂度会达到 $O(n^{2.5} \log V)$, 无法通过.
   • 整个图的结构非常优秀, 我们可以考虑 Trie 树优化建图, 这样的时间复杂度优化到 $O(n^{1.5} \log n \log V)$, 可以通过. 当然, 如果做的时候精细实现一下, 把每一层重复的部分压缩起来, 应该可以做到 $O(n^{1.5} \log n + n \log V)$ (没写过, 口胡的)
   • 事实上不用这么复杂, 我们仍然可以使用类似分治的方法解决. 我们继续将两个团 $A,B$ 划分为第 $b-1$ 位为 $0$ 的部分 $A_0,B_0$ 与为 $1$ 的部分 $A_1,B_1$, 那么我们考虑 $k$ 的第 $b-1$ 位:
     1. 如果这一位为 $0$, 那么答案显然就是 $\max (f(A_0,B_0), f(A_1,B_1))$, 直接递归即可.
     2. 否则, 注意到只有 $A_0,B_1$ 与 $A_1,B_0$ 的部分需要决策, 答案即为 $\max(|A_0|+|B_0|, |A_1| + |B_1| , f(A_0, B_1), f(A_1, B_0))$.
   • 总的时间复杂度为 $O(n \log V)$

J. Jungle Trail

若起点与终点间不连通, 则无解. 否则, 容易发现, 我们任取一条起点到终点的长为 $n+m-2$ 的路径, 每次移动都会走到一个新的行/列, 直接调整这些位置就是一组合法的方案.

K. Kitten and Roomba

我们在走路的时候, 维护一个 $p_i$, 表示此时你站在 $i$ 号点的概率, 那么整个过程的答案可以使用以下过程求出:

1. 初始 $E \leftarrow 0$
2. 对于每一步所走的 $x$:
   1. 令 $E \leftarrow E + p_x$
   2. 对所有 $(x,y) \in G$, 令 $p_y \leftarrow p_y + p_x / \deg (x)$
   3. 令 $p_x \leftarrow 0$.
3. $E$ 即为答案

由于图是一棵树, 我们直接随便钦定一个点当根, 然后对于修改一个点邻居的操作, 我们变成修改它的父亲并在自己位置打一个标记. 查询的时候直接询问真实的值与父亲的标记相加即可. 时间复杂度 $O(n+m)$

L. Lemurs

容易发现如果一个位置能放, 那么我们放了显然不会让答案变劣, 所以我们能放就放是最优的.

而对于一个位置 $(x,y)$, 其能放当且仅当对所有 $|x'-x|+|y'-y| \leq k$ 的 $(x',y')$ 都是 x, 这可以通过转 Chebyshev Distance 后询问矩形和实现. 而求出答案后, 做同样的操作即可.

唯一的问题是虽然 $1 \leq n,m \leq 1000$, 但最坏情况下有 $50$ 组测试数据, 上述算法的时间复杂度为 $O(T(n+m)^2)$, 于是以 4.5 秒(时限4.0秒)的好成绩 TLE 了.

考虑一个常数更小的算法: 对于一个 ., 本质上其限制了预期 Manhattan 距离 $\leq k$ 的位置不能放, 所以相当于这些位置都被 ban 了. 我们对每个点维护一个 $f_i$, 表示这个点的距离限制, 那么我们按照 $f_i$ 从大到小 BFS, 即可求出所有被 ban 的位置. 最后合法的位置同样可以求出, 这样的时间复杂度就优化到了 $O(Tnm)$, 可以通过.

M. Median

留坑.

Auto Post by QOJ Editorial bot

Next Stage: Grand Prix of Seoul (7.17), Grand Prix of Bytedance (7.24), TBD (7.31)

Past Contests

News

本帖所有内容均来自 Open Cup News 频道(https://t.me/opencup_ru) 与官方网站 (http://opencup.ru), 若信息有冲突请以频道内容为准.

本帖所提及的发帖时间均指莫斯科时间 (UTC +3)

• 09/02/2021 15:49: The first three stages of new season will be based on Petrozavodsk contests: 12.09 will be Grand Prix of Dolgoprudny, 19.09 - Grand Prix of IMO, 26.09 - Grand Prix of XiAn (if there will not be an actual onsite/online to base the new GP, in that case the GP of XiAn will be moved to next Sunday). The GP's will start at usual time.
• 09/02/2021 15:49: The final of XXI season of OpenCup is planned approximately at November 2021.
• 09/02/2021 16:42: Due to troubles with new interface of Yandex.Contest admin console for the sector coordinators, the start of XXII season is moved for one week. So the first GP (GP of Dolgoprudny) is planned to Sep 12, GP of IMO - to Sep 19, GP of XiAn - to Sep 26.
• 09/02/2021 16:43: Probably the new registration for sectors / ext logins will be needed. The information (if any) will appear here.
• 10/07/2021 13:45: The Widesiberian Olympiad changed the rules for the selection contest from ACM to mixed ACM+marathon with variable scoring, so it cannot be used as the OpenCup stage at the current season. In next seasons the non-ACM scoring stages may be considered, but major last-minute changes are not acceptable. So the Grand Prix of Eurasia at Oct 10 is cancelled.
• 10/22/2021 14:23: The GP of Korea will take place at Oct 24, usual time.
• 10/24/2021 16:54: The summary standings for 4 stages are published now.
• 11/05/2021 15:34: The GP of Siberia will take place at Nov 7, usual time. The GP's are planned for Nov 14, 21 and 28, all usual time. The names for the GP will be announced later.
• 11/07/2021 11:18: The standings on Yandex are broken
• 11/07/2021 11:18: http://opentrains.snarknews.info/~ejudge/res/res10555
• 11/07/2021 11:18: Div 1 standings
• 11/07/2021 11:24: http://opentrains.snarknews.info/~ejudge/res/res10565
• 11/07/2021 11:24: Div 2 standings
• 11/07/2021 12:35: Builtin standings are working now
• 11/07/2021 15:16: The results of the Siberian Grand Prix will be added to the rating after 10:00 GMT Nov 8, after the Widesiberian Olympiad closing ceremony, where the last hour for the base contest teams will be opened.
• 11/11/2021 09:33: The GP of EDG will take place at Nov 14, usual time
• 19/11/2021 22:01: The GP of Southeastern Europe will take place at Nov 28, usual time. The Nov 21 will be the day off, no Grand Prix is scheduled for that day.
• 14/02/2022 16:31: The Grand Prix of Kyoto will take place at Feb 20, usual time. The Grand Prix of Daejeon will take place at Feb 27, usual time. The Grand Prix of Gomel will take place at Mar 6, usual time. The Grand Prix of Belarus will take place at Mar 13, usual time. The results of Petrozavodsk camp will be counted in those 4 GP's.
• 26/02/2022 14:17: The Grand Prix of Daejeon is postponed at least till Mar 6. The Grand Prix of Belarus is postponed till Mar 13, the Grand Prix of Gomel is postponed till Mar 20. The GP of Daejeon, however, is still open for the early participation by ext teams, the link is http://official.contest.yandex.com/opencupXXII/contest/35265/enter
• 05/03/2022 20:50: The Grand Prix of Daejeon is postponed at least till Mar 20. Further information will follow. The link for participation of the ext teams is still working. Additionally, here is the link for the partcipation of the ext teams for the next GP: http://official.contest.yandex.com/opencupXXII/contest/35268/enter
• 19/03/2022 20:39: The final date of the Grand Prix of Daejeon is Mar 27, original time.
• 27/03/2022 10:03: GP of Daejeon link: http://official.contest.yandex.com/opencupXXII/contest/35265/enter
• 27/03/2022 10:04: There will be no Div 2 today, for further GP Div2 is under consideration.
• 02/04/2022 13:38: The link on 12'th stage of the OpenCup - GP of Grushevka Div 1 contest: http://official.contest.yandex.com/opencupXXII/contest/35268/enter
• 06/04/2022 00:41: The 13'th stage of the OpenCup will be at Apr 10, usual time. The teams participating Petrozavodsk camp will have their results included in the final standings.
• 28/04/2022 11:44: The 14'th stage of the OpenCup, GP of BSUIR, will be at May 1,, usual time. The teams participating BSUIR Open Finals will have their results included in the final standings. The 15'th stage is planned on May 8, usual time.
• 28/04/2022 11:45: The OpenCup season will be prolonged approx to end of July, because some planned GP are postponed due to COVID issues in China.
• 29/04/2022 13:45: http://official.contest.yandex.com/opencupXXII/contest/37753/enter - Division 1 Link for Grand Prix of BSUIR
• 01/05/2022 09:59: http://official.contest.yandex.com/opencupXXII/contest/37754/enter - Division 2 Link for Grand Prix of BSUIR
• 04/05/2022 18:52: The 15'th stage, the GP of Yuquan, is planned on May 8, usual time. Teams that were participated in Prefinals MW will have their results included in the final standings. http://official.contest.yandex.com/opencupXXII/contest/37831/enter - Division 1 Link
• 26/05/2022 13:42: The 16'th stage, the GP of Urals, is planned on June 5, usual time. Teams that were participated in Championship of Urals, will have their results included in the final standings.
• 02/06/2022 14:17: The 16'th stage, the GP of Urals, is planned on June 5, usual time. http://official.contest.yandex.com/opencupXXII/contest/38278/enter - Division 1 Link
• 05/06/2022 10:55: There will be Division 2 contest today, the link is: http://official.contest.yandex.com/opencupXXII/contest/38279/enter
• 12/07/2022 16:55: The Bytedance camp finally started, so there will be Stage 17, GP of Seoul at Jul 17, usual time, and Stage 18, GP of Bytedance at Jul 24, usual time. The results of the camp participants will be integrated. And at Jul 31 will be stage 19.

本帖最后更新于 02/06/2022 16:22 (UTC +3)

以下为 opencup.ru 中给出的时间表. 本表最后更新于 06/12/2021.

The information about future stages will appear later.

Announcement

В XXII Открытом Кубке им. Е.В. Панкратьева по программированию, который планируется провести с сентября 2021 по май-июль 2022 года, предполагается проведение от 14 до 24 этапов. Первый этап Кубка состоится 12.09.2021. В этом сезоне традиционно основной системой для первого дивизиона Кубка будет Яндекс.Контест. Основной системой для второго дивизиона Кубка будет ejudge, для команд второго дивизиона организован спонсорский зачёт Moscow Workshops. Спонсорского зачёта от компании Яндекс в текущем сезоне не будет.
В этом сезоне планируется полная перерегистрация всех секторов (с перегенерацией паролей). Перерегистрация будет идти до 1 октября 2021 года. При перерегистрации будет проведена синхронизация данных в обеих используемых системах (ejudge и Яндекс.Контест), что позволит использовать единую консоль администратора сектора для обоих дивизионов. До окончания перерегистрации все логины не перерегистрировавшихся секторов остаются as is. Для команд, использующих логины с префиксом ext, синхронизация будет проведена позднее.
При перерегистрации сектора (и для регистрации нового сектора) необходимо отправить заявку на адрес site-register(сoбakа)opencup(тoчka)org. В теме письма указать "Перерегистрация" или "Регистрация нового сектора". В самом письме указать следующую информацию:

Для ввода имён команд и получения условий задач координаторы должны использовать консоль администратора. Ссылки на консоль администратора для системы ejudge и для системы Яндекс.Контест находятся в меню слева.

Updated I:

Первый этап XXII Открытого Кубка по программированию - Гран-При Долгопрудного - состоится 12.09.2021 в 11:00.
Командам, участвовавшим в сборах в Петрозаводске, в зачёт идёт результат, показанный в Петрозаводске.
В связи с проблемами с доступом к серверу opentrains.snarknews.info и недостаточным количеством перерегистрированных секторов команды второго дивизиона будут участвовать в предстоящем этапе в системе Яндекс.Контест. При этом наборы задач совпадают лишь частично (как обычно в Div 2).
В связи с пандемией коронавируса командам рекомендуется писать через удалённый доступ из дома (для коммуникации можно использовать программные средства типа skype, discord, zoom и им подобные). В функции координатора сектора входит только высылка паролей командам своего сектора, у которых есть проблемы с доступом (у новых или забывших пароль).
Первоначальную регистрацию производят координаторы секторов и подсекторов. Команды, которые хотели бы принять участие в Кубке в составе того или иного сектора, но ещё не сообщили о своём намерении участвовать в текущем сезоне Кубка координатору сектора, могут до 11:00 11.09.2021 отправить по e-mail координатора заявку. В заявке для каждой команды указывать название команды, имена и фамилии участников, учебное заведение, курс или класс для каждого из участников (если таковые определены).
Координаторы секторов и подсекторов обязаны заполнить окончательные составы участвующих в Гран-При команд не позднее 16:00 11.09.2021. Предварительные составы желательно заполнять до начала Гран-При.

Update II:

Седьмой этап XXII Открытого Кубка по программированию - Grand Prix of Southeastern Europe - состоится 28.11.2021 в 11:00. Командам, участвовавшим в MW International 2021, в зачёт идёт результат, показанный на сборах. В связи с переносом сервера ejudge и недостаточным количеством перерегистрированных секторов команды второго дивизиона будут участвовать в предстоящем этапе в системе Яндекс.Контест. При этом наборы задач совпадают лишь частично (как обычно в Div 2). В связи с пандемией коронавируса командам рекомендуется писать через удалённый доступ из дома (для коммуникации можно использовать программные средства типа skype, discord, zoom и им подобные). В функции координатора сектора входит только высылка паролей командам своего сектора, у которых есть проблемы с доступом (у новых или забывших пароль). Первоначальную регистрацию производят координаторы секторов и подсекторов. Команды, которые хотели бы принять участие в Кубке в составе того или иного сектора, но ещё не сообщили о своём намерении участвовать в текущем сезоне Кубка координатору сектора, могут до 11:00 28.11.2021 отправить по e-mail координатора заявку. В заявке для каждой команды указывать название команды, имена и фамилии участников, учебное заведение, курс или класс для каждого из участников (если таковые определены).

Past contests:

• Grand Prix of Dolgoprudny: Div.1, Div.2, Discussion
• Grand Prix of IMO: Div.1, Div.2, Discussion
• Grand Prix of Xi'an: Div.1, Div.2, Discussion
• Grand Prix of Eurasia: CANCELLED
• Grand Prix of Korea: Div.1, Div.2, Discussion
• Grand Prix of Siberia: Div.1, Div.2, Discussion
• Grand Prix of EDG: Div.1, Div.2, Discussion
• Grand Prix of Southeastern Europe: Div.1, Div.2, Discussion
• Grand Prix of Poland: Div.1, Div.2, Discussion
• Grand Prix of Nanjing: Div.1, Div.2, Discussion
• Grand Prix of Kyoto: Div.1, Div.2
• Grand Prix of Daejeon: Div.1 (No Div. 2 Contest)
• Grand Prix of Belarus Grushevka: Div.1 (No Div. 2 Contest)
• Grand Prix of Gomel: Div.1 (No Div. 2 Contest)
• Grand Prix of BSUIR: Div. 1
• Grand Prix of Yuquan: Div. 1
• Grand Prix of Urals: Div. 1, Div. 2

比赛可以鸽，暂别不行。

我们几个管理员 Qingyu, Qingyu, Qingyu 和我在过去的半年中，组织和举办了不少的比赛，也还算及时地将官方比赛题目上传到了 QOJ 中。

我一直非常喜欢 UOJ，在去年收到 Qingyu 的邀请后，我思考了一段时间，并决定来当 QOJ 管理，我想为这个美好的 OJ 献出自己的一份力量，让这个 OJ 变得更加好，如今看来，当时的目标也基本实现了。

在当管理的一年中，还是有很多事让我记忆深刻的，还记得 XXI Open Cup named after E.V. Pankratiev, Grand Prix of Siberia; XXI Open Cup named after E.V. Pankratiev, Grand Prix of Eurasia; 7 February, 2021 — Waterloo local contest; NOIP 2020; Petrozavodsk Winter 2021. Day 9. Grand Prix of Suwon; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Suwon; Petrozavodsk Winter 2021. Day 8. Belarusian SU Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Belarus; Petrozavodsk Winter 2021. Day 7. North American Contest 1; Petrozavodsk Winter 2021. Day 6. PKU Contest 2; Petrozavodsk Winter 2021. Day 5. Almost Retired Dandelion Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Nizhny Novgorod; Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1); Petrozavodsk Winter 2021. Day 3. Nordic+ Contest 2020 (NCPC-2020 with some BAPC/UKIEPC 2020); Petrozavodsk Winter 2021. Day 2. UPC Contest; Petrozavodsk Winter 2021. Day 1. Jagiellonian U Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Krakow; Nordic Collegiate Programming Contest 2020; Potyczki Algorytmiczne 2020; Runda 5; Potyczki Algorytmiczne 2020; Runda 4; Potyczki Algorytmiczne 2020; Runda 3; Potyczki Algorytmiczne 2020; Runda 2; Potyczki Algorytmiczne 2020; Runda 1; Potyczki Algorytmiczne 2020; Runda próbna; 2019-2020 ICPC Northwestern Europe Regional Contest; 2018-2019 ICPC Northwestern Europe Regional Contest; USACO 2020 January Contest (Platinum); USACO 2019 December Contest (Platinum); The 2020 Benelux Algorithm Programming Contest; USACO 2019 February Contest (Platinum); USACO 2019 January Contest (Platinum); USACO 2018 December Contest (Platinum); 2017-2018 ICPC Northwestern Europe Regional Contest; Nordic Collegiate Programming Contest 2019; 2019-2020 ICPC Southwestern Europe Regional Contest; 2020 Canadian Computing Olympiad Day 2; 2020 Canadian Computing Olympiad Day 1; International Olympiad in Informatics 2020 Day 2; International Olympiad in Informatics 2020 Day 1; Petrozavodsk Summer 2020. Day 6. Korean Contest; Petrozavodsk Summer 2020. Day 5. JAG Summer 2019+; Petrozavodsk Summer 2020. Day 4. Xi Lin Contest 6; Petrozavodsk Summer 2020. Day 3. Songyang Chen Contest; Petrozavodsk Summer 2020. Day 2. SPb SU LOUD ENOUGH Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of SPb; Petrozavodsk Summer 2020. Day 1. Warsaw U Contest; USACO 2018 February Contest (Platinum); USACO 2018 January Contest (Platinum); USACO 2017 December Contest (Platinum); 2020-2021 ICPC North America - Pacific Northwest Regional Contest - Division 2; 2020-2021 ICPC North America - Pacific Northwest Regional Contest - Division 1; 2020-2021 ICPC North America - Mid-Atlantic USA Regional Contest; 2020-2021 ICPC North America - Mid-Central USA Programming Contest; 2020-2021 ICPC North America - East Central NA Regional Contest; 2020-2021 ICPC North America - Rocky Mountain Regional Contest; 2019-2020 ICPC North America - Rocky Mountain Regional Contest; Russia Open 2020 High School Team Programming Contest 2020-09-08 08:30:00 3 hours 30 minutes No ×0 IOI 2018 中国国家队清华集训 Day 4 (CTT 2017 Day 4); IOI 2018 中国国家队清华集训 Day 3 (CTT 2017 Day 3); IOI 2018 中国国家队清华集训 Day 2 (CTT 2017 Day 2); IOI 2018 中国国家队清华集训 Day 1 (CTT 2017 Day 1); 前 D 题发生了一系列事故，导致比赛前一天 Qingyu 哥哥晚上一点多写好 std，我三多造好数据，然后还发现了同样没睡在内卷的 hy，第二天起来一看 Qingyu 说他第一步假了，暴力和 std 都是错的，换上了现在的题意，11 点 Qingyu 写完 std 然后我造数据传好就弃疗了。以及后来的 QOJ Training Series 和 Qingyu 哥哥熬夜造 E 题等等 （主要原因还是我们太鸽），不过相信下一届管理员会比我们做得更好！

现在 NOI 也顺利结束了，又一批 OIer 完成了他们最重要的一战，而 QOJ 也到了换届的环节，下一届将有四个管理员，他们是：

Qingyu、Qingyu、Qingyu、Qingyu

祝你们一切顺利，QOJ 越办越好！

Online Contests

Opentrains

• Opentrains Logins
• Opentrains Contests
• A complete list
• Official contest list

Yandex

• Yandex Contests

Open Cup

• opentrains
• Official Website
• List of all Open Cup contests

AtCoder

• AtCoder test cases
• Kenkoooo

TopCoder

• Contest Archive
• Problem Archive

Polish Contests

• Olimpiada Informatyczna
• Szkopuł
• OIOIOI

Training Camp

• List of all Petrozavodsk Contests

OI Contests

ICPC Contests

http://oj.qingyu.us/archive/icpc/

为了避免自己的账户泄露，建议不要在大机房中使用浏览器的“保存密码”功能！！

若认为自己的密码已经泄露，需要在修改密码后使用 登出所有活跃会话 功能，否则此前认证过的会话可能不会失效。

同时，为了避免权限组的题目泄露，hydd 大神指示各位 hy 的粉丝 使用强度较高的密码，请不要使用诸如 123456、114514、19260817、hyakcts、ilovechino 的弱口令。

FTP 所有账户已重置，请有 FTP 权限的群友查看系统消息获取最新的用户密码。对于 Archive 中一些公开的测试数据，建议大家转至 Google Drive 镜像进行下载。

不建议在博客中写模拟赛题的题解，如果需要写内部题的题解，一定注意添加权限。所有内部题目的讨论博客需要拥有 access-secret-blogs 权限与校内团队（目前有 $12,16,17,19,22$ 五个团队）权限才可以查看。

本公告的最终解释权归 hydd 所有。

Discovery Hailiang Logins

这个东西在若干个群友监督下随机生成的,他们都表示直接通过!

随机生成器是 @Qingyu 瞎写的,有问题就喷他.

在随机现场的 @hydd, @Lenstar 表示这个真的是一次随机生成的.

因为一些原因去随便找了个爬虫爬了下来所有比赛名称。

下面是部分内容展示，完整版请见附件下载：

Part I: contest.yandex.ru

最后更新：2021.02.19，更新至比赛 id 25209

……

下载附件