代码中的il或i64均表示long long类型。

Problem A. First ABC

题意

给定一个包含大写字母ABC的字符串$S$，长度为$N$，保证ABC在该串中都至少出现过一次，输出第一个保证ABC都至少出现过一次的位置的序号。

题解

既然ABC都至少出现过一次，我们直接查找ABC这几个字母第一次出现的位置，取最大值即可

代码

1
2
3
4
5
6
void solve() {
    int n;
    string s;
    cin >> n >> s;
    cout << std::max({s.find('A'), s.find('B'), s.find('C')}) + 1;
}

Problem B. Vacation Together

题意

有$N$个人，给出他们$D$天的计划表（x表示该天上班，o表示该天休息）。现在求这$N$个人在这$D$天中能够一起休息的最长连续天数。

题解

我们用$v[i]$表示第$i$天是否有人上班。在读入数据时，如果某人在第$i$天上班，直接令$v[i]$加一即可（当然，你也可以使用bool数组做或运算）。然后我们线性地遍历整个数组，找到最长连续0段的长度即可。数组中的每个元素都只会被访问一次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool v[200];
void impl() {
    int n, d;
    cin >> n >> d;
    for (int i = 0;i < n;i++) {
        string s;
        cin >> s;
        for (int j = 0;j < d;j++) {
            v[j] = v[j] || s[j] == 'x';
        }
    }
    int ans = 0;
    for (int i = 0;i < d;i++) {
        if (!v[i]) {
            int l = 0, j = i;
            while (!v[j] && j < d) {
                j ++, l++;
            }
            ans = std::max(ans, l);
            i = j - 1;
        }
    }
    cout << ans;
}

Problem C. Find it!

题意

有一个$N$个点，$N$条边的有向图，没有自环。在图中任意寻找一个有向边组成的环，要求环上的点只在环中出现一次。并且按照有向边的指向输出这个环上的点（鼠鼠就是因为这个wa了一发）。注意图中可能包括不止一个环，图上的点也不一定都连通。

题解

我们考虑在图上的dfs，这样方便我们记录路径。

首先，我们在图上dfs时，会访问这部分图的所有边，如果图中有环，那么我们通过某条未访问的边进行dfs时，必然会到达一个曾经访问过的点$P$。此时我们就停止dfs，不要再访问其他边，一层层返回，并记录到达该节点的路径，当返回到这个点$P$时，就停止记录路径。

注意，我们的路径的记录顺序是和这个有向边的指向相反的，因此在最后输出答案时应该倒序输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
vector<int> to[200100];
int path[200100], vis[200100], sz, target;
void dfs(int p) {
    vis[p] = 1;
    if (sz) {
        return;
    }
    for (auto nxt : to[p]) {
        if (!vis[nxt]) {
            dfs(nxt);
            if (target) {
                if (p == target) {
                    target = 0;
                }
                path[sz++] = p;
            }
        } else {
            // loop!
            target = nxt;
            path[sz++] = p;
            break;
        }
    }
}
void impl() {
    int n, v;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> v;
        to[i].push_back(v);
    }
    for (int i = 1;i <= n && !sz;i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    cout << sz << '\n';
    for (int i = 0;i < sz;i++) {
        cout << path[sz - 1 - i] << ' ';
    }
}

Problem D. Grid Ice Floor

题意

有一个$N\times M$的地图，其中.表示可以通行，#表示墙壁，不能通行。数据保证地图的最外围都是墙壁，且起点为$(2,2)$始终是.。

你可以从起点任意向上下左右移动，但是一旦确定向某个方向移动，就必须一直朝这个方向移动，直到碰到墙壁，才能在无法继续移动的位置选择下一次移动的方向。

现在问，在地图中你可以访问到的点共有几个？

题解

考虑到$N,M\le 200$，我们可以直接bfs通过本题。直接从起点开始四个方向查找下一个停止的位置，然后继续扩展即可，每个点只需扩展至多一次，复杂度不超过$O(NM(N+M))$

