Note: Due to the rapid growth of our contest archive, we have ceased posting new contest announcements here as of 2024.

06/15/2026

한국 친구들 안녕하세요!

We have added Korean translation support to the website. The translation was completed mainly with the help of AI, so there may still be some minor mistakes.

If you find any issues or unnatural wording in the translation, please share them under this announcement. I will fix them as soon as possible. 감사합니다!

06/12/2026

The judge now supports auxiliary judging files out of the box, without requiring a custom judger to control the compilation process.

Two new problem.conf keys have been introduced: n_aux_files and aux_file_<i>. Files declared through these keys are copied from the upload directory to the preparation directory before the checker, validator, interactor, and standard solution are compiled. This allows grader sources to use #include "..." directives that resolve against these auxiliary files. (For with_implementer standard solutions, header files in require/ continue to take precedence as before.)

For security reasons, auxiliary file names are validated against a restricted character set, and the reserved files such as problem.conf and download.zip cannot be used as auxiliary files.

05/27/2026

We added support for subtasks in output-only tasks. By default, contestants submit a single output file for each subtask, and that output will be used to judge all test cases within the corresponding subtask.

An example task that uses this feature is Pebbling Odometer from IOI 2012 Day 1.

05/20/2026

We added more granular permission controls for blog posts. You can now designate co-authors and shared viewers for any blog you publish.

05/17/2026

For task uploaders, you may now use the syntax score_precision N or subtask_score_precision_i N in problem.conf to control score rounding behavior. Scores will be rounded to N decimal places.

04/20/2026

1. We introduced a Favourites feature that allows you to bookmark problems, contests, blogs, and users. Your favourites list is private and visible only to you.
2. We implemented an automated verification process for AI-translated statements. We plan to roll out batch translations for all problems on QOJ after further testing and validation.

03/14/2026

1. Official tutorials will no longer appear as an Editorial button on individual problem pages. Instead, they can be found in the Discussion section alongside user editorials and general discussions.
2. User-created editorials can now be posted anonymously.

12/22/2025

We updated our C/C++ compilers to GCC 15.2.0, our Rust compilers to rustc 1.92.0.

We also added the support for PyPy 3, Fortran, Ruby, and Lean 4. Detailed information can be found at here

12/16/2025

We updated the user modification portal. You may now choose your preferred language to display when multiple statements available.

12/12/2025

We have updated the issue report feature for each problem. Every problem now has its own independent discussion thread, where you are welcome to post discussions, editorials, or any other related content in the problem forum. All posts are public, making it easier for everyone to find relevant discussions and reference materials.

12/09/2025

You may now sort problems by their user rating in the problem set page.

12/02/2025

We have redesigned the user information editor page. Try our new portal in the modify my profile tab.

11/21/2025

We released the new version of our task proposal system. The guide on submitting your tasks can be found here

11/20/2025

We introduced an "Issues" feature. You can now report configuration errors for problem sets via the "Issue" tab located on each problem page.

08/27/2025

We added the feature for linking your team accounts with your QOJ accounts. As we are still testing this feature, linking accounts are only available for the U-Cup accounts. You can access our edit portal by using your U-Cup team account.

08/20/2025

We upgraded the compilers of our judge. The updated compilers info can be found here

07/19/2025

We upgraded the category statistics system. Now, for each category, duplicated task in different contests are only counted once.

06/10/2025

We upgraded our category system. The categories list now shows your personal progress in each tasks set.

06/02/2025

We upgraded our judging server. You can view more details here.

05/15/2025

We have introduced Training Mode, which can be enabled from your personal profile page.

When Training Mode is active, the system hides many of the usual “friendly reminders” during virtual contests — such as failed test cases, detailed judging feedback, and more. This feature is designed to simulate the environment of the ICPC World Finals.

03/19/2025

1. You can now upload the avatars directly on "modify profile" page. Gravatar is still supported and recommended to use.

01/13/2025

1. We updated the compilers and judging environment. More details can be found here

12/10/2024

1. The scoreboard now shows SE ("average hardness").

10/11/2024

1. The contest list now shows an estimated difficulty for the contests.

08/14/2024

1. Updates for the scoreboard of ICPC-style competitions
2. The Battle of Giants and External Scoreboard pages now refresh automatically.

05/12/2024

1. 更新 Python 3 版本为 Python 3.12.3。
2. 更新 DMD 版本为 DMD64 D Compiler v2.108.1。
3. 更新 rustc 版本为 rustc 1.75.0 (82e1608df 2023-12-21)。

04/28/2024

1. 增加了对 IOI 赛制比赛中关于子任务取最大值规则的支持。现在在 QOJ 上进行的 IOI 赛制的比赛将会使用标准的 IOI 评分规则（即，每个子任务的得分为所有提交记录该子任务得分的最大值；每个题的得分为所有子任务的得分之和。）
   • 同时，在 IOI 赛制的比赛中会存在 “My Score” 选项卡，展示当前你的得分。

04/24/2024

1. 修复了 Virtual Contests 时提交时间可能显示不正确的 bug。
2. 现在比赛的管理员可以设置每道题目提交次数限制与提交间隔限制。

01/16/2024

1. 更新 GCC 版本为 GCC 13.1.0。
2. 更新 Python 3 版本为 Python 3.12.1。

12/25/2023

1. 添加对 D 的支持，采用的编译器版本为 DMD64 D Compiler v2.106.0，编译选项为 -O -release -inline -boundscheck=off

09/29/2023

1. 添加对 Rust 的支持，采用的编译器版本为 rustc 1.70.1，编译选项为 rustc -o answer -C opt-level=3 answer.code
2. 将提交记录的代码高亮库更换为 highlight.js

09/11/2023

1. 主站的评测机数更改为 5 台。每台评测机的 CPU 均为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。其中评测机 #1 的内存为 32 GiB，其余两台评测机的内存为 16 GiB。
2. 修改了沙盒中的部分实现。由于此前编写的 judger 有部分不兼容新的沙盒，因此目前所有使用了自定义 judger 的题目均被暂时隐藏。他们将在确认兼容性后重新公开。

08/28/2023

1. 增加了对可任意选择 Time Window 开始时间赛制的支持。
2. 增加了对包含多个固定的 Time Window 的赛制的支持。
3. 增加比赛管理员可以为某个用户单独延长比赛时间的特性。
4. 比赛管理员现在可以取消用户的报名。
5. 修复了在 Time Window 结束后的提交仍然会被算入比赛提交的 bug。
6. 不再禁止用户选择开始时间比当前时间更早的 Time Window。
7. 比赛结束后的提交现在也可以在比赛提交记录中查看。

08/22/2023

1. 主站的评测机数更改为 3 台。每台评测机的 CPU 均为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。其中评测机 #1 的内存为 32 GiB，其余两台评测机的内存为 16 GiB。

08/10/2023

1. QOJ 开始记录评测记录的历史信息！

08/04/2023

1. 在注册 Virtual Contests 时会弹出确认列表。
2. 修复了在 VP 时可以查看题目统计信息的 bug。
3. 修复了在 IOI 赛制的 VP 时可以查看测试点详细信息的 bug。

06/14/2023

评测机所使用的 CPU 由 Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz 更换为 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz。

04/27/2023

1. 在 VP 时 Attachments 会默认隐藏题解。
2. 在 VP 时禁止查看比赛中其他人的提交记录。

03/21/2023

Category 增加显示每个子类别比赛与题目数。

03/19/2023

进行了一些微小的更新。

03/04/2023

1. 对应比赛的管理员可设置在比赛进行时排行榜的显示范围（是否显示正式选手/Virtual 选手，以及每类 Ghosts 的范围）
2. 对应比赛的管理员可导出比赛的 Standings 文件（.dat / TestSys 格式）
3. 在导入 Polygon 格式的题目时，使用标准校验器的题目将默认配置 use_builtin_checker，而不再使用独立的 checker。
4. 检验数据正确性不再要求配置 Main Correct Solution。

02/25/2023

1. 修复了无开始时间的比赛 VP 后不会滚榜的 bug。
2. 修复了 Category 对比赛排序时产生的问题。

02/18/2023

进行了一些微小的更新。

02/13/2023

进行了一些微小的更新。

02/03/2023

1. ICPC 赛制现支持设定封榜。
2. 修复了部分通信题出现 Dangerous Syscalls 的问题

01/09/2023

更新编译器信息如下：

• Python2: Python 2.7.18
• Python3: Python 3.10.9
• C/C99/C11/C++/C++98/C++11/C++14/C++17/C++20/C++23: GCC 11.1.0
• Java 8/Java 11: openjdk version "11.0.16"
• Pascal: fpc 3.0.4+dfsg-23

万能的 p_b_p_b 说：要有 CTS Round，于是 pjudge 有了 CTS Round。

大家 2023 年新年快乐！作为 pjudge 在 2023 年复活后的第一场比赛，Public CTS Round #1 将在 2023 年 1 月 7 日与 1 月 8 日 8:30 举行！

比赛将分为两日进行，每场比赛时间为当日上午 08:30 至 13:30，共 5 小时。每场比赛均为 IOI 赛制，且包含三道题目。

本次比赛的题目难度可参考 CTS 2022。 比赛的组题人为 p_b_p_b 与 Qingyu，搬题人为 alpha1022, flower, hehezhou, p_b_p_b, Qingyu。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

• 搬题人：
  • 咖啡, 画图：Qingyu
  • 治病, 拓扑序计数：feecle6418
  • 序列：Wu_Ren
  • 水果：p_b_p_b
• 组题人：Qingyu
• 题解：alpha1022, feecle6418, Wu_Ren, p_b_p_b

咖啡 (Div. 2 Only)

来源：

• Nordic Collegiate Programming Contest 2022. Problem C. Coffee Cup Combo
• https://qoj.ac/contest/1024/problem/4990

Tutorial by alpha1022.

不妨采用贪心策略：能喝则喝。

从左往右扫描，维护当前手中有几杯咖啡即可。

画图 (Div. 2 Only)

来源：

• All Ireland Programming Olympiad 2017 National Finals. Problem C. Paint bucket
• https://qoj.ac/contest/11/problem/48

Tutorial by alpha1022.

采用深度优先搜索或广度优先搜索得出 $(x,y)$ 所在的连通块并染色即可，需要保证每个格子不被重复访问。

治病 (Div. 1 + Div. 2)

来源：

• Petrozavodsk Winter 2020. Day 4. Yandex Cup 2020. Problem B. Bad Doctor
• http://qoj.ac/contest/444/problem/686

Tutorial by feecle6418.

首先我们要算出，如果不忽略任何医生，尼特花费的钱数。根据题意我们知道，对于某种药片，尼特吃这种药片的时间就是所有医生药方里的时间的并集，也就是给出一些区间让你求并。这是经典问题，按照左端点从小到大排序，维护当前最大的右端点即可。

如果忽略某个医生，只需要找到只被这一个医生覆盖的 (药片,时间) 二元组，把这些二元组的贡献减掉。对每种药片分开考虑，也就是对每个区间，求出只被这一个区间覆盖的位置的总长度。首先用差分求出每个位置被覆盖了多少次，找出只被覆盖一次的位置，把这些位置的权值赋值成 1，对权值做前缀和，然后求出每个区间内的位置的权值之和，就是只被这一个区间覆盖的位置的总长度。

所有差分、前缀和都需要在离散化之后的坐标上进行，瓶颈在于离散化，总时间复杂度为 $O((\sum K)\log (\sum K)+n+m)$。

拓扑序计数 (Div. 1 + Div. 2)

来源：

• Petrozavodsk Winter 2020. Day 4. Yandex Cup 2020. Problem C. Topological Ordering
• http://qoj.ac/contest/444/problem/687

Tutorial by feecle6418.

设 $f(S)$ 表示按照拓扑序从前往后的顺序加点，初始为空集，到已经加入 $S$ 这个点集，这一段的加点方案数。设 $g(S)$ 表示按照拓扑序从后往前的顺序删点，初始为全集，到现在还剩下 $S$ 这个点集，此时删除顺序的方案数。$f,g$ 都可以在 $O(2^nn)$ 时间内简单地 dp 求出。

对于给定的 $u,v$，$u$ 在 $v$ 前，就是要，拓扑序加入 $v$ 那一刻，$u$ 已经在拓扑序里了。所以，$ans_{u,v}=\sum [u\in S,v\notin S]f(S)g(S\cup \{v\})$（枚举加入 $v$ 之前一刻，有哪些点加入了拓扑序）

直接实现该算法的时间复杂度为 $O(2^nn^2)$，但 $S$ 的枚举有 $1/4$ 的常数，已经可以过。

当然，上述算法还可以继续优化到 $O(2^nn)$：枚举 $S,v$，相当于 $\forall u\in S$，$ans_{u,v}$ 都加上一个定值。因此瓶颈在于：“给出 $a_{0}\sim a_{2^n-1}$，对所有 $u$ 求出 $\sum_{u\in S}a_S$”。可以用下面的方法：

for i from n-1 downto 0:
    for j from 2^i to (2^{i+1}-1):
        ans[i]+=a[j]
        a[j-2^i]+=a[j]

最后 $ans_u$ 就是答案。因此我们把 $O(2^nn)$ 的循环优化到了 $O(2^n)$。（但是实际上速度仅仅变快了不到一倍）

序列 (Div. 1 Only)

来源：

• Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1). Problem H. Longest Loose Segment
• http://qoj.ac/contest/532/problem/894

Tutorial by Wu_Ren.

由于答案有可二分性，直接获得 $O(nm\log n)$ 做法。

下面是正解：

考虑每次建出小根笛卡尔树，并且在笛卡尔树上 dp。

我们对于每个节点，维护子树内 $a_i$ 最大值 $mx$，区间长度 $sz$，最长合法子段长度 $len$。

假设 $u$ 的两个儿子为 $lc,rc$，那么考虑合并 $lc,rc$ 的信息来得到 $u$ 的信息。

