测试点 $1$

大概是用来让你感受这个奇怪语言的劲的。找到代码中奇怪的数就能拿到 $10$ 分。

一种可以拿到 $10$ 分的输入：

23333333

测试点 $2$

先运行一次，发现需要输入 $10$ 个整数。用你喜欢的方式在代码中找到 geti 片段。发现每次读入进来之后，如果 $ 1 和 # 0 相等就输出 ok 否则输出 ko。于是我们不需要搞清楚代码的原理，只要修改一下代码，每次打印 # 0 然后复制粘贴即可。

注意代码中存在跳转行号，所以尽量不要一次插入多行输出行，不然可能会导致行号倒闭然后代码乱飞。

一种可以拿到 $10$ 分的输入：

7
47
1965
1915
-2551
-1646938625
-322
-167542220
4346926
1531256182

测试点 $3$

用你喜欢的方式在代码中找到 putc @ 111 片段，可以发现代码中总共有 $10$ 处输出 ok，按照 $1-3-3-3$ 的方式分布。运行一下可以发现，它让你输入 $20$ 个数，只要输入了就可以得到第一个 ok。事实上，如果你无脑打了 $20$ 个相同的整数，可以发现输出是 ok fail fail ok ok ok，也就是我们拿到了第四组限制的三分。

观察代码可以发现，后三组限制都是，判断某个量是否和预设量相等，如果是就输出三个 ok。通过打印中间变量，进行一些最基础的尝试可以发现，三个限制分别为：

• $20$ 个数至少一个非 $0$。
• $20$ 个数的和为 $0$。
• $20$ 个数全部相等。

回想题面中描述的关于自然溢出的说明，可以想到，只需要输出 $20$ 个 $2^{30}$ 即可。

一种可以拿到 $10$ 分的输入：

1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824

测试点 $4$

尝试几次，根据输出的提示可以发现，读入的是一个字符串可以获得 $3$ 分，字符串长度恰好为 $18$ 可以再获得 $2$ 分。

依然是用你喜欢的方法找到 putc @ 111，发现在代码的末尾有一个可以输出 $5$ 个 ok 的地方。它的判断条件自然在它之前紧跟着它，可以找到第 $300$ 行开始的 $9$ 行一周期循环了 $18$ 次的相似代码块，在其中的判断语句中可以找到一些接近 $100$ 的数，大胆猜测它对应 ASCII 码。查阅题面的表格构造对应的输入即可。

一种可以拿到 $10$ 分的输入：

primaryschoolpupil

测试点 $5$

代码中出现了功能类似于对 $998244353$ 取模的片段。

测试一下可以发现它需要输入 $10$ 个字符串。在输出 ok 的语句之前可以找到十个判断，发现是判断某运算结果和大整数是否相等。猜测是字符串哈希，打印运算结果，尝试几次后可以发现 a 到 z 对应 $0$ 到 $25$，底为 $26$。

于是将判断中的 $10$ 个大整数按照 $26$ 进制分解即可。

一种可以拿到 $10$ 分的输入：

z
x
l
r
p
vfk
lssb
driozw
bqqcgzg
sanuwq

测试点 $6$

代码和测试点 $5$ 几乎完全一致。进行尝试后可以发现在这份代码中底为 $31$。

直接进行 $31$ 进制分解可能会存在某一位 $\geq 26$ 的情况。于是暴力枚举和大整数模 $998244353$ 同余的数直到不存在这种情形即可。

一种可以拿到 $10$ 分的输入：

p
n
nxybfe
bchdeeu
bdaeyow
eimvdvj
cqtmtzr
dcshgqm
djgxcsu
hilgqu

测试点 $7$

尝试一下可以发现要输入 $10$ 个整数。代码的判断部分和前面两个测试点相似，打印中间变量后可以发现是在模 $998244353$ 意义下求出输入的逆元并进行比较。逆元运算是可逆的，求出参与比较的 $10$ 个整数的逆元即可。

