AtCoder Grand Contest 033 题解

作者: xht37 分类: 题解 发布时间: 2020-07-05 17:21

点击数:124

AtCoder Grand Contest 033

Darker and Darker

怎么 AGC 还有这种垃圾题啊。

const int N = 1e3 + 7;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
int n, m, d[N][N], ans;
queue<pi> q; 

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char c;
            rdc(c);
            if (c == '#') q.push(mp(i, j));
            else d[i][j] = -1; 
        }
    while (q.size()) {
        int x = q.front().fi, y = q.front().se;
        q.pop();
        ans = d[x][y];
        for (int i = 0; i < 4; i++) {
            int X = x + dx[i], Y = y + dy[i];
            if (X < 1 || X > n || Y < 1 || Y > m || ~d[X][Y]) continue;
            d[X][Y] = d[x][y] + 1, q.push(mp(X, Y));
        }
    }
    print(ans);
    return 0;
}

LRUD Game

四个方向独立,每个方向都判一下即可。

const int N = 2e5 + 7;
int n, m, k, x, y;
char a[N], b[N];

inline bool pd(int t, int w, char p, char q) {
    for (int i = 1; i <= k; i++) {
        if (a[i] == p) --t;
        if (!t) return 0;
        if (t != w && b[i] == q) ++t;
    }
    return 1;
}

int main() {
    rd(n, m, k), rd(x, y), rds(a, k), rds(b, k);
    if (!pd(x, n, 'U', 'D')) return prints("NO"), 0;
    if (!pd(n - x + 1, n, 'D', 'U')) return prints("NO"), 0;
    if (!pd(y, m, 'L', 'R')) return prints("NO"), 0;
    if (!pd(m - y + 1, m, 'R', 'L')) return prints("NO"), 0;
    prints("YES");
    return 0;
}

Removing Coins

考虑直径,设直径包含的点数为 $d$,若 $d \ge 3$,则每次操作可以把 $d$ 减去 $1$ 或 $2$,否则只能把 $d$ 减 $1$。

于是变成一个经典的博弈论问题,当一开始 $d \equiv 2 \pmod 3$ 时后手胜,否则先手胜。

const int N = 2e5 + 7;
int n, d[N];
vi e[N];

void dfs(int x, int f) {
    for (int y : e[x])
        if (y != f) d[y] = d[x] + 1, dfs(y, x);
}

int main() {
    rd(n);
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    d[1] = 1, dfs(1, 0);
    int rt = max_element(d + 1, d + n + 1) - d;
    d[rt] = 1, dfs(rt, 0);
    int ans = *max_element(d + 1, d + n + 1);
    prints(ans % 3 == 2 ? "Second" : "First");
    return 0;
}

Complexity

题意

  • 给定一个 $n$ 行 $m$ 列的字符矩阵,每个位置上要么为 . 要么为 #
  • 定义一个字符矩阵的凌乱度为:
    • 若所有字符都相同,则凌乱度为 $0$。
    • 否则,考虑所有的沿水平或者竖直方向的直线,将字符矩阵分成两个不为空的部分,设两个部分的凌乱度分别为 $a$ 和 $b$,则凌乱度为 $\max(a,b)+1$ 的最小值。
  • 要求给定的字符矩阵的凌乱度是多少。
  • $n,m \leq 185$。

题解

一个显而易见的 DP 是,将每个子矩阵当作一个状态,枚举直线转移,时间复杂度 $\mathcal O(n^5)$。

注意到凌乱度的最大值是 $\mathcal O(\log n)$ 的,于是设 $f_{i,u,d,l}$ 表示 $(u,d,l)$ 的情况下凌乱度为 $i$ 的最大 $r$,同理 $g_{i,u,l,r}$ 表示 $(u,l,r)$ 的情况下凌乱度为 $i$ 的最大 $d$。

此时转移可以双指针,时间复杂度 $\mathcal O(n^3\log n)$,注意滚动数组优化空间。

代码

