比赛地址：Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） - AtCoder
后记：大家都太强了%%%，如果我做不出第四题就要掉分了。。。
A - First ABC
找到第一个 \(\texttt{A, B, C}\) 三种字符都出现的位置。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 110;
int n, fga, fgb, fgc;
char s[N];
int main() {
n = read<int>();
scanf("%s", s + 1);
for (int i = 1; i <= n; ++ i) {
if (s[i] == 'A') fga = 1;
if (s[i] == 'B') fgb = 1;
if (s[i] == 'C') fgc = 1;
if (fga && fgb && fgc) {
cout << i << '\n';
break ;
}
}
return 0;
}
B - Vacation Together
B - Vacation Together (atcoder.jp)
找到最长的连续的区间，使得区间里全为 \(\texttt{o}\)。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 110;
int n, d, ans, mx;
char s[N][N];
int main() {
n = read<int>(), d = read<int>();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s[i] + 1);
}
for (int i = 1; i <= d; ++ i) {
int fg = 1;
for (int j = 1; j <= n; ++ j) {
if (s[j][i] == 'x') {
fg = 0;
break ;
}
}
if (fg == 0) {
mx = max(mx, ans);
ans = 0;
}
ans += fg;
}
cout << max(mx, ans) << '\n';
return 0;
}
C - Find it!
一个找环问题，拓扑排序 + dfs 即可。
这个蒟蒻因为忘记统计入度而罚了两罚。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2e5 + 5;
int n;
int in[N];
vector<int> e[N], ans;
queue<int> q;
bitset<N> vis;
void print() {
cout << ans.size() << '\n';
for (int v : ans) {
cout << v << ' ';
}
}
void dfs(int u) {
if (vis[u]) {
print();
exit(0);
}
ans.emplace_back(u);
vis.set(u);
for (int v : e[u]) {
dfs(v);
}
ans.pop_back();
vis.reset(u);
}
int main() {
n = read<int>();
for (int i = 1, x; i <= n; ++ i) {
e[i].emplace_back(x = read<int>());
++ in[x]; // 就是这里！
}
for (int i = 1; i <= n; ++ i) {
if (!in[i]) {
q.emplace(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : e[u]) {
-- in[v];
if (!in[v]) {
q.emplace(v);
}
}
}
for (int i = 1; i <= n; ++ i) {
if (in[i]) {
dfs(i);
break ;
}
}
return 0;
}
D - Grid Ice Floor
D - Grid Ice Floor (atcoder.jp)
一道考验搜索能力的题，我用的广搜，存储下每个节点的方向，防止重复。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 210;
const int dx[5] = {0, 0, 1, 0, -1};
const int dy[5] = {0, 1, 0, -1, 0};
int n, m;
char s[N][N];
bool vis[N][N][5], ok[N][N];
struct node {
int x, y, dir;
};
void bfs() {
queue<node> q;
q.push(node{2, 2, 0});
while (!q.empty()) {
node fr = q.front();
q.pop();
int x = fr.x, y = fr.y, dir = fr.dir;
if (vis[x][y][dir]) continue ;
ok[x][y] = 1;
vis[x][y][dir] = 1;
if (dir == 0) {
for (int i = 1; i <= 4; ++ i) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 1 && yy >= 1 && xx <= n && yy <= m && s[xx][yy] == '.') {
q.push(node{xx, yy, i});
}
}
continue ;
}
if (x + dx[dir] >= 1 && y + dy[dir] >= 1 && x + dx[dir] <= n && y + dy[dir] <= m) {
if (s[x + dx[dir]][y + dy[dir]] == '.') {
q.push(node{x + dx[dir], y + dy[dir], dir});
}
else {
q.push(node{x, y, 0});
}
}
}
}
int main() {
n = read<int>(), m = read<int>();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s[i] + 1);
}
bfs();
int ans = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (ok[i][j]) {
++ ans;
}
}
}
cout << ans << '\n';
return 0;
}
E - Defect-free Squares
E - Defect-free Squares (atcoder.jp)
用 DP 来解决问题。
设 \(dp\left( i, j\right)\) 代表右下角为 \(\left( i, j \right)\) 的无孔正方形的最大边 \(n\)，如果不存在这样的正方形，则为 \(0\)。
设答案为 \(ans\)，则
\[ans = \sum_{i = 1}^{h} \sum_{j = 1}^{w} dp \left( i, j \right)
\]
证明，如果 \(dp \left(i, j \right) = k\)，那么一定存在右下角为 \(\left(i, j \right)\) 的长度为 \(1, 2 \dots k\) 的正方形是无孔正方形。
递推式：
\[dp \left(i, j \right ) =
\begin{cases}
\min \{dp(i - 1, j), dp(i,j - 1), dp(i - 1, j - 1) \} + 1 & s(i, j) = \texttt{o}\\
0 & s(i, j) = \texttt{x}
\end{cases}
\]
小小的说明：
大小为 \(n\) 的正方形区域，其右下角正方形为 \((i，j)\)，是无孔的。
大小为 \((n−1)\) 的正方形区域，其右下角为 \((i，j−1)\)，是无孔的。
大小为 \((n−1)\) 的正方形区域，其右下角为 \((i−1，j)\)，是无孔的。
大小为 \((n−1)\) 的正方形区域，其右下角为 \((i−1，j)\)，是无孔的。
\((i，j)\)没有孔。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 3010;
int h, w, n;
ll dp[N][N];
bool hole[N][N];
int main() {
h = read<int>(), w = read<int>(), n = read<int>();
for (int i = 1, a, b; i <= n; ++ i) {
a = read<int>(), b = read<int>();
hole[a][b] = 1;
}
ll ans = 0;
for (int i = 1; i <= h; ++ i) {
for (int j = 1; j <= w; ++ j) {
if (hole[i][j]) continue ;
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
ans += dp[i][j];
}
}
cout << ans << '\n';
return 0;
}
还有一位大佬的暴力写法也过了，纯暴力是 \(n^3\) 的，这位大佬优化了枚举边的复杂度，使得他的代码跑过去了，下面展示一下。
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"
using namespace std;
//constexpr long long int MOD = 1000000007;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;
//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> H >> W;
vector<vector<int>>sum(H + 1, vector<int>(W + 1));
cin >> N;
for (int i = 0; i < N; i++) {
int y, x;
cin >> y >> x;
sum[y][x]++;
}
for (int i = 0; i <= H; i++) {
for (int j = 1; j <= W; j++) {
sum[i][j] += sum[i][j - 1];
}
}
for (int i = 1; i <= H; i++) {
for (int j = 0; j <= W; j++) {
sum[i][j] += sum[i - 1][j];
}
}
long long ans = 0;
for (int i = 0; i < H; i++) {
int bef = 0;
for (int j = 0; j < W; j++) {
int ok = bef - 1;
for (int k = max(0, bef - 1); i + k <= H && j + k <= W; k++) {
int num = sum[i + k][j + k] - sum[i][j + k] - sum[i + k][j] + sum[i][j];
if (num == 0) {
ok = k;
} else {
break;
}
}
ans += ok;
bef = ok;
}
}
cout << ans << endl;
}
F - Yet Another Grid Task
F - Yet Another Grid Task (atcoder.jp)
一个 \(n \times m\) 的网格，每个格子是黑色的或白色的，一个网格被认为是漂亮的，当且仅当 \((i, j)\) 为黑色时，\((i + 1, j)\) 和 \((i + 1, j + 1)\) 也是黑色的，问有多少种方法使得这个网格变成漂亮的（可以把白色染成黑色），对方案数模上 \(998244353\)。
实在是看不懂了，尽我所能了，下面是一份 AC 代码，但不是我写的，也不是题解的做法，有理解的可以在评论区评论。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2010;
const int mod = 998244353;
int n, m;
int h[N];
ll g[N][N], f[N][N];
char s[N][N];
int main() {
n = read<int>(), m = read<int>();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s[i] + 1);
}
for (int j = 1; j <= m; ++ j) {
h[j] = n + 1;
for (int i = 1; i <= n; ++ i) {
if (s[i][j] == '#') {
h[j] = i;
break ;
}
}
}
f[0][n + 1] = 1;
for (int i = 0; i <= n + 1; ++ i) {
g[0][i] = 1;
}
for (int i = 1; i <= m; ++ i) {
for (int j = 1; j <= h[i]; ++ j) {
f[i][j] = g[i - 1][j - 1];
}
for (int j = n + 1; ~j; -- j) {
g[i][j] = (g[i][j + 1] + f[i][j]) % mod;
}
}
cout << g[m][1] << '\n';
return 0;
}
- Contest Programming Beginner AtCoder 报告contest programming beginner atcoder beginner atcoder contest报告 contest programming securities beginner contest programming beginner registry contest programming christmas beginner contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde