ABC311(A-G)

Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） - AtCoder

比较轻松的一场，简单记录一下

A - First ABC ¶

给你一个只含有A、B、C的字符串 $S$ ，每种字符会出现至少一次。求出 $S$ 包含每种字符的最短前缀，输出前缀长度。

扫一轮，记录出现次数就可以了

#include <iostream>

using namespace std;

const int maxn = 110;
int n, cnt[3];
char s[maxn];

int main()
{
    cin >> n >> s;
    for(int i = 0; i < n; i++)
    {
        cnt[s[i] - 'A']++;
        if(cnt[0] && cnt[1] && cnt[2])
        {
            cout << i + 1 << endl;
            break;
        }
    }
    return 0;
}

B - Vacation Together ¶

有 $N$ 个人，每人都有一个长度为 $D$ 的字符串 $S_i$ 表示他接下来 $D$ 天是否有空。若 $S_{i,j}$ 是x表示第 $i$ 个人的第 $j$ 天没空，o则表示有空。

这 $N$ 个人打算找一段连续的，且大家都有空的时间出来玩，求出最长的时间。

o相当于1，x相当于0，用&运算合并成一个字符串，然后滑动窗口取最长。

#include <iostream>

using namespace std;

const int maxn = 110;
int n, d;
char now[maxn], s[maxn];

int main()
{
    cin >> n >> d;
    for(int i = 0; i < d; i++)
        now[i] = 'o';
    for(int i = 0; i < n; i++)
    {
        cin >> s;
        for(int j = 0; j < d; j++)
            if(s[j] == 'x')
                now[j] = 'x';
    }
    int ans = 0;
    for(int i = 0; i < d; i++)
    {
        if(now[i] == 'x')
            continue;
        int j = i;
        while(j+1 < d && now[j+1] == 'o')
            j++;
        ans = max(ans, j - i + 1);
        i = j+1;
    }
    cout << ans << endl;
    return 0;
}

C - Find it!¶

给定一个具有 $N$ 个点、$N$ 条边的有向图，每个点都有且只有一条出边。同时给定一个长度为 $N$的序列 $A$，用 $A_i$ 表示有一条边 $(i, A_i)$ 且 $i ≠ A_i$。

可以证明图中至少存在一个环，找出任意一个环，首先输出环的长度，然后按照顺序输出环中的点。

环存在其实很好证明，因为每个点都有一个出边，随便选一个点开始一直访问，一定会有一个点访问次数超过1次。

假设访问顺序为 $v_1v_2v_3...v_xv_{x+1}...v_{x+k}v_x$ ，则 $v_xv_{x+1}...v_{x+k}v_x$就是环。用ord数组记录访问顺序，fir数组记录第一次出现的下标即可在 $O(n)$ 时间完成。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 2E5 + 10;
int n, A[maxn], ord[maxn], fir[maxn];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    int cur = 1, v = 1;
    while(!fir[v])
    {
        fir[v] = cur;
        ord[cur++] = v;
        v = A[v];
    }
    printf("%d\n", cur-fir[v]);
    for(int i = fir[v]; i < cur; i++)
        printf("%d ", ord[i]);
    return 0;
}

D - Grid Ice Floor ¶

给定一个 $N \times M$ 的矩阵，#表示岩石，.表示冰块。矩阵下标从 $(1, 1)$ 开始，地图的四周一定是岩石，岩石不可通行，你的人物初始停留在 $(2, 2)$ 。人物每次移动时，从上下左右选择一个方向，一路滑行，直到碰到岩石，并在岩石前面的冰块停留，然后开始下一次移动。求出人物能经过的冰块数量（停留也算经过）。

很基础的dfs

#include <iostream>

using namespace std;

const int maxn = 200 + 10;
int n, m;
char g[maxn][maxn];
bool vis[maxn][maxn], col[maxn][maxn];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void dfs(int r, int c)
{
    vis[r][c] = 1;
    for(int i = 0; i < 4; i++)
    {
        int nr = r, nc = c;
        while(g[nr+dr[i]][nc+dc[i]] == '.')
        {
            nr += dr[i], nc += dc[i];
            col[nr][nc] = 1;
        }
        if(!vis[nr][nc])
            dfs(nr, nc);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        scanf("%s", g[i]);
    col[1][1] = 1;
    dfs(1, 1);
    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ans += col[i][j];
    cout << ans << endl;
    return 0;
}

E - Defect-free Squares ¶

给定一个 $H \times W$ 的矩阵，矩阵中有 $N$ 个位置是洞，用 $(r_i, c_i)$ 表示第 $i$ 个洞的位置

问：矩阵中有多少个没有洞的正方形？

数据范围：$1 ≤ H,W ≤ 3000$

预处理出前缀和，正方形的和为0相当于没有洞。然后枚举左上角，对于正方形的边长，二分一个最大值出来，正方形的边长就是以这个点为左上角的个数。$O(n^2logn)$，常数较小，我做的时候就是二分过的。

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 3010;
typedef long long LL;
int n, m, s[maxn][maxn], k, len[maxn][maxn];
int getsum(int r1, int c1, int r2, int c2)
{return s[r2][c2] - s[r2][c1-1] - s[r1-1][c2] + s[r1-1][c1-1];}
int check(int r, int c, int n)
{return !getsum(r, c, r+n-1, c+n-1);}

int main()
{
    cin >> n >> m >> k;
    while(k--)
    {
        int r, c;
        scanf("%d %d", &r, &c);
        s[r][c] = 1;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    int l, r;
    LL ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(getsum(i, j, i, j) == 1)
                continue;
            l = max(1, len[i-1][j-1]-1);
            r = min(n-i, m-j) + 1;
            while(l < r)
            {
                int x = (l + r + 1) / 2;
                if(check(i, j, x))
                    l = x;
                else
                    r = x - 1;
            }
            len[i][j] = l;
            ans += l;
        }
    cout << ans << endl;
    return 0;
}

这里用了len数组，len[i][j]表示以(i,j)为左上角的没有洞的正方形的最大边长，显然，len[i][j]与len[i-1][j-1]是有关系的，二分的时候用len数组可以更加精准的确定l的下界，优化了一点常数。

不过既然能想到len之间的关联，dp几乎是呼之欲出的，只需要稍作修改就可以了。

$dp[i][j]$：以 $(i, j)$ 为右下角的没有洞的正方形的最大边长。

转移也比较直观，如图，dp[i-1][j-1], dp[i-1][j], dp[i][j-1]叠加取最小值即可得到dp[i][j]

\[ dp[i][j] = \left\{ \begin{matrix} min(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]) + 1 & \quad (hole[i][j] == 0) \\ 0 & \quad (hole[i][j] == 1) \end{matrix} \right. \]

时间复杂度 $O(n^2)$

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 3010;
typedef long long LL;
int n, m, k, dp[maxn][maxn];
bool hole[maxn][maxn];

int main()
{
    cin >> n >> m >> k;
    while(k--)
    {
        int r, c;
        scanf("%d %d", &r, &c);
        hole[r][c] = 1;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = hole[i][j] ? 0 : min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
            ans += dp[i][j];
        }
    cout << ans << endl;
    return 0;
}

F - Yet Another Grid Task ¶

给定一个 $N \times M$ 的矩阵，#表示黑色，.表示白色，如果一个矩阵的所有位置满足以下条件，则称这个矩阵是美丽的：

若 $(i, j)$ 是黑色，且 $(i+1, j)$ 存在，则 $(i+1, j)$ 也是黑色。

若 $(i, j)$ 是黑色，且 $(i+1, j+1)$ 存在，则 $(i+1, j+1)$ 也是黑色。

现在，你可以将任意多个白色染成黑色，求出能将图变成美丽的染色方案数（mod 998244353）。

数据范围：$1≤N,M≤2000$

借鉴了这个题解的做法。

对于一个黑色方块，会限制这个方块右下的斜线(也包括斜线以下的位置)都涂成黑色，而有些位置是受其他黑色影响必须涂成黑色，有的位置是自己手动涂黑的(可选)。

考虑从左往右涂，每一列只需要考虑最高（注：行号越小越高，即第0行最高）的黑色方块的位置，因为最高的黑色方块下方的方块是被强制涂黑的。假设第c-1列最高的黑色方块位置是r，则（在不考虑初始的黑色方块的情况下）可以将第c列的最高黑色方块定在0到r+1。

于是有 $dp[c][r]$ ：前 $c$ 列已经涂完，且第 $c$ 列最高的黑色方块高度是 $r$ 的方案数。

考虑 $dp[c][r]$ 可以从哪些状态转移过来，若 $i+1 < r $，此时 $dp[c-1][i]$ 是不能转移到 $dp[c][r]$ 的，因为 $(c-1, i)$ 是黑色，所以 $(c, i+1)$ 会被强制涂成黑色，这与状态的定义不符。若 $i + 1 ≥ r$ ，此时的 $dp[c-1][i]$ 可以转移到 $dp[c][r]$ ，因为可以手动在第 $c$ 列涂色使得最高的黑色方块高度是 $r$

因此转移为 $dp[c][r] = \sum\limits_{i=r-1}^{n}dp[c-1][i]$，其中 $i = n$ 表示第 $c-1$ 列全是白色的情况。

当然，上面的这个转移是 $O(n)$ 的，我们可以弄个前缀和，从下往上枚举，就能在 $O(1)$ 的时间转移了，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int mod = 998244353;
const int maxn = 2010;
int n, m;
char g[maxn][maxn];
int dp[maxn][maxn], h[maxn];


int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        scanf("%s", g[i]);
    for(int j = 0; j < m; j++)
    {
        h[j] = n;
        for(int i = 0; i < n; i++)
            if(g[i][j] == '#')
            {
                h[j] = i;
                g[i+1][j+1] = '#';
                break;
            }
    }
    for(int i = h[0]; ~i; i--)
        dp[0][i] = dp[0][i+1] + 1;
    for(int c = 1; c < m; c++)
        for(int r = h[c]; ~r; r--)
            dp[c][r] = (dp[c][r+1] + dp[c-1][max(0, r-1)]) % mod;
    cout << dp[m-1][0] << endl;
    return 0;
}