一种可以拿到 $10$ 分的输入：

998244353
1
224032231
204247430
800006205
536388420
830137805
173645564
591950221
212467234

测试点 $8$

与第 $7$ 个测试点相似，同样是存在某个函数 $f(x)$ 将输入变换后与 $10$ 个整数比较。打印中间变量可以发现 $f(0)=0$，$f(1)=1$，但 $f(2)$ 很大并且看上去没有规律。

尝试打印 $f(-1)$ 发现会 Runtime Error，于是尝试 $f(998244351)$，$f(998244352)$，$f(998244353)$ 和 $f(998244354)$，发现有周期 $998244353$，并且是奇函数。猜测是指数函数，写暴力验证可以得到 $f(x)=x^{77977}$。

由于 $\gcd(77977,\varphi(998244353))=1$，所以可以直接求出 $77977$ 次方根。或者可以写一个暴力来枚举，跑五分钟不到可以跑出来。

一种可以拿到 $10$ 分的输入：

0
1
43409364
171593339
879723643
750576725
275034811
464166077
503262602
826391194

测试点 $9$

还不会。

测试点 $10$

还不会。

A

杜老师做的，听说是烂题。

B

签到题，先咕了。

C

做法一

倒过来模拟染色过程，考察联通块数的变化量。可以发现，倒过来模拟这个过程时，右边界有相同的颜色，下边界也有相同的颜色，所以染色会增加连通块当且仅当新的颜色与右边界和下边界都不同。

容易想到用线段树维护 DDP，每个节点要记录 $2^2$ 个值，表示不翻转/翻转行，不翻转/翻转列时的 DDP 状态。维护是简单的。

时间复杂度 $O(n\log n)$，有 $36$ 的常数，能跑过去。

做法二

先咕着。

D

不是我做的，咕了。

E

存在一个暴力的费用流做最小权完美匹配的做法，用 Cost Scaling 和匈牙利可以做到 $O(n^3\log V)$，常数比较大，应该是过不去的。

分析菱形覆盖的形态，发现对于上半部分，第 $i$ 行与第 $i+1$ 行间的竖直菱形数量恰好为 $i$，且相邻两层间的竖直菱形插空分布。于是可以把竖直菱形按照斜向分组，建出一个新的费用流，每一组对应 $1$ 的流量。此时只需限制点的流量和边的流量 $\leq 1$ 就可以保证竖直菱形插空分布。分类讨论一下边权的值暴力跑费用流。

注意到这个新图流量只有 $O(n)$ 大小，于是跑暴力即可，时间复杂度 $O(n^3\log n)$，可以通过。

F

签到题，求出每一层的 SG 函数，异或起来就做完了。

G

签到题，二分答案之后排序来 check 即可。

H

还没完全会，等过了再补。

I

杜老师做的签到题。

J

容易发现 $(1,0),(0,1),(-1,-1)$ 可以构造所有点，故答案 $\leq 3$。先特判答案为 $1$ 的情况。

要让答案 $\leq 2$，至少需要所有点在同一个半平面内。此时需要特判如果存在两个点方向恰好相反，如果还有不在直线上的点就答案为 $3$，否则答案为 $2$。

然后对于所有点在同一个半平面内的情形构造。对于所有点都 $x\geq 0$ 的情形，可以构造 $(0,1)$ 和 $(1,-10^{18})$ 作为答案。类比到所有情形，只需要半平面对应的直线的一个方向选择一个向量，然后找到半平面内尽量接近直线的点，往另一个方向拉到无穷远处即可。

尽量接近直线的点可以 exgcd 求出。

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

K

可以建出一个差分约束模型，于是可以得到如果有解，那么存在一种方案每个点的值要么是 $0$ 要么是 $K$。

对于两个有包含关系的区间，可以确定大区间减去小区间的部分全是 $0$，并删除大区间。得到一个位置是 $0$ 之后需要把剩余的区间缩起来然后继续考虑包含关系，同时判掉区间被删空的情形。

