ACL001

· · 个人记录

https://atcoder.jp/contests/acl1/tasks

目前仅有 A, B, C, D。

A - Reachable Towns

考虑暴力就是枚举点对连边。

然后发现其实可以用单调栈优化到 O(n) 连边。就做完了。

其实这题有个很好的性质，但我没找。

B - Sum is Multiple

这里是题解做法。

考虑原命题等价于 2N\ |\ k(k+1)。则必有 x\ |\ 2N 满足 x\ |\ k 且 \dfrac{2N}{x} |\ k+1。这玩意是可以枚举因数然后 exCRT 做的。

当然你指数枚举质因数复杂度也很合理。

C - Moving Pieces

dp 难以记录状态，又找不到好的贪心做法，那么这个题 n, m \leqslant 50 就已经把流胡你脸上来了。

我们考虑非常关键的一点就是一个点往右或者往下走一格可以使答案增加 1。这就容易连边了。至于怎么限制一个点一个 o 可以限制到汇点的流量。之后来一手最大费用最大流就行。

if(s[i][j] == '#') continue;
if(i != n && s[i + 1][j] != '#') zkw.addedge(Hash(i, j), Hash(i+1, j), n*m+10, 1);
if(j != m && s[i][j + 1] != '#') zkw.addedge(Hash(i, j), Hash(i, j+1), n*m+10, 1);
zkw.addedge(Hash(i, j), n * m + 2, 1, 0);
if(s[i][j] == 'o') zkw.addedge(n * m + 1, Hash(i, j), 1, 0);

D - Keep Distances

好题。

感性认知发现我们从左往右贪心跳最小的，再从右往左贪心跳最大的，那么每一个位置一定在对应位之间。大胆猜想，手摸作为证明就行。

其实证明不难

那么倍增跳一跳就行了。