November 1, 2022

Educational Codeforces Round 138

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 E. Cactus Wall

平面图最小割

等价于对偶图最短路
边权只有 01，所以开两个队列 bfs() 即可。

Posted by xiaodao
Category: 日常

某岛

Educational Codeforces Round 138

Problem D. Letter Picking

Problem E. Red-Black Pepper

Problem E. Cactus Wall

Archives

Blogroll

Links

Myself

Project