AtCoder Grand Contest 031 题解

作者: xht37 分类: 题解 发布时间: 2020-07-08 16:34

点击数:27

AtCoder Grand Contest 031

Colorful Subsequence

对于每种字符,可以选某一个或者不选,最后去掉空的。

const int N = 1e5 + 7;
int n;
char s[N];

int main() {
    rd(n), rds(s, n);
    map<char, int> c;
    for (int i = 1; i <= n; i++) ++c[s[i]];
    modint ans = 1;
    for (pi o : c) ans *= o.se + 1;
    print(ans - 1);
    return 0;
}

Reversi

首先去重,显然不影响答案。

考虑 DP,设 $f_i$ 表示以 $i$ 为最终某一段的结尾。

枚举 $i$ 所在的段的长度转移,注意 $i$ 所在的段比如跟 $i$ 的颜色相同,时间复杂度 $\mathcal O(n^2)$。

考虑转移的条件,对于每种颜色记录所有这个颜色的转移和,时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, a[N];
modint c[N], f[N];

int main() {
    rd(n), rda(a, n);
    n = unique(a + 1, a + n + 1) - (a + 1);
    c[a[1]] = f[0] = 1;
    for (int i = 1; i <= n; i++)
        f[i] = c[a[i]], c[a[i+1]] += f[i];
    print(f[n]);
    return 0;
}

Differ by 1 Bit

如果 $a\operatorname{xor}b$ 中有奇数个 $1$ 则 YES,否则 NO

构造可以递归构造,时间复杂度 $\mathcal O(n2^n)$。

void f(int a, int b, int s) {
    if (s) {
        int d = (a ^ b) & s;
        s ^= d &= -d;
        int c = a ^ (s & -s);
        f(a, c, s), f(c ^ d, b, s);
    } else print(a, ' ');
}

int main() {
    int n, a, b;
    rd(n, a, b);
    if (__builtin_parity(a ^ b)) prints("YES"), f(a, b, (1 << n) - 1);
    else prints("NO");
    return 0;
}

A Sequence of Permutations

题意

  • 对于 $1 \sim n$ 的排列 $p,q$,定义排列 $f(p,q)$,满足 $f(p,q)$ 的第 $p_i$ 个元素为 $q_i$。
  • 定义排列的序列 $a$ 满足,$a_1 = p$,$a_2 = q$,$a_{n+2} = f(a_n,a_{n+1})(n \ge 1)$。
  • 求 $a_k$。
  • $n \le 10^5$,$k \le 10^9$。

题解

注意到 $f(p,q) = qp^{-1}$,另有 $(pq)^{-1} = q^{-1}p^{-1}$,于是有:
$$
\begin{aligned}
a_1 &= p \\
a_2 &= q \\
a_3 &= qp^{-1} \\
a_4 &= qp^{-1}q^{-1} \\
a_5 &= qp^{-1}q^{-1}pq^{-1} \\
a_6 &= qp^{-1}q^{-1}pq^{-1}qpq^{-1} = qp^{-1}q^{-1}p^{2}q^{-1} \\
a_7 &= qp^{-1}q^{-1}p^{2}q^{-1}qp^{-1}qpq^{-1} = qp^{-1}q^{-1}pqpq^{-1} \\
a_8 &= qp^{-1}q^{-1}pqpq^{-1}qp^{-2}qpq^{-1} = qp^{-1}q^{-1}pqp^{-1}qpq^{-1} \\
\end{aligned}
$$
记 $t=qp^{-1}q^{-1}p$,则 $a_7 = tpt^{-1}$,$a_8 = tqt^{-1}$。

于是得到规律:$a_{n+6} = ta_nt^{-1}$,$a_{n+6k} = t^{k}a_nt^{-k}$。

快速幂即可,时间复杂度 $\mathcal O(n \log k)$。

代码

const int N = 1e5 + 7;
int n, k, p[N], q[N], vp[N], vq[N], t[N], vt[N], ans[N];

inline void init(int *a) {
    for (int i = 1; i <= n; i++) a[i] = i;
}

inline void inv(int *a, int *b) {
    for (int i = 1; i <= n; i++) b[a[i]] = i;
}

inline void mul(int *a, int *b) {
    static int c[N];
    for (int i = 1; i <= n; i++) c[i] = a[b[i]];
    for (int i = 1; i <= n; i++) a[i] = c[i];
}

