Visits: 354

AtCoder Grand Contest 034

Kenken Race

分 $c < d$ 和 $c>d$ 讨论一下，后者合法多一个限制：存在 $i \in [b,d]$ 满足 $i-1,i,i+1$ 都是空的。

const int N = 2e5 + 7;
int n, a, b, c, d;
char s[N];

inline bool pd(int i, int j) {
    while (i != j) {
        if (s[i+1] == '#' && s[i+2] == '#') return 0;
        if (s[i+1] == '.') i += 1;
        else i += 2;
    }
    return 1;
}

int main() {
    rd(n), rd(a, b), rd(c, d), rds(s, n);
    if (c < d) return prints(pd(a, c) && pd(b, d) ? "Yes" : "No"), 0;
    bool ok = 0;
    for (int i = b; i <= d; i++)
        if (s[i] == '.' && s[i-1] == '.' && s[i+1] == '.') ok = 1;
    prints(ok && pd(a, c) && pd(b, d) ? "Yes" : "No");
    return 0;
}

ABC

每次操作相当于将 BC 移到 A 后面，从前往后做就行了。

const int N = 2e5 + 7;
int n;
char s[N];
ll ans;

int main() {
    rds(s, n);
    for (int i = 1, t = 0; i < n; i++)
        if (s[i] == 'B' && s[i+1] == 'C') ans += t, ++i;
        else if (s[i] == 'A') ++t;
        else t = 0;
    print(ans);
    return 0;
}

Tests

显然答案是若干个 $x$，一个 $[0,x]$，若干个 $0$。

二分答案，枚举 $[0,x]$ 的那个找到最大值，时间复杂度 $\mathcal O(n \log (nx))$。

const int N = 1e5 + 7;
int n, x, p[N];
ll b[N], l[N], r[N], s[N], sum;

inline ll calc(int x, ll t) {
    return t <= b[x] ? t * l[x] : b[x] * l[x] + (t - b[x]) * r[x];
}

inline ll pd(ll t) {
    int w = t % x ? t % x : x, c = (t - w) / x;
    ll sum = 0, ret = 0;
    for (int i = 1; i <= c; i++) sum += s[p[i]];
    for (int i = c + 1; i <= n; i++)
        ret = max(ret, sum + calc(p[i], w));
    sum += s[p[c+1]];
    for (int i = 1; i <= c; i++)
        ret = max(ret, sum - s[p[i]] + calc(p[i], w));
    return ret;
}

int main() {
    rd(n, x);
    for (int i = 1; i <= n; i++)
        rd(b[i], l[i], r[i]), p[i] = i,
        s[i] = b[i] * l[i] + (x - b[i]) * r[i], sum += b[i] * l[i];
    sort(p + 1, p + n + 1, [&](int i, int j) { return s[i] > s[j]; });
    if (!sum) return print(0), 0;
    ll l = 1, r = 1ll * n * x;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (pd(mid) >= sum) r = mid;
        else l = mid + 1;
    }
    print(l);
    return 0;
}

Manhattan Max Matching

题意

• 在平面上有 $n$ 个位置有红点，$n$ 个位置上有蓝点，其中 $(rx_i,ry_i)$ 上有 $rc_i$ 个红点，$(bx_i,by_i)$ 上有 $bc_i$ 个蓝点，红蓝点总个数相同。
• 现在要将红蓝点一一匹配，两点匹配的价值为其曼哈顿距离，要求最大价值和。
• $n \le 10^3$，$rc_i,bc_i \le 10$。

题解

首先显然可以直接建图跑费用流，但边数为 $\mathcal O(n^2)$ 无法接受。

考虑曼哈顿距离有性质：

$$
\begin{aligned}
|x_1-x_2|+|y_1-y_2|
&=\max(
x_1-x_2+y_1-y_2,
x_1-x_2-y_1+y_2,
-x_1+x_2+y_1-y_2,
-x_1+x_2-y_1+y_2
)\\
&=\max(
(x_1+y_1)+(-x_2-y_2),
(x_1-y_1)+(-x_2+y_2),
(-x_1+y_1)+(x_2-y_2),
(-x_1-y_1)+(x_2+y_2)
)\\
\end{aligned}
$$

于是只需要建四个点对应每种情况，边数 $\mathcal O(n)$，可以直接跑费用流。

代码