当然，也可以极致优化空间...

#include <iostream>
#include <vector>

const int mod = 998244353;
int n, m;

using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m;
    vector<int> dp(n+2), h(m, n);
    string s;
    for(int i = 0; i < n; i++)
    {
        cin >> s;
        for(int j = 0; j < m; j++)
            if(s[j] == '#')
                h[j] = min(h[j], i);
    }
    for(int i = h[0]; ~i; i--)
        dp[i] = dp[i+1] + 1;
    for(int c = 1; c < m; c++)
    {
        for(int r = n; r > h[c]; r--)
            dp[r] = 0;
        for(int r = h[c]; ~r; r--)
            dp[r] = (dp[r+1] + dp[max(0, r-1)]) % mod;
    }
    cout << dp[0] << endl;
    return 0;
}

G - One More Grid Task ¶

给定一个 $N \times M$ 的矩阵 $A$ ，$A$ 的每个位置有一个正整数。用 $R$ 表示 $A$ 的子矩阵，$sum(R)$ 表示子矩阵所有数字之和，$min(R)$ 表示子矩阵中最小的数字。定义 $f(R) = sum(R) \times min(R)$，对于 $A$ 的所有子矩阵，求出最大的 $f(R)$。

数据范围：$1≤N,M,A_{i,j}≤300$

首先固定子矩阵的左右两边 $l$ 和 $r$ ，然后用 $O(n)$ 时间处理出两个数组：

$c_{l,r}[i] = min(a[i][l],\ a[i][l+1]\ ...\ a[i][r])$

$d_{l,r}[i] = a[i][l]+a[i][l+1] +\ ...\ + a[i][r]$

接下来问题转化为：给定两个数组 $c$ 和 $d$ 求出 $(x, y)$ 使得 $f(x, y) = min(c[x]...c[y]) \times (d[x]+\ ...\ + d[y])$ 最大

先将 $d$ 处理成前缀和形式，然后枚举每个 $c[i]=min(c[x]...c[y])$ 的情况，由于 $d$ 中的值非负，在最小值不变的情况下肯定越大越好，因此 $c[i]=min(c[x]...c[y])$ 说明 $c[i] > c[x-1]$ 且 $c[i] > c[y+1]$，这就转化成找出 $c$ 中每个元素的上一个、下一个比他小的元素问题，可以用单调栈在 $O(n)$ 的时间解决。总时间复杂度 $O(n^3)$

#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

typedef long long LL;
const int maxn = 310;
int n, m, a[maxn][maxn], c[maxn], um[maxn], d[maxn];
LL ds[maxn];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    LL ans = 0;
    for(int l = 1; l <= m; l++)
    {
        for(int i = 1; i <= n; i++)
            c[i] = 500, d[i] = 0;
        for(int r = l; r <= m; r++)
        {
            for(int i = 1; i <= n; i++)
                c[i] = min(c[i], a[i][r]), d[i] += a[i][r];
            for(int i = 1; i <= n; i++)
                ds[i] = ds[i-1] + d[i];
            stack<int> st;
            for(int i = n; i; i--)
            {
                while(!st.empty() && c[i] < c[st.top()])
                    um[st.top()] = i, st.pop();
                st.push(i);
            }
            while(!st.empty())
                um[st.top()] = 0, st.pop();
            for(int i = n; i; i--)
            {
                while(!st.empty() && c[st.top()] >= c[i])
                    st.pop();
                int dm = st.empty() ? n : st.top() - 1;
                ans = max(ans, (ds[dm]-ds[um[i]]) * c[i]);
                st.push(i);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

最后更新: 2023-08-18
创建日期: 2023-08-17

ABC311(A-G)

A - First ABC¶

B - Vacation Together¶

C - Find it!¶

D - Grid Ice Floor¶

E - Defect-free Squares¶

F - Yet Another Grid Task¶

G - One More Grid Task¶