【题解】Atcoder 题的一些记录 -boshi

这里的题目前来说都是 Atcoder 中比较简单的题。但我还是没几道是自己想出来的。

$x+y+z$个人，每个人有 $a,b,c$三个参数，将这些人分为 $X,Y,Z$三类，求 $\sum_{i\in X}a_i+\sum_{i\in Y}b_i+\sum_{i\in Z}c_i$的最大值
NOI2019 有类似的一道题。假设只有 $a,b$两个参数，我们可以先将所有人放入集合 $Y$，然后选择 $a$个人放入集合 $X$。选择的那 $a$个人一定是 $a-b$最小的几个。
同理，如果分为了三类，假设我们已经确定了哪些人放入 $Z$，我们用上面的方法就可以了。如何利用上面的方法呢？我们还是将所有人按照 $a-b$排序，那么剩下的人中放入 $X$的一定都在放入 $Y$的人的左边。根据这一性质，我们可以枚举这两种人的分界线，然后进行贪心。
我只想到了第一步，第二步没有想到。我曾试验过这样一种做法：先将任意的 $x+y$个人用方法 1 分配进 $X,Y$两个集合，然后不停添加新的人，进行替换。这样的做法存在的问题是：无法保证权值单调，因此不能用单调队列维护贪心。

给定一排无穷多的硬币，只有有限个位置反面朝上。每次选择一段长度为奇质数的区间，将它们区间翻转。求最少多少次使得所有硬币正面朝上。
先将序列转化为前缀异或序列，则每次我们可以同时翻转两个距离为奇质数的位。
根据素数分布，两个距离为偶数的位我们可以 $2$步完成同时翻转，距离为奇数但是不是质数的位，我们可以 $3$步完成翻转。
因此我们需要将所有的位两两匹配（显然有偶数个位），且匹配权值为：
$$
\begin{cases}
1 & (|x-y|\in \mathcal P\text{\ } {2})\\
2 & (|x-y|\in {2n })\\
3 & (|x-y|\in {2n+1}\text{\ }P)
\end{cases}
$$
实际上，我们只需要最大化权值为 $1$的匹配即可。设有 $E$个位的下标为偶数，$O$个位的下标为奇数，$x$为权值为 $1$的匹配数，则 $ans=x+\lfloor (O-x)/2\rfloor\times 2 + \lfloor (E-x)/2\rfloor\times 2 + ((O-x)\bmod 2)\times 3$，这个函数有关 $x$是单调的。最大化 $x$直接使用二分图最大匹配即可。
我只想到了第三点，没有意识到第四点。

给定 $y$，$x$一开始等于 $0$，给定一个数列 $d_i$，依次对于 $i=1\cdots n$，如果 $|x\pm d_i-y|<|x-y|$，则将 $x$更新。对于每一个 $i$，求能否将 $d_i$更改后使得最终 $x\not=y$
我们可以从后往前动态维护，对于剩余的序列，如果起始位置为每个地方，能否到达终点。
但是维护这个东西的复杂度较高，我们可以想一想能否少维护一点东西。
实际上，我们只需要维护最小的距离 $f[i]$使得如果 $x,y$的距离为 $f[i]$，时，$x$经过序列 $d[i\cdots n]$没法到达 $y$
我花了很久 (分两次思考，两次间隔 9 个月，每次大概都花了半个小时以上) 才想到了第 3 点。

给定 $n\times n$的矩阵上的 $2n$个点，矩阵的左侧有每行有一辆向右开的车，下方每列有一辆向上开的车。车出发后会捡起遇到的第一个点。有多少种让车出发的顺序可以使所有的点被捡到？
假如一个点只能被一个车捡，或者一辆车的路径上只有一个点，那么这两者一定需要匹配。将可以匹配的车和点删除后，运用鸽巢原理可以知道，每辆车的路径上都有两个点，每个点都可以被两个车捡，它们的关系大致形成几个环。
这就启发我们，我们刚才删掉的是基环树的树边，剩下的是环。
实际上，如果 $(x,y)$处有一个点，那么在图 $G$上的点 $x,y$之间连一条边即可。一种合法的车和点的配对方式对应着一种合法的将每条边分配到它的端点的方案。当然，并不是每一种安排方式都可以任意安排车启动 d 的顺序。我们需要保证在启动车 $i$之前，所有挡住它的点已经都被捡起了。这种关系对应的是图 $H$上的一种拓扑序，且图 $H$是个森林。
这道题难度很大，我花了很久只能想到第一步。实际上类似的模型我曾经见过，只能没有突发奇想将这个问题和基环树模型联系起来。