AtCoder Grand Contest 033 题解

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

Visits: 329

AtCoder Grand Contest 033

Contents hide
1 Darker and Darker
2 LRUD Game
3 Removing Coins
4 Complexity
4.1 题意
4.2 题解
4.3 代码
5 Go around a Circle
5.1 题意
5.2 题解
5.3 代码
6 Adding Edges
6.1 题意
6.2 题解
6.3 代码

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$ 的只包含 R 和 B 的字符串 $s$，求出有多少种染色方案，满足将棋子放在任意一个点上，都存在一种进行 $m$ 次操作的方案，每次操作选择将棋子顺时针或逆时针移动一段，使得经过的第 $i$ 段为 $s_i$。
  • $n,m \le 2 \times 10^5$，答案对 $10^9+7$ 取模。

题解

不妨设 $s_1$ 为 R，若不是则交换 R 和 B，那么圆上显然不存在连续两段为 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;
}

发表评论

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

更多阅读
标签云
AC 自动机 bitset DP Hash Trie Two Pointers 二分 二分图 交互题 凸包 前缀和/差分 区间 DP 单调栈 单调队列 博弈论 可持久化 基环树 容斥 并查集 扫描线 换根 DP 数论 曼哈顿距离 最小生成树 最短路 构造 树形 DP 树状数组 树链剖分 根号分治 概率期望 欧拉回路 状压 生成函数 矩阵 线段树 组合计数 网络流 背包 计算几何 记忆化搜索 调和级数 贪心 费用流 随机化