AtCoder Grand Contest 033 – 解题报告

A – Darker and Darker

一眼题，直接 BFS 找最长最短路即可。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2020, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

typedef pair<int, int> pii;

int n, m, dist[MAX_N][MAX_N];
char S[MAX_N][MAX_N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", S[i] + 1);
    memset(dist, 0x3f, sizeof(dist));
    queue<pii> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (S[i][j] == '#')
                dist[i][j] = 0, q.push(make_pair(i, j));
    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++)
        {
            int dstx = x + dx[d], dsty = y + dy[d];
            if (S[dstx][dsty] != '\0' && dist[dstx][dsty] > dist[x][y] + 1)
                dist[dstx][dsty] = dist[x][y] + 1, q.push(make_pair(dstx, dsty));
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, dist[i][j]);
    printf("%d\n", ans);
    return 0;
}

B – LRUD Game

贪心的考虑四个方向能不能越出边界即可，很傻逼。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

int n, m, len, sx, sy;
char S[MAX_N], T[MAX_N];

int main()
{
    scanf("%d%d%d%d%d%s%s", &n, &m, &len, &sx, &sy, S + 1, T + 1);
    // upper;
    bool ans = false;
    int x = sx, y = sy;
    for (int i = 1; i <= len; i++)
    {
        if (S[i] == 'U')
            x--;
        if (x < 1)
            ans = true;
        if (T[i] == 'D' && x < n)
            x++;
        if (x < 1)
            ans = true;
    }
    x = sx, y = sy;
    for (int i = 1; i <= len; i++)
    {
        if (S[i] == 'D')
            x++;
        if (x > n)
            ans = true;
        if (T[i] == 'U' && x > 1)
            x--;
        if (x > n)
            ans = true;
    }
    x = sx, y = sy;
    for (int i = 1; i <= len; i++)
    {
        if (S[i] == 'L')
            y--;
        if (y < 1)
            ans = true;
        if (T[i] == 'R' && y < m)
            y++;
        if (y < 1)
            ans = true;
    }
    x = sx, y = sy;
    for (int i = 1; i <= len; i++)
    {
        if (S[i] == 'R')
            y++;
        if (y > m)
            ans = true;
        if (T[i] == 'L' && y > 1)
            y--;
        if (y > m)
            ans = true;
    }
    puts(ans ? "NO" : "YES");
    return 0;
}

C – Removing Coins

首先考虑一条链的情况，每次可以选一端或者是非端点进行操作，所以就变成了巴什博弈。然后仔细思考，最后怎么搞都变成直径的子链，所以对直径长度 \(+ 1 \bmod 3\) 进行判断，如果模出来为 \(2\)，那就后手赢，亦而反之。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

int n, head[MAX_N], current, up[MAX_N];
bool tag[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

int max_dist, pt;

void dfs(int u, int fa, int dep)
{
    if (max_dist < dep)
        pt = u, max_dist = dep;
    up[u] = fa;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u, dep + 1);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    int A, B;
    dfs(1, 0, 0), max_dist = 0, A = pt, dfs(pt, 0, 0), B = pt;
    if ((max_dist + 1) % 3 == 2)
        puts("Second");
    else
        puts("First");
    return 0;
}

D – Complexity

这个题纪中出过加强版，我当然不会（加强版好像是用单调栈 + 线段树搞）。

首先想出 sb 暴力 \(\Theta(n^5)\)，设置状态 \(dp[x][y][a][b]\) 为当前子矩阵，然后乱切即可。

然后可以考虑用背包中大体积小价值的思想去对状态进行优化，显然答案上界为 \(\Theta(\log_2 n + \log_2 m)\)，所以可以考虑设 \(dp[i][l][r][k]\) 为左上角 \((i, l)\)、左下角 \((i, r)\) 且用 \(k\) 的代价，能向右的最大距离。

这个可以做到 \(\Theta(n^4 \log_2 n)\)。继续优化，发现如果是竖着切，其实循环个 \(\log_2 n\) 差不多，所以这部分是 \(n^3 \log_2 n\)。如果是横着切就没那么简单了。当然，如果横着切，我们肯定会尽量让上下均等，这样是最优的，所以套个二分即可。最后枚举答案，然后疯狂切分即可。

// D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 220, MAX_LOG = 20;

int n, m, sum[MAX_N][MAX_N], dp[2][MAX_N][MAX_N][MAX_N];
char str[MAX_N][MAX_N];

bool check(int i, int j, int l, int r)
{
    int acc = sum[j][r] - sum[i - 1][r] - sum[j][l - 1] + sum[i - 1][l - 1];
    return acc == 0 || acc == 1LL * (j - i + 1) * (r - l + 1);
}

int calc(int p, int i, int j, int k)
{
    int l = i, r = j - 1, res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        res = max(res, min(dp[p][i][mid][k], dp[p][mid + 1][j][k]));
        if (dp[p][i][mid][k] < dp[p][mid + 1][j][k])
            r = mid - 1;
        else
            l = mid + 1;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", str[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (str[i][j] == '#');
    if (check(1, n, 1, m))
        puts("0"), exit(0);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int k = 1, acc; k <= m; k = acc)
            {
                acc = k;
                while (acc <= m && check(i, j, k, acc))
                    acc++;
                for (int p = k; p < acc; p++)
                    dp[0][i][j][p] = acc - 1;
                if (acc == k)
                    dp[0][i][j][k] = k - 1, acc++;
            }
    for (int x = 1;; x++)
    {
        int c = x & 1, pc = !(x & 1);
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                for (int k = 1; k <= m; k++)
                {
                    int ret = dp[pc][i][j][k];
                    if (ret == m)
                        dp[c][i][j][k] = m;
                    else
                        dp[c][i][j][k] = max(dp[pc][i][j][ret + 1], calc(pc, i, j, k));
                }
        if (dp[c][1][n][1] == m)
            printf("%d\n", x), exit(0);
    }
    return 0;
}