const int N = 187;
int n, m, w;
char a[N][N];
int f[N][N][N], g[N][N][N], F[N], G[N];

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++) rds(a[i], m);
    int tn = n - 1, tm = m - 1;
    while (tn) ++w, tn >>= 1;
    while (tm) ++w, tm >>= 1;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            f[l][r][m+1] = m;
            for (int j = m; j; j--)
                if (!(l == r || (a[l][j] == a[r][j] && f[l][r-1][j] >= j))) f[l][r][j] = j - 1;
                else f[l][r][j] = a[l][j] == a[l][j+1] ? f[l][r][j+1] : j;
        }
    for (int l = 1; l <= m; l++)
        for (int r = l; r <= m; r++) {
            g[l][r][n+1] = n;
            for (int i = n; i; i--)
                if (!(l == r || (a[i][l] == a[i][r] && g[l][r-1][i] >= i))) g[l][r][i] = i - 1;
                else g[l][r][i] = a[i][l] == a[i+1][l] ? g[l][r][i+1] : i;
        }
    if (f[1][n][1] == m) return print(0), 0;
    for (int k = 1; k <= w; k++) {
        for (int l = 1; l <= n; l++)
            for (int r = l; r <= n; r++)
                for (int j = 1; j <= m; j++)
                    f[l][r][j] = f[l][r][f[l][r][j]+1];
        for (int l = 1; l <= m; l++)
            for (int r = l; r <= m; r++)
                for (int i = 1; i <= n; i++)
                    g[l][r][i] = g[l][r][g[l][r][i]+1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                for (int p = i; p <= n; p++) F[p] = f[i][p][j];
                for (int p = j; p <= m; p++) G[p] = g[j][p][i];
                F[n+1] = j - 1, G[m+1] = i - 1;
                for (int p = i; p <= n; p++)
                    for (int w = F[p]; w > F[p+1]; w--)
                        g[j][w][i] = max(g[j][w][i], p);
                for (int p = j; p <= m; p++)
                    for (int w = G[p]; w > G[p+1]; w--)
                        f[i][w][j] = max(f[i][w][j], p);
            }
        if (f[1][n][1] == m) return print(k), 0;
    }
    return 0;
}

Go around a Circle

题意

  • 有一个圆被 $n$ 个点分成了等长的 $n$ 段,每段的颜色为 R 或者 B。注意,染色方案旋转不同构。
  • 给定一个长度为 $m$ 的只包含 RB 的字符串 $s$,求出有多少种染色方案,满足将棋子放在任意一个点上,都存在一种进行 $m$ 次操作的方案,每次操作选择将棋子顺时针或逆时针移动一段,使得经过的第 $i$ 段为 $s_i$。
  • $n,m \le 2 \times 10^5$,答案对 $10^9+7$ 取模。

题解

不妨设 $s_1$ 为 R,若不是则交换 RB,那么圆上显然不存在连续两段为 B

若 $s$ 中没有 B,则问题等价于圆上不存在两个连续的 B 的方案数,直接 DP 即可,接下来不考虑这种情况。

由于不存在连续两段为 B,因此我们可以当作圆上若干个非空 R 段被 B 隔开。

记 $s$ 中每一个极大的相同字符段长度为 $c_{1\dots k}$,我们容易得到若干条件:

  1. 圆上每一个 R 段的长度都为奇数。
  2. 圆上每一个 R 段的长度都不超过 $c_1 + 1$。
  3. 若 $k$ 为奇数,即 $s$ 中最后一段为 R,则可以将 $s$ 中的这一段直接去掉,也就是直接将 $k$ 减 $1$。
  4. 对于 $i \in [2,k]$ 且 $i$ 为奇数,若 $c_i$ 为奇数,则圆上每一个 R 段的长度都不超过 $c_i$。

可以证明这些条件为充要条件。

于是问题变成每一段的长度为奇数且不超过一个定值,可以使用前缀和优化 DP 解决,时间复杂度 $\mathcal O(n)$。

代码

const int N = 2e5 + 7;
int n, m, c[N], k, w;
char s[N];

namespace k1 {
    modint f[N][2][2];
    inline void main() {
        f[1][0][0] = f[1][1][1] = 1;
        for (int i = 1; i < n; i++)
            f[i+1][0][0] = f[i][0][0] + f[i][0][1],
            f[i+1][0][1] = f[i][0][0],
            f[i+1][1][0] = f[i][1][0] + f[i][1][1],
            f[i+1][1][1] = f[i][1][0];
        print(f[n][0][0] + f[n][0][1] + f[n][1][0]);
    }
}