$mx,sz$ 的合并是显然的。考虑 $len$ 的合并，首先，假如合法子段不经过 $u$，那么就是 $len_u\leftarrow \max(len_{lc},len_{rc})$。假设存在 $u\in[l,r]$ 使得 $[l,r]$ 是合法子段，那么假设 $\max\limits_{i\in[l,u-1]} \{a_i\}\ge \max\limits_{i\in[u+1,r]} \{a_i\}$，此时我们可以发现，如果 $l>u-sz_{lc}\land r>u$，那么 $[l-1,r-1]$ 也是合法的。

那么就可以知道，我们可以认为跨越 $u$ 的合法子段要么一个端点是 $u$，要么一个端点是 $u-sz_{lc}$ 或 $u+sz_{rc}$。

这里可以发现，假如 $[l,u]$ 是合法子段且 $l>u-sz_{lc}$，那么 $[l-1,u-1]$ 也是合法子段，所以说一个端点是 $u$ 且另一个端点不是 $u-sz_{lc}$ 或 $u+sz_{rc}$ 的情况一定不优于 $\max(len_{lc},len_{rc})$。

那么我们只需要考虑一个端点在 $u-sz_{lc}$ 或 $u+sz_{rc}$，并且过 $u$ 的情况了（也就是说，我们只需要考虑至少把一颗子树完全包含的情况），这个转移是显然的。

复杂度 $O(nm)$。

水果 (Div. 1 Only)

来源：

• (Singapore) National Olympiad in Informatics 2022. Problem E. Fruits
• http://qoj.ac/contest/919/problem/3875

Tutorial by p_b_p_b.

为了方便，先把 $a_i\ne -1$ 且无论如何都无法成为前缀最大值的水果删掉。

为了方便，再把水果的美味度修改一下，使得没有确定位置的水果的美味度是 $1,2,\cdots,m$ ，而确定位置的水果的美味度则是夹在中间的小数。

设 $a_1,\cdots,a_n$ 是读入的方案，$A_1,\cdots,A_n$ 是最终的方案。

放弃思考，直接设 $dp_{x,v}$ 表示确定了 $A_1,\cdots,A_x$ ，且其中最大值小于 $v+0.99$ （$v$ 是整数），考虑如何转移。

• 如果 $a_x\ne -1$ ，那么有两种选择
  • 让 $a_x$ 成为最终的前缀最大值，那么从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移。
  • 扔掉 $a_x$ ，从 $dp_{x-1,v}$ 转移。
• 如果 $a_x=-1$ ，再分两种
  • $a_1,\cdots,a_{x-1}$ 的最大值小于 $v$ ，那么这里肯定应该贪心放 $v$ ，从 $dp_{x-1,v-1}+c_v$ 转移。
  • 否则这里只能被迫开摆，随便放个以后不用的小的，从 $dp_{x-1,v}$ 转移。（注意因为我们做过预处理，所以这里总是可以保证不超过 $v$ 。）

于是就获得了一个非常垃圾 $O(n^2)$ 做法，下面考虑优化。

• 对于 $a_x\ne -1$ ，注意到 $dp_{x,0},\cdots,dp_{x,m}$ 单调不降，因此一定是一个前缀从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移，而其他地方直接把 $dp_{x-1,v}$ 拉过来。因此只要二分分界点就可以直接前缀赋值。
• 对于 $a_x=-1$ ，显然只有一个合法状态会从 $dp_{x-1,v}$ 转移，剩下的都从 $dp_{x-1,v-1}+c_v$ 转移。不过这个怎么维护呢？

设 $S_i=\sum_{j=1}^i c_j$ 表示 $c$ 的前缀和。另外设 $pre_x$ 表示 $a_1,\cdots,a_x$ 有几个 $-1$ 。

对每个 $dp_{x,v}$ 维护一个二元组 $f_{x,v}=(x',y)$ ，表示 $dp_{x,v}=S_v-S_{v-(pre_x-x')}+y$ ，那么就做完了：从 $dp_{x-1,v-1}+c_v$ 转移，就等价于 $f_{x,v}=f_{x-1,v-1}$ 。而其他转移也都是简单的单点或区间赋值。

暴力线段树就能维护了。还可以再好看一点，用双端队列来维护二元组的连续段，但其实区别不大。

Public NOIP Round #4 将在 2022 年 11 月 20 日 8:30 举行！

比赛分为普及组和提高组，普及组进行 3.5 小时，提高组进行 4.5 小时。普及和提高分别有 4 道题，OI 赛制，其中普及组和提高组有两题相同。

与上一次比赛相同的是，本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛，而 MarsOJ 则可以提供仿真 csp/noip 考场环境的云电脑，具体可以加入用户群（915426363）。 选手可以根据自己的训练需要来自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

本次比赛的题目难度约为 CSP-J / noip ，所有题目都有部分分。

本次模拟赛的组题人为 Qingyu ，搬题人为 Qingyu, Wu_Ren, p_b_p_b, feecle6418。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

• 搬题人：
  • 数字：gyh20
  • 因子：Wu_Ren
  • 移除石子：feecle6418
  • 抓内鬼：p_b_p_b
  • 异或序列：feecle6418
  • 数圈圈：feecle6418
• 组题人：hehezhou
• 题解：gyh20, Wu_Ren, feecle6418, p_b_p_b

数字 (Div. 2 Only)