首先将起点$(2,2)$入队，并设$avail[2][2]=1,vis[2][2]=1$，然后不断从队列中取出点，做如下操作：

  • 分别朝四个方向扩展，直到遇到墙壁，将沿途的点$(i,j)$的$avail[i][j]$设为$1$
  • 如果碰壁的点$(i,j)$尚未放入过扩展队列（$vis[i][j]=0$），则将其放入，并令$vis[i][j]=1$

最后，统计出$\sum\limits_{i=1}^N\sum\limits_{j=1}^Mavail[i][j]$的值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int shifts[][2] =  {
        0, 1, 1, 0, 0, -1, -1, 0
};
char mp[300][300];
bool u[300][300];
int st[210][210];
struct Inf {
    int x, y;
};
void impl() {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        scanf("%s", mp[i] + 1);
    }
    std::queue<Inf> q;
    u[2][2] = 1;
    st[2][2] = 1;
    q.push({2, 2});
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        for (auto & shift : shifts) {
            int x = node.x + shift[0], y = node.y + shift[1], vx = -1, vy = -1;
            while (1 <= x && 1 <= y && x <= n && y <= m) {
                if (mp[x][y] == '.') {
                    vx = x;
                    vy = y;
                    u[x][y] = true;
                } else {
                    break;
                }
                x += shift[0], y += shift[1];
            }
            if (vx != -1 && vy != -1 && !st[vx][vy]) {
                q.push({vx, vy});
                st[vx][vy] = 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            ans += u[i][j];
        }
    }
    cout << ans;
}

Problem E. Defect-free Squares

题意

有一个$H\times W$的卡片，上面有$N$个格子被挖空了。

现在你需要求出在卡片上这样的正方形的个数：

  • 这个正方形内覆盖的区域没有小洞
  • 正方形的边长大于等于1

两个正方形被视作不同，当且仅当它们左上角位置和边长至少有一个不同。

题解

我们要求出整个卡片上的正方形数目，就需要能够迅速转移状态的方式，而且是从先前的状态转移到之后的状态。首先，确定一个正方形的方式是正方形的一个角加上正方形的大小。如果我们定以某个格点为正方形的某一角（注意是确定的一个角，我们下面的所有讨论都是针对这一个角来说的），那么这个格点上确定的合法正方形数就是以这个格点为某一角的最大边长。如果该格点上是洞，那么不可能有以该格点为某一角的合法正方形。否则，我们考虑如何从它紧挨的格点转移到当前格点。为了方便转移，也符合一般编写程序的习惯，我们选取正方形的右下角。

如果在这个格点$(i,j)$的合法正方形的边长可以是$k$，那么说明以$(i-k+1,j-k+1)$为左上角，$(i,j)$为右下角的正方形区域内都是没有洞的，从此就可以推出，$(i-1,j)$，$(i-1,j-1)$，$(i,j-1)$这几个格点处的合法正方形的边长至少为$k-1$，并且一定是同时满足。这一点可以画图证明 ，这三个条件同时满足，就可以保证$(i-k+1,j-k+1)$为左上角，$(i,j)$为右下角的正方形区域内（除去点$(i,j)$）没有洞。

由此可以得到状态转移方程：
$$
dp[i][j]=\left\{\begin{array}{}
min\{dp[i-1][j],dp[i-1][j-1],dp[i],[j-1]\}+1 & (hole[i][j]=0) \\
0 & (hole[i][j]= 1)
\end{array}\right.
$$
时间复杂度$O(HW+N)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool x[3100][3100];
int dp[3100][3100];
void solve() {
    int h, w, n, a, b;
    cin >> h >> w >> n;
    while (n--) {
        cin >> a >> b;
        x[a][b] = true;
    }
    il ans = 0;
    for (int i = 1;i <= h;i++) {
        for (int j = 1; j <= w; j++) {
            if (!x[i][j])
                dp[i][j] = std::min({dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]}) + 1;
            ans += dp[i][j];
        }
    }
    cout << ans;
}