A - First ABC
Sol
考虑使用三个 bool 记录当前 A ， B ， C 是否出现过，枚举判断即可。
#include <bits/stdc++.h>
using namespace std;
bool a, b, c;
int n;
string s;
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++) {
if (s[i] == 'A') a = true;
if (s[i] == 'B') b = true;
if (s[i] == 'C') c = true;
if (a and b and c) {
cout << i + 1 << endl;
return 0;
}
}
return 0;
}
B - Vacation Together
Sol
考虑横向枚举，对于每一天记录是否有人没空，记录上一次有人没空是哪天，统计答案时直接相减。
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3+5;
string s[MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> s[i];
int last = -1, ans = 0;
for (int i = 0; i < m; i++) {
bool flag = true;
for (int j = 1; j <= n; j++)
if (s[j][i] == 'x') flag = false;
if (flag) {
ans = max(ans, i - last);
} else {
last = i;
}
}
cout << ans << endl;
return 0;
}
C - Find it!
Sol
正常解法应该是 \(\text{DFS}\)，但是因为本题特殊的输入，所以可以使用指针在数组里面跳来跳去。
跟染色一样，对每一个节点染色，先枚举每一个点，看它有没有被染色，如果没有就进行以下操作：
-
将指针指向这个点。
-
沿着边跳。
-
-
如果跳到了未染色的点，将其染成当前颜色，并放入一个
vector中，重复 2，3 步。 -
如果跳到了与当前染色不同的节点，肯定没希望了，结束这次操作。
-
如果跳到了与当前染色相同的点，
break掉，并开始第 4 步。
-
-
将前面链状的部分拿掉，因为最后的答案可能是一个 \(\rho\) 形，输出答案。
重点在第 4 步，vector 没有 pop_front()，但是我们把它 reverse 一下，pop_back() 后再 reverse 回来不就行了吗。
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int n, a[MAXN], color[MAXN], c;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> ans;
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
c++;
ans.clear();
int p = i;
bool flag = true;
do {
color[p] = c;
ans.push_back(p);
if (color[p] != 0 and color[p] != c) {
flag = false;
break;
}
p = a[p];
} while (color[p] == 0);
reverse(ans.begin(), ans.end());
while (ans.back() != p) ans.pop_back();
reverse(ans.begin(), ans.end());
if (flag) {
cout << ans.size() << endl;
for (int j : ans) cout << j << " ";
cout << endl;
return 0;
}
}
}
return 0;
}
D - Grid Ice Floor
Sol
考虑 \(\text{BFS}\)，每一次状态转移就是从这个点往四个方向延展，中途遇到的格子不能放进队列中，碰到后的那个格子如果没有走过就放进队列中。
代码细节较多，需要注意。
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
queue<pair<int, int>> q;
int vis[MAXN][MAXN];
int n, m;
bool check(int x, int y) {
return 0 <= x and x < n and 0 <= y and y < m;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
string maze[MAXN];
void bfs() {
vis[1][1] = 1;
q.push(make_pair(1, 1));
while (q.size()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int tx = x;
int ty = y;
while (1) {
if (!check(tx + dir[i][0], ty + dir[i][1]) or maze[tx + dir[i][0]][ty + dir[i][1]] == '#') {
if (!vis[tx][ty]) q.push(make_pair(tx, ty));
vis[tx][ty] = 1;
break;
}
vis[tx][ty] = 1;
tx += dir[i][0];
ty += dir[i][1];
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> maze[i];
bfs();
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ans += vis[i][j];
cout << ans << endl;
return 0;
}
E - Defect-free Squares
Sol
考虑 \(\text{DP}\)，设 \(f_{i,j}\) 为以 \((i, j)\) 为右下角的无洞正方形的数量。
此时状态转移方程该怎么写呢？
考虑到对于一个点 \((i,j)\)，对它有贡献的只有 \(3\) 个点：\((i-1,j)\)，\((i-1,j)\)，\((i-1,j)\)。
此时我们发现，如果一个点 \((i, j)\) 为右下角的正方形的边长为 \(l\)，那此时，需满足有以 \((i-1, j)\)，\((i,j-1)\)，\((i-1,j-1)\) 为右下角的正方形的边长至少为 \(l-1\)。
所以转移方程式就出来了。
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
int n, m, k, a[MAXN][MAXN];
long long f[MAXN][MAXN], ans;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
a[x][y] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j]) {
continue;
}
f[i][j] = min({f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]}) + 1;
ans += f[i][j];
}
}
cout << ans << endl;
return 0;
}