namespace Dinic {
    const int N = 1e5 + 7, M = 2e6 + 7;
    const ll inf = 1e18;
    int n, S, T;
    int h[N], hi[N], e[M], t[M], tot;
    ll d[N], f[M], c[M], mxf, ans;
    bool v[N];

    inline void add(int x, int y, ll z, ll w, bool o = 1) {
        e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0, -w, 0);
    }

    inline bool bfs() {
        for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
        queue<int> q;
        q.push(S), d[S] = 0, v[S] = 1;
        while (q.size()) {
            int x = q.front();
            q.pop(), v[x] = 0;
            for (int i = h[x]; i; i = t[i]) {
                int y = e[i];
                ll z = f[i], w = c[i];
                if (d[y] <= d[x] + w || !z) continue;
                d[y] = d[x] + w;
                if (!v[y]) q.push(y), v[y] = 1;
            }
        }
        return d[T] != inf;
    }

    ll dfs(int x, ll now = inf) {
        if (x == T) return now;
        v[x] = 1;
        ll rst = now;
        for (int &i = hi[x]; i; i = t[i]) {
            int y = e[i];
            ll z = f[i], w = c[i];
            if (v[y] || d[y] != d[x] + w || !z) continue;
            ll k = dfs(y, min(z, rst));
            if (!k) d[y] = inf;
            else ans += k * w, f[i] -= k, f[i^1] += k, rst -= k;
            if (!rst) break;
        }
        v[x] = 0;
        return now - rst;
    }

    inline void main() {
        while (bfs()) {
            for (int i = 1; i <= n; i++) hi[i] = h[i];
            ll now;
            while ((now = dfs(S))) mxf += now;
        }
    }

    inline void init(int _n, int _S, int _T) {
        n = _n, S = _S, T = _T, tot = 1, mxf = 0, ans = 0;
        for (int i = 1; i <= n; i++) h[i] = 0; 
    }
}
using Dinic::add;
using Dinic::inf;

int main() {
    int n;
    rd(n);
    int p1 = n << 1 | 1, p2 = p1 + 1, p3 = p2 + 1, p4 = p3 + 1;
    int S = p4 + 1, T = S + 1;
    Dinic::init(T, S, T);
    for (int i = 1, x, y, c; i <= n; i++)
        rd(x, y, c),
        add(S, i, c, 0),
        add(i, p1, inf, x + y),
        add(i, p2, inf, x - y),
        add(i, p3, inf, -x + y),
        add(i, p4, inf, -x - y);
    for (int i = 1, x, y, c; i <= n; i++)
        rd(x, y, c),
        add(i + n, T, c, 0),
        add(p1, i + n, inf, -x - y),
        add(p2, i + n, inf, -x + y),
        add(p3, i + n, inf, x - y),
        add(p4, i + n, inf, x + y);
    Dinic::main();
    print(-Dinic::ans);
    return 0;
}

Complete Compress

题意

• 给定一棵 $n$ 个点的树，树上的某些节点上有一个人。
• 每次可以选择两个距离 $\ge 2$ 的人，它们将向对方移动一个点。
• 问能否使得所有人都在一个点上。
• $n \le 2 \times 10^3$。

题解

枚举最终的点 $rt$，以 $rt$ 为根建树。

则每一步必然是找到两个非祖先关系的人，向着它们的 $\text{lca}$ 移动一格。

若将点 $x$ 上的人视为 $\text{dist}(rt,x)$ 个，则问题等价于每次消掉两个非祖先关系的人，问是否能消完。

考虑 DP，设 $f_u$ 表示 $u$ 子树的答案，设 $d_u$ 表示 $u$ 子树内的人数，则：

• 若 $u$ 存在某个儿子 $v$，满足 $d_u < 2d_v$，则有转移 $f_u = d_u – d_v + \min(f_v, \lfloor\frac{2d_v – d_u}{2} \rfloor)$。
• 否则，$f_u = \lfloor\frac{d_u}{2} \rfloor$。

最终要求 $d_{rt}$ 为偶数，且 $2f_{rt} \ge d_{rt}$ 才能更新答案。

代码

const int N = 2e3 + 7, inf = 1e9;
int n, m, d[N], s[N], f[N], ans = inf;
char a[N];
vi e[N];