inline void ksm(int *a, int b) {
    static int d[N];
    init(d);
    while (b) {
        if (b & 1) mul(d, a);
        mul(a, a), b >>= 1;
    }
    for (int i = 1; i <= n; i++) a[i] = d[i];
}

int main() {
    rd(n, k), rda(p, n), rda(q, n), inv(p, vp), inv(q, vq);
    init(t), mul(t, q), mul(t, vp), mul(t, vq), mul(t, p), inv(t, vt);
    int r = k % 6 ? k % 6 : 6, w = (k - r) / 6;
    ksm(t, w), ksm(vt, w);
    init(ans), mul(ans, t);
    switch (r) {
        case 1 : mul(ans, p); break;
        case 2 : mul(ans, q); break;
        case 3 : mul(ans, q), mul(ans, vp); break;
        case 4 : mul(ans, q), mul(ans, vp), mul(ans, vq); break;
        case 5 : mul(ans, q), mul(ans, vp), mul(ans, vq), mul(ans, p), mul(ans, vq); break;
        case 6 : mul(ans, q), mul(ans, vp), mul(ans, vq), mul(ans, p), mul(ans, p), mul(ans, vq); break;
    }
    mul(ans, vt);
    printa(ans, n);
    return 0;
}

Snuke the Phantom Thief

题意

  • 有 $n$ 个两两不同的点,第 $i$ 个点的坐标为 $(x_i,y_i)$,价值为 $v_i$。
  • 你要选择一些点,满足 $m$ 条限制,每条限制形如:
    • L a b,最多选择 $b$ 个 $x_i \le a$ 的点。
    • R a b,最多选择 $b$ 个 $x_i \ge a$ 的点。
    • D a b,最多选择 $b$ 个 $y_i \le a$ 的点。
    • U a b,最多选择 $b$ 个 $y_i \ge a$ 的点。
  • 求选择的点的最大价值和。
  • $n \le 80$,$m \le 320$。

题解

枚举选择的点的个数 $k$,考虑费用流。

对于每一维,那么最多 $b$ 个 $\le a$ 的点可以转化为按坐标从小到大选择的第 $[b+1,k]$ 个点的坐标要 $\ge a + 1$,最多 $b$ 个 $\ge a$ 的点可以转化为选择的第 $[1,k-b]$ 个点的坐标要 $\le a – 1$。

考虑如何建图,将点 $i$ 拆成两个点 $P_i,Q_i$,另外加入 $2k$ 个点 $X_{1\dots k},Y_{1\dots k}$,表示某一维上选择的第 $i$ 个点。

连边如下:

  • $(S, X_i, 1, 0)$。
  • $(X_i,P_j,1,0)$,其中点 $j$ 在 $X_i$ 的坐标限制内。
  • $(P_j,Q_j,1,-v_j)$。
  • $(Q_j,Y_i,1,0)$,其中点 $j$ 在 $Y_i$ 的坐标限制内。
  • $(Y_i,T,1,0)$。

跑最小费用最大流即可。

代码

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;

const int N = 87, M = 327;
int n, m, x[N], y[N], a[M], b[M];
char t[M];
ll v[N], ans;

inline bool in(int l, int x, int r) {
    return l <= x && x <= r;
}

inline ll work(int k) {
    static int lx[N], rx[N], ly[N], ry[N];
    for (int i = 1; i <= k; i++)
        lx[i] = ly[i] = 1, rx[i] = ry[i] = 100;
    for (int i = 1; i <= m; i++)
        switch (t[i]) {
            case 'L' : {
                for (int j = b[i] + 1; j <= k; j++)
                    lx[j] = max(lx[j], a[i] + 1);
                break;
            }
            case 'R' : {
                for (int j = 1; j <= k - b[i]; j++)
                    rx[j] = min(rx[j], a[i] - 1);
                break;
            }
            case 'D' : {
                for (int j = b[i] + 1; j <= k; j++)
                    ly[j] = max(ly[j], a[i] + 1);
                break;
            }
            case 'U' : {
                for (int j = 1; j <= k - b[i]; j++)
                    ry[j] = min(ry[j], a[i] - 1);
                break;
            }
        }
    for (int i = 1; i <= n; i++)
        if (lx[i] > rx[i] || ly[i] > ry[i]) return 0;
    static int S, T, P[N], Q[N], X[N], Y[N], C;
    S = 1, T = 2, C = 2;
    for (int i = 1; i <= n; i++) P[i] = ++C, Q[i] = ++C;
    for (int i = 1; i <= k; i++) X[i] = ++C, Y[i] = ++C;
    Dinic::init(C, S, T);
    for (int i = 1; i <= n; i++) add(P[i], Q[i], 1, -v[i]);
    for (int i = 1; i <= k; i++) {
        add(S, X[i], 1, 0), add(Y[i], T, 1, 0);
        for (int j = 1; j <= n; j++) {
            if (in(lx[i], x[j], rx[i])) add(X[i], P[j], 1, 0);
            if (in(ly[i], y[j], ry[i])) add(Q[j], Y[i], 1, 0);
        }
    }
    Dinic::main();
    return Dinic::mxf == k ? -Dinic::ans : 0;
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(x[i], y[i]), rd(v[i]);
    rd(m);
    for (int i = 1; i <= m; i++) rdc(t[i]), rd(a[i], b[i]);
    for (int k = 1; k <= n; k++) ans = max(ans, work(k));
    print(ans);
    return 0;
}

