ATC 小清新杂题题解

ABC225G X

假如已经确定了选择的点，考虑所有共一个角的点对。若选且只选了一个点，则共角一定是划线方案的一个端点，费用为 $\frac{c}{2}$。这很最小割，集合划分模型。额外维护第 $0,n+1$ 行和第 $0,m+1$ 列即可。

ABC137F Polynomial Construction

妙妙构造题。题意很像拉插，而拉格朗日插值和中国剩余定理的灵魂在于 $n$ 项的和式。对于每个确定的 $x$，当前点可以得到 $y$，其他确定点只能得到 $0$。仿造这个过程，我们有 $1-(x-a)^{p-1}$ 用于调整取值，二项式定理拆开即可。

ABC135F Strings of Eternity

假如 $s$ 已经被复制扩展使大小达到 $+\infty$，那么我们唯一可以调整的就是 $t$ 在模 $\lvert{s}\rvert$ 意义下的起始位置。若该位置可以放置，则后继位置也是固定的，这是一个 $n$ 点最多 $n$ 条边的图。求最长路或输出环即可。

ABC225F String Cards

贪心是错误的，但是若 $s+t<t+s$，则在答案中 $s$ 一定在 $t$ 前。可以基于这个性质直接 $O(n^4)$ DP。

ABC128F Frog Jump

若 $A=B+x$，则经过的点是形如以下这样的两个等差数列的并。$A,A+x,A+2x,\cdots,A+kx$，$0,x,2x,\cdots,kx$。对于每个 $x$，枚举 $k$ 即可，当等差数列出现交或者 $A,B$ 取值不合法时退出。