• https://codeforces.com/contest/1728
• https://zhuanlan.zhihu.com/p/562734265

Problem D. Letter Picking

区间博弈 dp，状态 f[][]，但是比一般的博弈 dp 要简单，转移 trivial。
首先我们可以两轮操作绑定在一起转移，只要考虑长度为偶数的状态，并且也不用记录上一轮选了什么字符。
进一步不难归纳出结果只有可能是先手胜或平局，进一步简化状态和转移。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e3) + 9;
char s[N]; bool f[N][N];
int n;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    Rush {
        n = strlen(RS(s));

        REP(i, n+1) f[i][i] = 0;

        for(int l=2;l<=n;l+=2) {
            REP(i, n-l+1) {
                int j = i+l;
                bool ll = f[i+2][j] || (s[i] > s[i+1]);
                bool lr = f[i+1][j-1] || (s[i] > s[j-1]);
                bool rl = f[i+1][j-1] || (s[j-1] > s[i]);
                bool rr = f[i][j-2] || (s[j-1] > s[j-2]);
                f[i][j] = (ll && lr) || (rl && rr);
            }
        }
        puts(f[0][n] ? "Alice" : "Draw");
    }
}

Problem E. Red-Black Pepper

• https://oi-wiki.org/math/number-theory/bezouts/

调整法。先考虑判定性问题，用扩展欧几里得求丢番图方程 ax + by = n 特解，然后判断是否存在一组解使得 ax 在 [0, n] 范围内即可。

考虑最优化问题，根据输入，可以预处理出关于 ax 的，定义域为 [0, n] 之间整数的，非严格凸函数 f，所谓非严格就是可能中间存在一些相等的情况，比如最值可能会是一个区间，
不过稍后会看到，这问题并不大。。

每次询问的目标函数的定义域则是 f 函数的子集，以特解为中心，每次步长为 lcm(a, b)，这也是非严格凸函数，因为我们已经预处理出了它的导数，所以可以在导数上二分求极值。
不过我们能做的更好，只要检查最值附近的两个点的函数式值 f(xl), f(xr) 即可，具体来说，假设我们预处理阶段保留的是最值的右端点 x0，
那么就检查 xl < x0 <= xr，如果是左端点，
就检查 xl <= x0 < xr。。。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(3e5) + 9;
int a[N], b[N], x0; LL f[N];
int n;

LL exgcd(LL a, LL b, LL &x, LL &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

LL query() {
    LL a, b, x, y; RD(a, b);
    LL d = exgcd(a, b, x, y);
    if (n % d) return -1;
    x *= n/d*a; d = a/d*b;
    x -= ceil(max(0ll, x-x0), d) * d;
    x += max(0ll, x0-x) / d * d;
    LL z = -1; if (x >= 0) checkMax(z, f[x]);
    x += d; if (x <= n) checkMax(z, f[x]);
    return z;
}

void init() {
    RD(n); LL s = 0; REP(i, n) RD(a[i], b[i]), s += b[i];
    REP(i, n) a[i] -= b[i]; sort(a, a+n, greater<int>());
    f[0] = s; REP(i, n) f[i+1] = f[i] + a[i];
    x0 = upper_bound(a, a+n, 0, greater<int>()) - a - 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    init(); Rush OT(query());
}

Problem F. Fishermen

。。。居然比赛时只有 <10 个人过，，，但是做法非常简单。。。
首先可以看出是个最优匹配模型。。然后，权值都在单侧的顶点上，于是可以 sort 之后直接跑 Kuhn’s 算法。。。这是个比较常见的套路。。
然后再加一个优化。。。“if you haven’t found an augmenting path, don’t reset the values representing which vertices were visited by the algorithm.”
就过了。。。囧。。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e3) + 9, N2 = N*N;
int a[N], b[N2], py[N]; bool vis[N2]; VI adj[N2];
int n, bn;

bool dfs(int x) {
    if (vis[x]) return 0;
    vis[x] = 1;
    for (auto y: adj[x]) {
        int xx = py[y];
        if (xx == -1 || dfs(xx)) {
            py[y] = x;
            return 1;
        }
    }
    return 0;
}

LL kuhn() {
    LL z = 0; int c = 0;
    fill(py, py+n, -1);
    REP(i, bn) if (dfs(i)) {
        z += b[i]; fill(vis, vis+bn, 0);
        ++c; if (c == n) break;

    }
    return z;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    RD(n); REP(i, n) {
        RD(a[i]); REP(j, n) b[i*n+j] = a[i]*(j+1);
    }
    bn = n*n; sort(b, b+bn); bn = unique(b, b+bn) - b;

    REP(i, n) {
        int t = 0; REP(j, n) {
            t = lower_bound(b+t, b+bn, a[i]*(j+1)) - b;
            adj[t].PB(i);
        }
    }
    OT(kuhn());
}