Walk on Graph

题意

  • 给定一张 $n$ 个点 $m$ 条边的连通无向图,边有长度。
  • 定义一条路径的长度为,设这条路径经过的边的长度依次为 $l_{1\dots k}$,则路径长度为 $\sum_{i=1}^{k} l_i2^{i-1}$。
  • 有 $q$ 次询问,每次给定 $s,t,r$,求是否存在一条 $s \to t$ 的路径,满足其长度模 $P$ 的值为 $r$。
  • $n,m,q \le 5 \times 10^4$,$P \le 10^6$ 且为奇数。

题解

倒过来考虑这个问题,走一条边 $c$ 就是 $x\to 2x+c$,因为 $P$ 是奇数,所以 $2$ 有逆元,即这是一个双射,所以一定能回到自己。

注意到一个点走两次一条边会回到自己,$x\to 4x+3c$,那么如果有另一条边 $c^\prime$,则我们能凑出 $3(c-c^\prime)$。记 $g$ 是所有边权之差以及 $P$ 的 $\gcd$,那么我们只需要在模 $\gcd(3g, P)$ 意义下考虑这个问题即可(此时模数要么是 $g$ 要么是 $3g$)。

假设所有边模 $g$ 都为 $z$,那么令 $x^\prime=x+z$,将边权减去 $z$,走一步后新的 $x^\prime$ 会变成 $2(x^\prime-z) + (c+z) + z = 2x^\prime + c$,和原来的规则一样,所以我们可以认为在新的图中,每条边都是 $g$ 的倍数。

对于 $(1,x)$,其能到的状态可以写成 $(v, 2^px+qg)(0\le q<3)$ 的形式,由之前的变换 $x\to 4x+3c$,且 $c$ 是 $g$ 的倍数,得 $x$ 和 $4x$ 是等价状态,故 $0\le p<2$。这样新的图中点数就只有 $\mathcal O(n)$ 个了,用并查集连一下就好了。

代码

const int N = 5e4 + 7, M = 1e6 + 7;
int n, m, q, P, a[N], b[N], c[N], f[N*6+1], g, z;
bool v[2][M];

inline int get(int x) {
    return x == f[x] ? x : f[x] = get(f[x]);
}

inline void merge(int x, int y) {
    f[get(x)] = get(y);
}

inline int id(int x, int y, int z) {
    return (x - 1) * 6 + y * 3 + z;
}

int main() {
    rd(n, m, q), rd(P);
    for (int i = 1; i <= m; i++)
        rd(a[i], b[i], c[i]), g = __gcd(g, abs(c[i] - c[1]));
    g = g ? g : P, P = __gcd(P, 3 * g), z = c[1] % g;
    for (int i = 1; i <= 6 * n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) {
        int w = (c[i] - z) / g;
        for (int p = 0; p < 2; p++)
            for (int q = 0; q < 3; q++)
                merge(id(a[i], p, q), id(b[i], 1 - p, (2 * q + w) % 3)),
                merge(id(b[i], p, q), id(a[i], 1 - p, (2 * q + w) % 3));
    }
    for (int i = 0, j = z; i < P << 1; i++, (j <<= 1) %= P) v[i&1][j] = 1;
    for (int i = 1, s, t, r; i <= q; i++) {
        rd(s, t, r);
        bool ans = 0;
        for (int p = 0; p < 2; p++)
            for (int q = 0; q < 3; q++)
                if (get(id(t, 0, 0)) == get(id(s, p, q)))
                    ans |= v[p][(r+z+(3-q)*g)%P];
        prints(ans ? "YES" : "NO");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注