modint f[N], g[N], ans;

int main() {
    rd(n, m), rds(s, m);
    for (int l = 1, r = 1; l <= m; l = ++r) {
        while (r < m && s[r+1] == s[l]) ++r;
        c[++k] = r - l + 1;
    }
    if (k == 1) return k1::main(), 0;
    if (n & 1) return print(0), 0;
    w = c[1] + !(c[1] & 1), k -= k & 1;
    for (int i = 3; i <= k; i += 2)
        if (c[i] & 1) w = min(w, c[i]);
    n >>= 1, w >>= 1;
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++)
        g[i] = g[i-1] + (f[i] = g[i-1] - (i - w - 2 >= 0 ? g[i-w-2] : 0));
    for (int i = 0; i <= min(n, w); i++) ans += f[n-i] * (i + 1);
    print(ans + ans);
    return 0;
}

Adding Edges

题意

  • 给定一棵 $n$ 个点的树 $T$ 和一张 $n$ 个点 $m$ 条边的无向图 $G$。
  • 每次可以选择三个满足下列条件的整数 $a,b,c$,在 $G$ 中添加边 $(a,c)$:
    • $G$ 中存在边 $(a,b)$ 和 $(b,c)$,但不存在边 $(a,c)$。
    • $T$ 中存在一条简单路径以某种顺序包含了 $a,b,c$。
  • 求最终 $G$ 中的边数。
  • $n,m \le 2 \times 10^3$。

题解

考虑压缩 $G$,如果存在 $(a,b),(a,c)$ 且在 $T$ 中存在一条路径顺次包含 $a,b,c$,那么删除 $(a,c)$ 加上 $(b,c)$ 不改变答案。

对 $G$ 进行充分压缩后,有结论:最终 $(x,y)$ 有边当且仅当存在 $a_1,a_2,\cdots,a_t$ 满足:

  • $a_1 = x$,$a_t = y$。
  • $G$ 中存在边 $(a_i,a_{i+1})$。
  • $T$ 中存在一条路径顺次包含 $a_1,a_2,\cdots,a_t$。

这个就很好统计了,考虑如何压缩 $G$。

对于一条加边 $(a,b)$,记 $p(a,b)$ 表示在 $T$ 中以 $a$ 为根离 $b$ 最近且在 $G$ 中与 $b$ 相连的祖先,若 $p(a,b)$ 存在,则应该直接加 $(b,p(a,b))$,否则将 $b$ 子树打上标记,碰到边时压缩即可。

时间复杂度 $\mathcal O(n(n+m))$。

代码

const int N = 2e3 + 7;
int n, m, ans;
vi e[N];
int f[N][N], p[N][N];
bool g[N][N];

void dfs(int x, int *f) {
    for (int y : e[x])
        if (y != f[x]) f[y] = x, dfs(y, f);
}

inline void add(int x, int y) {
    if (p[x][y] == y || p[y][x] == x) return;
    if (p[x][y]) return add(p[x][y], y);
    if (p[y][x]) return add(p[y][x], x);
    vector<pi> a;
    for (int i = 0; i < 2; i++) {
        g[x][y] = 1, p[x][y] = y;
        queue<int> q;
        q.push(y);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int v : e[u])
                if (v != f[x][u]) {
                    if (!p[x][v]) p[x][v] = y, q.push(v);
                    else if (g[x][v]) g[x][v] = g[v][x] = 0, a.pb(mp(y, v));
                }
        }
        swap(x, y);
    }
    for (pi o : a) add(o.fi, o.se);
}

void dfs1(int x, int t, int *f) {
    if (p[t][x] == x) ++ans, t = x;
    for (int y : e[x])
        if (y != f[x]) dfs1(y, t, f);
}

int main() {
    rd(n, m);
    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, f[x]);
    for (int i = 1, x, y; i <= m; i++) rd(x, y), add(x, y);
    for (int x = 1; x <= n; x++)
        for (int y : e[x]) dfs1(y, x, f[x]);
    print(ans >> 1);
    return 0;
}

发表评论

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