比赛链接

solved by JJLeo

一共有$n$天，每天可能会有鱼或没鱼，可能会有蛤或没蛤，如果有鱼就可以抓鱼，如果有蛤就可以抓蛤做诱饵，如果之前有做好的诱饵就可以用诱饵抓鱼（不需要有鱼），每天至多进行一种操作，问最后最多能抓多少鱼。

有鱼肯定直接抓，其它情况倒着扫一遍记录后面有几个空的天用于诱饵抓鱼，如果天数够就做诱饵，否则就把诱饵用掉。

solved by 2sozx

给定一个字符串 $S,|S|\le2\times10^6$ 定义三种操作，将 $S$ 的前 $x$ 位移动到 $S$ 末尾；将 $S$ 的后 $x$ 位移动到 $S$ 开端；询问 $S$ 的第 $x$ 位是什么字符。

容易发现前两个操作不改变 $S$ 的相对顺序，因此每次操作记录操作之后 $S$ 的起点在哪即可。

solved by 2sozx

$t$ 组询问，每个询问按照顺时针或者逆时针给出 $20$ 个点，问这 $20$ 个点是左手还是右手（图为左手），左右手大小不变。

暴力找哪两个点是最下面的点即可，即两个点的距离位 $9$ ，之后找到大拇指外侧的点，通过叉积判断方向即可判断左右手。

solved by 2sozx

设二维平面全部整点均为白色点，现在可以选择 $n$ 个点使其变为黑色。如果有两个点相邻，即 $|x_1-x_2|+|y_1-y_2|=1$ 并且颜色不同，则不同颜色的对数加一，问是否有一种选点方式使得最后有 $m$ 个不同颜色的对数。$n\le 50,m\le 200$

先考虑 $m$ 在什么范围可以构造出来。显然 $m>4*n$ 不可能构造。我们考虑 $m$ 的下界，显然 $n$ 个数构成一个连通块的时候 $m$ 最小，考虑一种构造方案使得每次构造都最优，即优先向正方形构造。假定已经是一个正方形，下一个黑色的点必定连在一条边的外边，这样可以构造出一个 $L$ 形，下次放在 $L$ 形的中心最优。如果已经是一个矩形，则下一个黑点应该在短边的外面相连，重复这种操作即可。可以预处理出来 $m$ 的下界。考虑构造，在已知的最优情况下考虑移动点，可将仅与两个黑点相连的点移动到仅与一个黑点相邻的白点上，这样会使得 $m+2$ ,如果不存在与两个黑点相邻的点，则选择与一个黑点相邻的白点并将其移动到无穷远处即可，易知这样构造是可以满足条件的。

另一种构造方法：我们先考虑 $x$ 个点对角线相连的情况，这样会有 $4*x$ 个对数，我们很容易会发现再加上 $x^2-x$ 个点依旧可以很容易的做出总对数不变的情况，如果目标的 $m$ 并非是 $4$ 的倍数，我们可以在对角线的端点向外侧连上一个点，总对数为 $4*x+2$ 并且我们会多出 $x$ 个可以使总对数不变的点。这样反过来给定 $m$ 时也可以构造出答案。

solved by JJLeo

给定偶数个元素，选择两种完全不相交的使他们两两匹配的方案（不相交指两种方案不能有两个元素都在同一组），使得两次匹配中所有匹配的两元素差值之和最小。

考虑找到最小和次小的两种匹配方式，最小肯定是排序后然后从小到大两个两个组合即可。次小需要进行dp，考虑排序后的某个元素跨过偶数个元素与后面某个元素匹配，这样自己以及中间的元素就可以错开匹配，扫一遍维护最小值即可。

solved by 2sozx

给定两个数 $a,b(a,b\le2\cdot10^6)$，要找到 $c,d,e,f$ 使得满足 $d<b,f<b,c,e\le10^{12},\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$。如果找不到输出 $-1 -1 -1 -1$

先判断 $gcd(a,b)$ 是否为 $1$。如果不为 $1$ ，容易构造出来 $c=\frac{a}{gcd(a,b)}+1,d=\frac{b}{gcd(a,b)},e=1,f=\frac{b}{gcd(a,b)}$

若 $gcd(a,b)=1$ ,判断 $b$ 是否存在至少两个不同的质因数。如果存在则找到 $p\not =1,q\not =1$ 有$gcd(p,q)=1$，令 $d=p,f=q$，之后会得到一个裴蜀方程 $fc-de=a$ ，扩展欧几里得解一下正整数解即可。如果不存在，则一定不存在 $d<b,f<b$ 使得 $lcm(d,f)=b$,输出 $"-1 -1 -1 -1"$ 即可。

solved by JJLeo

给定一个$n$个点$m$条边的无向连通图，一开始$i$点的颜色就是$i$。每次操作选择一个颜色$c$，如果已经不存在这个颜色则无事发生；否则如果某个点的颜色为$c$，另一个颜色为$d$的点与该点相邻，则所有颜色为$d$的点全部变为颜色$c$。问全部操作完成后所有点的颜色。$(n,m \le 8 \times 10^5)$

显然每次操作后每种颜色组成的点是一个联通块。因此每种颜色的点在扩张一次后就不会再产生作用，可以将其称作某种颜色的内侧点，而每次新加入的点则称作外侧点，可以考虑开一个vector放每种颜色的外侧点。扩张某种颜色时遍历上述vector中的全部外侧点，合并所有相连的其它颜色对应的vector，并将扩张过的点弹出vector，除合并外每个点仅进出vector一次，合并时采用启发式合并，时间复杂度$O(\log n)$。

upsolved by Bazoka13

upsolved by

upsolved by

upsolved by JJLeo

solved by JJLeo

签到。

比手速。

0min：分配读题
2min：ZYF 秒L，和MJX 看B，CSK 冲F
14min：CSK WA F
21min：找到B性质 MJX AC B，ZYF 看 A， MJX看C
34min：MJX AC C,ZYF 看A
47min：ZYF WA1 后 AC A，大家一起看F
97min~113min：经过漫长的讨论终于 AC F，CSK ZYF 看E，MJX 看D
114min：CSK ZYF 秒 E，看G
152min：CSK ZYF 秒 G，ZYF MJX构造D，CSK 看 H
227min：ZYF构造心态崩了，MJX接盘
261min：MJX AC，讨论 K
till end：对K有初步想法，然而没时间写了。
after end：ZYF 对于 ? 以及数字构成的序列产生了厌恶

• CSK强制下机，很痛苦，CSK$H$题写了傻逼线段树，很痛苦
• MJX写代码常有小 bug ，下场尤为突出