void dfs(int x, int fa = 0) {
    s[x] = a[x] == '1', d[x] = 0;
    int o = 0;
    for (int y : e[x])
        if (y != fa) {
            dfs(y, x), s[x] += s[y], d[x] += d[y] += s[y];
            if (d[y] > d[o]) o = y;
        }
    if (d[x] >= 2 * d[o]) f[x] = d[x] >> 1;
    else f[x] = d[x] - d[o] + min(f[o], (d[o] * 2 - d[x]) >> 1);
}

int main() {
    rd(n), rds(a, n);
    for (int i = 1; i <= n; i++) m += a[i] == '1';
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    for (int x = 1; x <= n; x++) {
        dfs(x);
        if (d[x] & 1) continue;
        if (f[x] * 2 >= d[x]) ans = min(ans, d[x]);
    }
    print(ans == inf ? -1 : ans >> 1);
    return 0;
}

RNG and XOR

题意

• 给定 $n$ 和 $a_{0\dots 2^n-1}$。
• 有一个初始为 $0$ 的变量 $x$。
• 每次操作会将 $x$ 以 $\frac {a_i}{\sum_{j=0}^{2^n-1}a_j}$ 的概率异或上 $i$。
• 求对于 $i \in [0,2^n-1]$，$x$ 第一次变成 $i$ 的期望操作次数。
• $n \le 18$，$a_i \le 10^3$，答案对 $998244353$ 取模。

题解

为了方便，将 $a_i$ 视为 $\frac {a_i}{\sum_{j=0}^{2^n-1}a_j}$。

设 $x_i$ 为 $i$ 第一次变成 $0$ 的期望操作次数，显然 $x_i$ 也是 $0$ 第一次变成 $i$ 的期望操作次数。

有转移：
$$
x_i =
\begin{cases}
0 & i = 0 \\
\sum_{j=0}^{2^n-1} a_jx_{i\operatorname{xor}j} + 1 & i \ne 0
\end{cases}
$$
即异或卷积：
$$
(x_0,x_1,\cdots,x_{2^n-1})\operatorname{xor}(p_0,p_1,\cdots,p_{2^n-1}) = (c,x_1-1,x_2-1,\cdots,x_{2^n-1}-1)
$$
其中 $c$ 为一个常数。

注意到显然异或卷积 $(p_0,p_1,\cdots,p_{2^n-1})$ 后总和不变，因此 $c = x_0+2^n-1$，即：
$$
(x_0,x_1,\cdots,x_{2^n-1})\operatorname{xor}(p_0,p_1,\cdots,p_{2^n-1}) = (x_0+2^n-1,x_1-1,x_2-1,\cdots,x_{2^n-1}-1)
$$
注意到如果将 $p_0$ 减 $1$，那么右边第 $i$ 项会减去 $x_i$，正好把右边的未知项删掉了，即：
$$
(x_0,x_1,\cdots,x_{2^n-1})\operatorname{xor}(p_0-1,p_1,\cdots,p_{2^n-1}) = (2^n-1,-1,-1,\cdots,-1)
$$
这时异或卷积中的三项有两项都已知了，那么剩下的一项可以直接 FWT 求出。

然而会发现求出的答案不对，问题出在这样的异或卷积是有不只一组解的，对每个 $x_i$ 都加上 $k$ 之后式子依然成立。

又注意到 $x_0 = 0$，因此我们把求出来的每一项都减去 $x_0$ 就是我们要的答案。

时间复杂度 $\mathcal O(n2^n)$。

代码

const int N = 1 << 18 | 1;
int n;
modint a[N], b[N], s;

inline void XOR(modint *f, modint x) {
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j++) {
                modint p = f[i+j] * x, q = f[i+j+k] * x;
                f[i+j] = p + q, f[i+j+k] = p - q;
            }
}

int main() {
    rd(n), n = 1 << n;
    for (int i = 0; i < n; i++) rd(a[i]), b[i] = P - 1, s += a[i];
    modint vs = 1 / s;
    for (int i = 0; i < n; i++) a[i] *= vs;
    a[0] -= 1, b[0] = n - 1;
    XOR(a, 1), XOR(b, 1);
    for (int i = 0; i < n; i++) b[i] /= a[i];
    XOR(b, (modint)1 / 2);
    for (int i = 0; i < n; i++) print(b[i] - b[0]);
    return 0;
}