对于不存在包含关心的情形，排序之后贪心即可，一定有解。

时间复杂度 $O(n\log n)$。需要注意实现的细节。

L

树上背包模板。

M

将代价拆到每条边上，变成 这条边交换的次数 $+$ 这条边两侧均出现了的颜色种类数。如果不进行交换，一条边的代价 $\leq 2$。对于初始存在一条边代价为 $0$ 的情形，显然取到理论最小值 $n-2$，特判即可。

然后可以发现，要让一条初始为 $2$ 代价的边变成 $1$ 代价，必须要用它进行一次交换，并且最终它恰好隔开黑色和白色。于是这样的边最多一条，只需要判这种边存不存在。

容易发现存在的充要条件是这条边：

1. 将树分成了两个区域，大小分别是黑色点个数和白色点个数。
2. 黑色区域有恰好一个白点。
3. 白色区域有恰好一个黑点。
4. 这个黑点与这个白点都不是叶子。

判断这四个条件即可，时间复杂度 $O(n)$。

时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是把小 S 和小 Y 变成 S 接 Y，仅此而已。

先进行一些分析。假设需要让 $(a,b,c)$ 分别是冠亚季军，那么：

1. $a$ 会尽量多过题且不会罚时；
2. $c$ 只会过一个题，且是最后一次提交才通过；
3. 除了这三个人之外的所有人都不过题。

更进一步的分析可以得到，$b$ 可行的过题情况有两类：

1. 在一次提交通过了唯一一个题，之前可能有罚时；
2. 过了两个题，最后两发提交才通过。

预处理出每个人作为冠军和季军的罚时，称为 $l_i,r_i$。只需要对于所有人作为亚军时的所有可行罚时情况，统计对应的 (冠军, 季军) 对的个数即可。

注意到，亚军过一个题且罚时大于 $L$ 的所有可行罚时中只需要保留最小的那个即可。所以可以根号分治统计所有人作为亚军的可行罚时情况。时间复杂度是 $O(n\sqrt L)$ 的，具体地，可以 $O(c^2)$ 或 $O(c+L)$ 来统计可行罚时情况。

然后计算出合法的数量。可能存在统计的时候多算冠军和季军是同一个人的情况，此时需要减掉。

查询需要减掉的情况数，本质是进行 $O(n \sqrt L)$ 次如下询问：对于 $[l,r]$，查询有多少 $i$ 满足 $[l_i,r_i]\subseteq [l,r]$。这是一个二维数点问题，可以离线下来做可持久化分块。更简单的做法是，容易发现，这 $O(n\sqrt L)$ 次询问中，只有 $O(n)$ 次询问的区间 $[l,r]$ 长度大于 $20$，所以可以提前预处理较短的区间的答案，对于较长的区间用主席树回答。

总时间复杂度是 $O(n\sqrt L + n\times 20^2 + n\log n)$。代码不是很难写，但是细节比较多。实现的时候不需要精细实现，复杂度多一点 $\log$ 或者 $20$ 也没卡。

关于 std：我偷看了一眼，看上去就没有根号分治，应该是 polylog 的。大概可以，每个人作为亚军时，每个提交对应了罚时情况中的一个公差为 $20$ 的等差数列，维护出区间之后大概处理一下，可以做到 $O(n\log n)$ 或者 $O(20\times n\log n)$。

IMO2023SL C1

将格子按照横纵坐标加和模 $3$ 分成等价类。每个等价类个数奇偶性需要相同，故可知 $3\mid nm$。

同时所有满足 $3\mid nm$ 的 $(n,m)$ 都合法。由 $3\times 2$ 和 $3\times 3$ 的构造显然得到，两个构造分别为：

00    11    11
00 -> 01 -> 11
00    00    11

和

000    011    011    011    101    111
000 -> 001 -> 101 -> 110 -> 100 -> 111
000    000    110    111    111    111