来源：AtCoder Beginner Contest 182 (https://atcoder.jp/contests/abc182/tasks/abc182_c)

Tutorial by gyh20.

做法 $1$：

直接搜索每一位是否删掉，时间复杂度可以做到 $2^{\log n}\log n$ 或者 $2^{\log n}$，这里的 $\log$ 是以 $10$ 为底的，可以通过。

Submission #56492 - Public Judge (pjudge.ac)

做法 $2$：

我们知道，一个数字能被 $3$ 整除，当且仅当其所有数位之和是 $3$ 的倍数，所以我们一定不会删数位是 $3$ 的倍数的这些位，同时也不会删三个 $\bmod 3$ 相同的位，同时也不会同时删 $\bmod 3=1$ 的和 $\bmod 3=2$ 的，这样我们就知道答案不超过 $2$。

于是求出所有数位上有多少个 $\bmod 3=1$，多少个 $\bmod 3=2$，分类讨论一下即可。

Submission #56801 - Public Judge (pjudge.ac)

因子 (Div. 2 Only)

来源：

• Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem B. Non-Trivial Common Divisor
• ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem B. Non-Trivial Common Divisor
• https://qoj.ac/contest/505/problem/1336

Tutorial by Wu_Ren.

容易知道 $k$ 取某个质数最优，开个桶统计每个质数的答案即可，复杂度 $O(\sum \sqrt{a_i}+\omega (a_i))$。

移除石子 (Div. 1 + Div. 2)

来源：

• Petrozavodsk Winter 2020. Day 4: Yandex Cup 2020. Problem H. Delete the Points
• https://qoj.ac/contest/444/problem/692

Tutorial by feecle6418.

算法一

对于前三个测试点，可以从左往右删，第 $i$ 次输出 $(4i,4i,4i-2,4i-2)$。

对于第四、五个测试点，可以从下往上删，按照纵坐标顺序，第 $i$ 次删掉排在第 $2i-1$ 位、第 $2i$ 位的点即可。

结合起来期望得分 $50$。

算法二

大胆猜想一定有解。

算法一中的讨论指引我们从边上开始删。

将所有点按照横坐标从小到大排序，相同的按照纵坐标从小到大排序。不妨在该顺序中从后往前删。设在该顺序下，最后一个点为 $X$，倒数第二个点为 $Y$，倒数第三个点为 $Z$。

但是不一定合法，我们分类讨论几种情况：

1. $X,Y$ 都是横坐标最大的点，这时靠右放个正方形，可以删掉 $X,Y$。

   

2. 横坐标最大的点只有 $X$。

   1. $Y$ 的纵坐标小于或等于 $X$ 的纵坐标，则放一个以 $Y$ 为左下顶点的很大的正方形。

      

   2. $Y$ 的纵坐标大于 $X$ 的纵坐标。

      1. $Z$ 的横坐标等于 $Y$ 的横坐标，$Z$ 的纵坐标大于 $X$ 的纵坐标。

         这时以 $YZ$ 为一边放一个正方形就可以删掉 $Y,Z$：

         

      2. $Z$ 的横坐标等于 $Y$ 的横坐标，$Z$ 的纵坐标恰好等于 $X$ 的横坐标。

         这时以 $YZ,ZX$ 中短的一边作为正方形的一条边，比如下图中 $YZ\le ZX$，就这样画：

         

         注意，为了防止 $YZ=ZX$ 时把 $XYZ$ 三个点恰好都框住，需要把正方形偏移 0.5 个单位，这也是题目允许输出小数的原因。

      3. 不是以上两种情况，则以 $(x_Y,y_X)$ 为左下角作一个很大的正方形即可：

         

瓶颈在于排序，时间复杂度为 $O(n\log n)$，期望得分 $100$。

如果某些情况讨论漏了，可以得到 $90$ 分，因为数据随机时很难覆盖所有情况。

抓内鬼 (Div. 1 + Div. 2)

来源：

• Noric Collegiate Programming Contest 2021. Problem C. Customs Control
• Petrozavodsk Winter 2022. Day 4: Almost Northern Contest. Problem C. Customs Control
• https://qoj.ac/contest/822/problem/1774

Tutorial by p_b_p_b.

算法一

$k=1$ 。

不难想到一个简单策略是只在点 $1$ 处放一个 uoj 壮丁，其他地方都放 pjudge 壮丁。这种策略只会在 $1$ 和 $n$ 有边时失败，但此时唯一的最短路就是从 $1$ 一步走到 $n$ ，因此只要 $n\ge 3$ 就可以在 $1,n$ 都放 pjudge 壮丁，就解决了。

算法二

$u_i\in \{1,n\}$ 或 $v_i\in \{1,n\}$ 。

同样先特判掉 $1,n$ 有边的情况，然后不难发现只要给 $1$ 和 $n$ 分配不同来源的壮丁，剩下的点随便分，就一定可以掐断所有路线。或者如果 $k=0$ 或 $k=n$ 也是显然有解的。

算法三

一般情况。

沿用算法二，先给 $1,n$ 分配不同来源的壮丁，不妨假设 $1$ 的壮丁是 P 而 $n$ 的壮丁是 U 。

可以发现，如果存在边 $(1,x)$ ，并且 $x$ 的壮丁也是 P ，那就相当于把 $x$ 从图里删掉了。这是因为从 $1$ 不能一步走到 $x$ ，而其他拐一个弯再到 $x$ 的走法不可能是最短路。存在边 $(y,n)$ 且 $y$ 的壮丁是 U 的情况同理。

因此只需要把 pjudge 壮丁贪心分配给 $1$ 旁边的点。那么要么是把 $1$ 旁边的点都删完了，要么是剩下的 uoj 壮丁可以把 $n$ 旁边的点删完。总之 $1$ 和 $n$ 肯定有一个是周围的点被删完了。

异或序列 (Div. 1 Only)

来源：

• Petrozavodsk Winter 2021. Day 8: Belarusian SU Contest, Yandex Cup 2021. Problem C. Brave Seekers of Unicorns
• XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem C. Brave Seekers of Unicorns
• https://qoj.ac/contest/536/problem/1085

Tutorial by feecle6418.

算法一

从小到大加入数来 dp。暴力一点，既然要求连续三个的异或和不为 $0$，就记录序列的最后两个位置 $x,y$ 分别是什么，加入 $z$ 的时候要求 $x,y,z$ 异或和不为 $0$。

时间复杂度 $O(n^3)$，期望得分 $40$ 分。

算法二

注意到性质：如果连续三个位置 $a_i,a_{i+1},a_{i+2}$ 违反了题目的限制，那 $(a_{i-1},a_i,a_{i+1})$ 就不可能违反限制了。

设 $f(n)$ 表示以 $n$ 结尾有多少个合法的序列。使用容斥：$f(n)=1+\sum _{i < n}f(i)-C$，$C$ 是在 $n$ 处第一次违反限制的序列数。$C$ 怎么算？如果一个序列 $[\dots,x,y,n]$ 在 $(x,y,n)$ 第一次违反限制，枚举 $y$，如果 $x=(y\operatorname{xor}n) < y$，$C$ 就应该加上 $f(x)$。

时间复杂度 $O(n^2)$，期望得分 $60$ 分。

算法三

对于 $\sum_{i < n}f(i)$ 这部分，可以用前缀和优化。

对于 $C=\sum_{y < n}[(y\operatorname{xor}n) < y]f(y\operatorname{xor}n)$，考虑满足条件的 $y$ 有何性质：实际上只要 $y$ 的二进制最高位和 $n$ 相同就有 $(y\operatorname{xor}n) < y$ 了。此时，枚举最高在哪一位 $y$ 和 $n$ 不同，则比这一位低的位可以任取，这样 $(y\operatorname{xor}n)$ 就属于一段特定的区间。因此我们把上述求和拆成了 $O(\log n)$ 段区间求和，同样可以前缀和。

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

数圈圈 (Div. 1 Only)

来源：

• Petrozavodsk Winter 2021. Day 8: Belarusian SU Contest, Yandex Cup 2021. Problem F. Border Similarity Undertaking
• XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem F. Border Similarity Undertaking
• https://qoj.ac/contest/536/problem/1088

Tutorial by feecle6418.

算法一

枚举每种情况，再暴力判断条件是否满足。

可通过子任务 $1$，期望得分 $5$。

算法二

预处理从 $x$ 开始往右、往下最长的一段连续相同字符，再暴力枚举，这时可以 $O(1)$ 判断了。

时间复杂度 $O(n^2m^2)$，可通过子任务 $1,2$，期望得分 $15$。

算法三

子任务 $3$ 中，只需要求有多少个矩形，这很容易 $O(1)$ 计算。

子任务 $4$ 中，注意圈的大小肯定不大，因此小范围内枚举即可。结合前述期望得分 $40$。

算法四

考虑对矩阵分治，每次选择长的一边割开，然后计算经过中线（中线长度等于短的一边长度）的“圈”数量。不妨假设是竖着切的。

在下图中，我们对每一对 $(u,v)$ 求出左边的 匚 和右边对称的形状数量，最终乘起来即可。因为两边是对称的，下面就只描述怎么求 匚 数量了。

设 $L_u$ 表示 $u$ 往左，相同字符至多能延伸到第几列；$D_{x,y}$ 表示 $(x,y)$ 往下，相同字符至多能延伸到第几行。则我们要求的是 $$ \sum_{i=\max(L_u,L_v)}^{mid} [D_{i,u}\ge v] $$ 若 $L_u\ge L_v$，就是求： $$ \sum_{i=L_u}^{mid} [D_{i,u}\ge v] $$ 因为 $L_u$ 是固定的，所以这里可以用一个桶存下所有的 $D_{i,u}$，做个后缀和就可以 $O(1)$ 求出了。

否则，我们发现 $[D_{i,u}\ge v]$ 等价于 $[U_{i,v}\le u]$（$U$ 表示向上延伸最远能到第几行），所以做法是一样的。

时间复杂度 $O(nm\log nm)$，因为递归有 $\log nm$ 层，设短边长 $x$ 长边长 $y$，每层用 $x^2+xy\le 2xy$ 也即 $O(xy)$ 的时间处理了询问，加起来每层是 $O(nm)$。可以通过本题得到 $100$ 分。

当然，如果固定 $u$ 将 $\{D_{i,u}\}$ 看成一个序列，上面就是问序列的某个后缀里有几个数 $\ge x$，用树状数组容易优化到 $O(\log n)$ 单次询问。时间复杂度 $O(nm(\log nm)^2)$。也可以通过本题得到 $100$ 分。

• 搬题人：
  • 就这：Y25t
  • 保序回归问题：Y25t
  • 恰钱：skip2004
  • 排序：Wu_Ren
  • 图同构：hehezhou
  • 找零：p_b_p_b
• 组题人：p_b_p_b
• 题解：p_b_p_b, Wu_Ren, Y25t, nantf

就这 (Div. 2 Only)

来源：

• 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem A. Constructiveforces
• Кубок Трёх Четвертьфиналов 2021. Problem A. Constructiveforces

Tutorial by Y25t

其实只用保证每个长为 $m$ 的子串中恰好有 $k$ 个 1 就合法了，一种简单的构造是：

for(int i=0;i<n;i++) std::cout<<(i%m<k);

保序回归问题 (Div. 2 Only)

来源：

• 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem E. Positive Thinking
• Кубок Трёх Четвертьфиналов 2021. Problem E. Positive Thinking

Tutorial by Y25t

当 $\prod y_i> 0$ 时，取 $x_i=y_i$，答案为 $0$。

当 $\prod y_i= 0$ 时，设 $\{y_i\}$ 中 $0$ 的个数为 $c$，那么至少要 $c$ 的代价才能使乘积非 $0$。而先把 $c-1$ 个 $0$ 变成 $1$，然后剩下那个 $0$ 根据情况变为 $1$ 或 $-1$ 即可取到这个下界。

当 $\prod y_i< 0$ 时，考虑 $\{y_i\}$ 中绝对值最小的位置，不妨设为 $j$。当 $y_j> 0$ 时将其变为 $-1$，否则将其变为 $1$，这样能使 $\prod y_i$ 反号，花费代价为 $|y_j|+1$，容易证明这是下界。

这些情况均可线性判断。

恰钱：(Div. 1 + Div. 2)

来源：

• The 2022 ICPC Asia Regionals Online Contest (I)

Tutorial by p_b_p_b

如果你会数位 dp 那么可以直接往里套，显然是能做的。

否则，你也可以毛估估一下：

• 当 $\text{ctz}(x)\le 5$ 时 $\text{ppc}(x)$ 也很小，这样只会有 $O((\log r)^4)$ 个合法的 $x$ 。
• 否则这样的 $x$ 只有 $r/2^5$ 个，也不会太多，把合法的留下就更少了。

所以可以写个爆搜得到所有合法的 $x$ ，然后每次询问时二分。爆搜只需要 dfs+剪枝 即可。

最后，你也可以每次询问时枚举 $\text{ctz}(x)$ ，然后进行一些神秘贪心或调整，也可以通过此题。

排序：(Div. 1 + Div. 2)

来源：

• Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest. Problem C. StalinSort Algorithm

链接：https://qoj.ac/problem/1456

tutorial by Wu_Ren

考虑 dp，设 $f_i$ 为当前子序列结尾为 $a_i$ 并且保证最终子序列包含 $a_i$ 的情况下，当前子序列长度的最大值。

那么考虑 $f_i+1$ 贡献到 $f_j$ 的条件，设 $nx_i$ 为 $\min\{j\mid j>i\land a_j>a_i\}$，那么就是 $j\in[nx_i,nx_{nx_i})\land a_j>a_i$。

为了干掉 $a_j>a_i$ 这个条件，我们可以按 $a_i$ 从小到大枚举 $i$ 进行转移，这样就可以忽略这个条件。具体的，按 $a_i$ 从小到大枚举 $i$，用 $f_i$ 更新答案，然后用 $f_i+1$ 更新在 $[nx_i,nx_{nx_i})$ 中的 $f_j$。

注意，假如 $a_0=0$，那么 $f_i$ 的初值是 $[i\in[nx_0,nx_{nx_0})]$。

用线段树辅助转移，复杂度 $O(n\log n)$。

图同构：(Div. 1 Only)

来源：

• 2021“MINIEYE杯”中国大学生算法设计超级联赛（6）. Problem 1007. Power Station of Art
• Petrozavodsk Summer 2021. Day 6. Xi'an JTU Contest 1, Grand Prix of Xi'an. Problem G. Power Station of Art
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Xi'an. Problem G. Power Station of Art

链接：https://qoj.ac/problem/1869

Tutorial by nantf

对相邻两个点 $u,v$ 操作时，相当于将两点同时反色，然后交换颜色。于是可以看成每个点的颜色跟着点权形成的二元组在移动，从起点到终点如果经过了偶数条边（经过多次算多次）则最终颜色不变，否则最终颜色需要反色。

每个连通块独立，以下分别考虑每个连通块，有两种情况。

1. 该连通块为二分图

则无论如何移动，只要确定了每个二元组的起点和终点，则颜色是否被反色只与起点与终点是否在二分图的同一部有关。

分别考虑每种点权，则要求 $A$ 图和 $B$ 图的 左部黑点+右部红点 数量相等、右部黑点+左部红点 数量相等。这是一个必要条件。构造说明这也是充分条件。

任取这个连通块的一棵生成树，任取一个叶子，不妨设其在 $B$ 图中为左部黑点或右部红点，则任取 $A$ 图中一个点权相同的左部黑点或右部红点（由和相等一定存在），将其一路交换过来，以后的过程就可以在两张图中都忽略这个叶子。最后所有点都可以归位。

2. 该连通块不为二分图

也即该连通块一定存在奇环。

此时在确定每个二元组的起点和终点后，颜色是否被反色还不好确定。

再注意到，所有二元组经过的边数之和为偶数。则要求两图黑点奇偶性相同，红点奇偶性相同，且对于每种点权，两图的总点数相等。这是一个必要条件。构造说明这也是充分条件。

首先若整个连通块就是一个奇环，可以用下述的方法使得点权不变的前提下，相邻两个点 $x,y$ 的颜色反转。

• 将 $x$ 上的二元组沿反方向交换一圈到 $y$ 点，然后将原本 $y$ 上的二元组沿反方向交换一圈到 $x$ 点。

那么先任意交换至点权对应，由黑点红点奇偶性不变，容易用该操作使得颜色也对应。

然后对于任意一个连通块，固定一个奇环，任取这个连通块的一棵生成树（要求奇环上至多一条边不属于该生成树），任取一个不在奇环上的叶子。任取 $A$ 图中一个点权相同的点一路交换过来，若仅沿树边交换会导致颜色不对，则交换到该叶子后再一路交换到奇环，绕奇环交换一圈，再原路返回，颜色就是正确的。最后只会剩下这个奇环的点没有归位，用上一种情况的做法即可。

直接按上述过程判断即可，时间复杂度 $O(n+m)$。

找零：(Div. 1 Only)

来源：

• 京都大学プログラミングProgrammingコンテストContest 2021. Problem F. One Yen Coin
• Petrozavodsk Winter 2022. Day 1. Kyoto U Contest 2. Problem F. Flatland Currency.
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Kyoto. Flatland Currency.

链接：https://qoj.ac/problem/2544

Tutorial by p_b_p_b

可以发现，虽然纸币有不同面额，但我们其实只关心面额为 $1$ 的纸币数。剩余的钱具体是用哪些纸币表示出来，对后续操作没有影响。

因此也不难发现每次只会购买一个物品，不会出现打包购买的情况。

所以一个价格为 $a_i$ 的物品的价值就是 $5\lceil a_i/5\rceil-a_i$ ，我们需要做一个背包问题。但是价格实在是太高了。

注意到价值很小，所以可以把价值放进状态里。设 $dp_{i,j}$ 表示考虑了前 $i$ 个物品，获得的价值为 $j$ ，所需的最小代价，这样就可以把复杂度优化到 $O(n^2)$ 。

然后有多种继续优化的方法：

• 注意到如果价值相同，那么一定是按价格从小到大选。所以可以设 $dp_{i,j}$ 表示考虑了所有价值 $\le i$ 的物品，获得的价值为 $j$ ，所需的最小代价，然后利用决策单调性在 $O(n\log n)$ 的时间内从 $dp_i$ 转移到 $dp_{i+1}$ 。
• 注意到价值的 $\text{lcm}$ 是 $12$ ，所以可以把每种价值的物品分别先打包成价值为 $12$ 的包裹，然后按照价格从小到大选包裹。这样的一个问题是最优解的价值并不一定是 $12$ 的倍数，但是可以枚举价值为 $1,2,3,4$ 的物品选的个数模 $12,6,4,3$ 的值，然后先把这些物品选掉之后再贪心即可。
• 放弃分析，直接先按照性价比排序贪心选，然后在每种价值物品的边界附近进行小背包。大概和前一种是等价的。

提示：根据验题人的反馈，我们删去了一道题目并调整了分数分布。

Public Easy Round #3 将在 2022 年 9 月 25 日 08:00 举行！比赛将进行 5 小时，共 7 道题，OI 赛制。

在四个月后，又一场 PER 与大家见面了。与此前不同的是，我们调整了 Easy Round 的难度，增加了若干道签到题。题目的难度分布在 NOIP T1 至省选 T2，欢迎所有水平的选手来参加！

本次比赛中可能会包含若干道提交答案题、交互题与通信题。如果你不熟悉这些类型的题目，你可以使用 PTR #1、PER #1、PER #2 与 PR #6 中的题目来作为练习。

特别地，本场比赛每道题目的权重不同。题目的分数分布为 $50 + 50 + 75 + 75 + 75 + 125 + 200$，其中每道题目都可能包含一个或多个子任务，每个子任务中可能会有不同的评分方式。

本场比赛的组题人为 Qingyu，搬题人为 Qingyu, flower, feecle6418, Wu_Ren，验题人待定。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

• 搬题人：
  • 一维围棋：Wu_Ren
  • 斜二等轴测图：Wu_Ren
  • 盒子里的糖果：hehezhou
  • 冲塔：p_b_p_b
  • 波特分组：feecle6418
  • 别急：Y25t
• 组题人：p_b_p_b
• 验题人：syzf2222, Zeardoe, Dualqwq, yllcm
• 题解：hehezhou, Wu_Ren, p_b_p_b, Y25t

一维围棋 (Div. 2 Only)

来源：

• ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem A, AiGo
• Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem A, AiGo

QOJ 链接：https://qoj.ac/problem/1335

tutorial by Wu_Ren

枚举哪个位置去放棋子，首先如果上面已经有棋子就不能放，然后向左向右如果都是连续一段白再接一段黑，那么也不能放，否则一定能放。放了之后向左向右分别扫一遍即可知道占领了多少黑棋。

复杂度 $O(n)$ 或 $O(n^2)$。

斜二等轴测图 (Div. 1 + Div. 2)

来源：

• 2018 Multi-University Training Contest 3. Problem B, Visual Cube
• Petrozavodsk Summer 2020. Day 3: Songyang Chen Contest 3. Problem B, Visual Cube

QOJ 链接：https://qoj.ac/problem/1266

tutorial by Wu_Ren

按照题意模拟即可，复杂度 $O(T(a+b)(b+c))$。

盒子里的糖果 (Div. 2 Only)

来源：

• Petrozavodsk Summer 2021. Day 4: Shanghai ICPC Camp 2021 Onsite Day 1 by PKU. Problem F, Interval Shuffle

QOJ 链接：https://qoj.ac/problem/1848

tutorial by hehezhou

算法一

令 $dp_{i,j}$ 表示 $i$ 次操作后，$a_j$ 的最大值。

那么有： $$\begin{cases}dp_{i,j}=dp_{i-1,j}&j\in[1,l_i)\bigcup(r_i,n]\\ dp_{i,j}=\max(dp_{i-1,j}+1,\max_{k\in [l_i,r_i]}dp_{i-1,k})&j\in[l_i,r_i]\end{cases}$$

即只需考虑 $i-1$ 步时的最大值即可推出 $i$ 步后的最大值。构造某位的最大值只需按照 dp 转移式逆推即可。

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

算法二

考虑用线段树优化上述过程：

1. 计算 $\max_{k\in [l_i,r_i]}dp_{k}$ 即为一次查询区间最大值。
2. 更新 $dp$ 值可以表示为一次区间加和一次区间取 $\max$。

这是一个经典线段树问题，可以在 $O(n\log n)$ 的时间复杂度内解决。

冲塔 (Div. 1 + Div. 2)

来源：

• National Olympiad in Informatics 2022. Problem 3, Towers

QOJ 链接：https://qoj.ac/problem/3873

tutorial by p_b_p_b

先不管“每列只能冲至多两个塔”的限制，直接先把每行最左和最右的塔都冲掉。

这时候当然可能会出现某一列超过两个塔了。但是往好处想：如果超过两个塔，是不是说明中间那个塔就不需要冲了呢？

因此可以每次找到最靠右的一列，使得这一列有超过两个塔，然后把中间的那些塔全都往左移动一位。

不难发现每次这样操作之后仍然满足每个塔都被覆盖，并且 $O(n)$ 次操作之后就不会存在冲了超过两个塔的列了。

用 set 维护，复杂度 $O(n\log n)$ 。

波特分组 (Div. 1 Only)

来源：

• Petrozavodsk Winter 2020. Day 7: Gennady Korotkevich Contest 5. Problem F, Flip
• XX Open Cup named after E.V. Pankratiev, Grand Prix of Gomel. Problem F, Flip

QOJ 链接：https://qoj.ac/problem/1427

tutorial by feecle6418

设 $S=\sum k$。

算法一

直接枚举每枚硬币哪面朝上，时间复杂度 $O(q2^{2n})$，可以通过第一个子任务，期望得分 $9$。

算法二

考虑先枚举每一种情况，用子集和变换预处理每种输入哪些会有贡献，时间复杂度 $O(2^{2n}n+S)$，可以通过前两个子任务，期望得分 $25$。

此外，可能存在一些高复杂度算法，可以通过前三个子任务。

算法三

首先，给定一种分组状态，它出现的概率是多少？设最后一个分到 A 组的人编号为 $i_A$，最后一个分到 B 组的人编号为 $i_B$，则概率为 $2^{-\min(i_A,i_B)}$。

对于每组询问，不妨假设全分在 A 组，枚举 $\min(i_A,i_B)=p$ 的值，计算分组方案数：

• $p=b_k$，此时分组方案数为 $\binom{b_k-k}{n-k}$。
• $p$ 位置分在 B 组，不妨设 $b_i < p < b_{i+1}$，则分组方案数为 $\binom{p-i-1}{n-1}$。对于固定的 $i$，$p-i-1$ 构成区间，恰当预处理前缀和可以 $O(1)$ 求出。
• $p>b_k$ 且 $p$ 位置在 A 组，则分组方案数为 $\binom{p-k-1}{n-k-1}$。对于每种出现的 $k$，分别 $O(n)$ 预处理该式与概率的乘积的后缀和即可。

因为不同的 $k$ 只有 $\sqrt S$ 个，所以时间复杂度 $O(n\sqrt S+S)$，期望得分 $100$。注意边界。

本题也存在线性做法。

别急 (Div. 1 Only)

来源：

• XXII Open All-Siberian Programming Contest named after I.V. Pottosin Final tour, II day. Problem 11: Captivating process
• XXII Open Cup named after E.V. Pankratiev, Grand Prix of Siberia. Problem 11: Captivating process

QOJ 链接：https://qoj.ac/problem/4758

tutorial by Y25t

建两张有向图 $F,G$，对所有 $1\le i\le n$ 在 $F$ 中连有向边 $(i,f_i)$，在 $G$ 中连边 $(i,g_i)$。那么它们分别形成基环内向森林。

对于一个点 $u$ ，若它能沿着 $F$（或 $G$）中唯一出边走若干步能回到 $u$，则称它为 $F$（或 $G$）中的环点，否则称它为 $F$（或 $G$）中的树点。定义 $dep^F_u$ 为在 $F$ 中 $u$ 第一次走到环点所需步数。若 $u$ 在 $F$ 中是环点，则 $dep^F_u=0$，同时定义 $l^F_u$ 为 $u$ 所在环的长度，$d^F_u$ 为 $u$ 在其所在环上的编号（满足 $0\le d^F_u< l^F_u$ 且 $d^F_{f_u}\equiv d^F_{u}+1\pmod{l^F_u}$）。类似地定义 $dep^G,l^G,d^G$。

对于一块石板 $(x,y)$，不妨设 $dep^F_x\le dep^G_y$。考虑将时间分为 $[0,dep^F_x),[dep^F_x,dep^G_y),[dep^G_y,+\infty)$ 三段，分别判断是否会裂开。

$[0,dep^F_x)$

在这段时间里，$x$ 为在 $F$ 中的树点，$y$ 为在 $G$ 中的树点。

该石板会在这段时间中裂开，当且仅当存在点 $u$ 使得以下三个条件同时满足：

• $dep^F_x-dep^F_u=dep^G_y-dep^G_u$，即 $dep^F_u-dep^G_u=dep^F_x-dep^G_y$。
• 在 $F$ 中 $u$ 是树点，且为 $x$ 的祖先。
• 在 $G$ 中 $u$ 是树点，且为 $y$ 的祖先。

于是将询问离线后在 $G$ 的树部分进行 dfs。用 std::set 或动态开点线段树维护 $2n$ 个线段集合 $S_i(-n\le i\le n)$。在进入一个点 $u$ 时，在 $S_{dep^F_u-dep^G_u}$ 中插入线段 $[dfn^F_u,dfn^F_u+sz^F_u-1]$（其中 $dfn^F,sz^F$ 为在 $F$ 中的 dfs 序和子树大小），回溯时撤销。对于询问 $(x,y)$，在进入 $y$ 后判断 $S_{dep^F_x-dep^G_y}$ 中是否有线段覆盖了 $dfn^F_x$ 即可。

该算法加一些简单特判后可通过子任务 7。

$[dep^F_x,dep^G_y)$

在这段时间里，$x$ 为在 $F$ 中的环点，$y$ 为在 $G$ 中的树点。

该石板会在这段时间中裂开，当且仅当存在点 $u$ 使得以下三个条件同时满足：

• $d^F_u-d^F_x\equiv dep^G_y-dep^G_u\pmod{l^F_u}$ 即 $d^F_u+dep^G_u\equiv d^F_x+dep^G_y\pmod{l^F_u}$。
• 在 $F$ 中 $u$ 是环点，且与 $x$ 在同一环中。
• 在 $G$ 中 $u$ 是树点，且为 $y$ 的祖先。

于是可以用类似的 dfs 进行求解。

该算法加一些简单特判后可通过子任务 6。

$[dep^G_y,+\infty)$

在这段时间里，$x$ 为在 $F$ 中的环点，$y$ 为在 $G$ 中的环点。

该石板会在这段时间中裂开，当且仅当存在点 $u$ 使得以下三个条件同时满足：

• $d^F_u-d^F_x\equiv d^G_u-d^G_y\pmod{\gcd(l^F_u,l^G_u)}$
• 在 $F$ 中 $u$ 是环点，且与 $x$ 在同一环中。
• 在 $G$ 中 $u$ 是环点，且与 $y$ 在同一环中。

用 std::set 维护三元组即可简单判断。

该算法可直接通过子任务 5。

结合以上三个算法即可通过本题。

Public NOIP Round #1 将在 2022 年 9 月 10 日 14:00 举行！

这是 Public Judge 举办的第一场 NOIP 系列模拟赛，欢迎捧场！

比赛将分为普及组和提高组，普及组进行 3.5 小时，提高组进行 4 小时。普及和提高分别有 4 道题，OI 赛制，其中普及组和提高组有两题相同。 本次比赛的题目难度约为 CSP J/S，所有题目都有部分分。 本次模拟赛的组题人为 p_b_p_b ，搬题人为 Y25t, feecle6418, Qingyu, Wu_Ren, hehezhou, p_b_p_b ，验题人为 syzf2222, Zeardoe, Dualqwq, yllcm。 赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

A. Add One

考虑把 $+1$ 看成 $xor a$ 操作，可以发现 $a$ 只可能是 $2^k-1 (k \ge 1)$。因此考虑枚举 $a$ 判断是造出来 $???????01111$ 的形式，可以从低位到高位建线性基，每次从低位到高位贪心的xor，时间复杂度 $O(n \log w)$

B. Beautiful Sum

$$ \sum_{i=1}^n (\mu(i)\mu(i+k))^2 \\ = \sum_{i=1}^n \sum_{d^2 | i} \mu(d) \sum_{e^2 | i+k}\mu(e) \\ = \sum_{d = 1}^{\sqrt n}\mu(d)\sum_{e=1}^{\sqrt n} \sum_{i=1}^n [d^2 | i \land e^2 |i + k] $$

最后一部分等价于 $ye^2-xd^2=k, 1 \le xd^2 \le n$ 的解的数量。可以利用 exgcd 计算。 同时也可以找到所有 $xd^2, ye^2$，用双指针计算所有相差为 $k$ 的数量。 因此可以对于 $d^2,e^2>B$ 的数对采用做法2，时间复杂度为 $\sum_{i=B}^{\sqrt{n}} \frac{n}{i^2} = \frac{n}{B}$，其它采用第一个做时间复杂度为 $O(B\sqrt{n} \log n)$， 令 $B = \frac{n^{1/4}}{\log^{1/2}} n$，时间复杂度为 $O(n^{3/4}\log^{1/2} n)$。

C. Counting Sequence

令 $B = \sqrt{2n}$。 当 $a_1 \le B$ 时$\max a_i$ 是 $O(\sqrt{n})$ 的，因此可以$f_{i,j}$ 表示和为 $i$ 上一个数字为 $j$。 当 $a_1 > B$ 时不需要考虑 $a_i>0$ 的限制，因此可以 $g_{i,j}$ 表示 $i$ 个数字，$\sum_{k=1}^i a_k-i\times a_1 = j$，考虑枚举 $a_1,a_2$ 的关系转移。 时间复杂度是 $O(n\sqrt{n})$。

E. Exciting Travel

原问题等价于，用 $p_i,p_{i+1}$ 的路径上的点换答案$+1$。 考虑建立虚树，令 $f_u$ 表示 $u$ 的子树的答案。对于$l_i = lca(p_i, p_{i+1})$，在$lca$ 处枚举是否选择这条路径。考虑所有的转移类似于$\sum_{u \in path(p_i,p_{i+1}), v\not \in path(p_i,p_{i+1})} f_v + 1$。考虑令 $g_u = \sum_{v} f_v-f_u$，这个式子可以写成$g$ 的链和加上常数的形式，因此在$dp$的过程直接维护$g$的前缀和即可。

F. Flower's Land

考虑点分治，分治重心为 $rt$，计算必须包含 $rt,u$ 的大小为 $k$ 的连通块的最大权值。 令 $f_{i,j}$ 表示先序遍历为 $[i,n]$ 内部的点选了 $j$ 个并且满足不存在 $u,fa_u$ 的 dfn序在$[i,n]$ 并且 $u$ 选了，$fa_u$ 没选，枚举是否选 $u$ 以此决定是否跳过 $u$ 的子树即可。类似的令 $g_{i,j}$ 表示后序遍历 $[1,n]$ 的选 $j$ 的权值。$O(k)$ 合并两个背包的某个点即可。 点分治的当前区域大小少于$k$ 的时候剪枝，复杂度为 $O(nk\log {\frac{n}{k}})$

G. Games

令 $f_{u,i,0/1}$ 表示 $u$ 的子树，$a_u = i$，是否有子树内的点比$a_u$ 大，利用前缀和转移即可。 类似的，令 $g_{u,i,0/1}$ 表示 $u$ 的子树补的答案。通过换根 dp 转移即可。时间复杂度 $O(nm+q)$。

I. Inverse Line Graph

考虑问题转化为，给新图每个点赋两个权值，代表的含义是原图的端点，因此需要保证任意一个颜色的导出子图是完全图，并且每条边在恰好一个完全图里，称边被颜色覆盖为边在这个颜色的导出子图里。 我们随便选一个点 $u$ 考虑把 $u$ 的出边划分成两个集合，分别代表两个颜色。不妨设 $u$ 的出度为 $S$，两种颜色的集合分别为 $S_1, S_2$。 假设我们得到了正确的划分，对于 $S$ 中的每个点，已经使用了一种颜色，对于剩下的没有被覆盖的边，必须成为一个新的完全图，因此可以递归处理。 设$x\in S_1, y_1,y_2 \in S_2$ 且 $(x,y_1),(x,y_2)$，那么 $x,y_1$ 和 $x,y_2$ 必须染一个颜色，但是 $y_1,y_2$ 的边已经被覆盖，因此无解。因此 $S_1,S_2$ 之间是一个匹配。 任选一个 $p \in S$，令 $S_1= \{p\}, S_2 = S - S_1$，并且检验一遍。 那么一定存在$p,q \in S_1, (p,q)$。假设我们有 $p,q \in S_1$ 的初始条件，那么对于$x \in S$，若与$p,q$ 均有连边，必须在$S_1$ 里，否则在$S_2$ 里。经过上述过程，假设 $p,q,t\in S$，那么 $p,q$ 在一个集合里与 $p,t$ 在一个集合里的初始条件是等价。对于 $t\in S_2,(p,t)$，通过上述方法同样检验一遍。如果仍然不满足意味着， $p,q$ 不在一个集合, $p,t$ 不在一个集合，因为 $t \in S_2$，所以 $t,p$ 没有边因此 $t,q$ 不在一个集合，于是无解。 因此可以转化为最多 $3$ 次检验，每次时间复杂度 $O(n+m)$，总时间复杂度$O(\sum n+\sum m)$。

J. Just Another Number Theory Problem

考虑计算 $s_i$ 表示有多少对相邻的差为 $i$，并且依次加入质数。 因为是任意两个数字互质，因此是均匀分布的，所以有转移$s_i:=(p - i + 1) s_i + 2 \sum_{j > i} s_j$，利用后缀优化即可。

N. No!

只用关心 $h$ 为前缀最大值的位置，因此对强按照从大到小排序后，令 $f_i$ 表示必须选第 $i$ 面强，不考虑第 $i$ 会倒的答案。那么有$f_i = \max_{j=1}^{i-1} \min(f_j, \frac{h_j-h_i}{a_j})$，后半部分可以看成一个平移的反比例函数和一个值域上限。因为对于两个 $j_1,j_2$ 对后续的贡献不考虑上限只有一个交点，因此考虑用类似于斜率优化的方式维护即可。如果使用基数排序和gcd技巧可以做到 $O(n + m + q)$。