A - First ABC
题意
给一个长度为N的仅由ABC三个字符组成的字符串S，问S中ABC三个字符第一次出现的位置的最大值。
题解
使用map<char,bool>判重，记录当前不同的字符串的个数cnt，当cnt等于3时，输出此时的下标+1作为答案。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lowbit(x) ((x) & -(x))
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1 ) | 1)
#define SZ(x) (int)(x.size())
#define FOR(i,x,y) for (int i = (x),_##i = (y);i < _##i;i++)
#define FORD(i,x,y) for (int i = (x),_##i = (y);i > _##i;i--)
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int t = 1;
string s;
int n;
cin >> n;
cin >> s;
map<char,bool> mp;
int cnt = 0;
FOR (i, 0, SZ(s)) {
if (!mp[s[i]]) {
cnt++;
mp[s[i]] =1;
}
if (cnt == 3) {
cout << i +1 << "\n";
return 0;
}
}
return 0;
}
B - Vacation Together
题意
给出N个人的接下来D天的日程表，问这D天中，N个人都连续空闲的天数的最大值。
题解
使用cnt记录当前连续空闲的时长,mx记录答案。对于每一天，都判断N个人是否空闲，如果空闲就cnt++，否则就拿现在的天数与mx取最大值，cnt恢复为0.
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lowbit(x) ((x) & -(x))
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1 ) | 1)
#define SZ(x) (int)(x.size())
#define FOR(i,x,y) for (int i = (x),_##i = (y);i < _##i;i++)
#define FORD(i,x,y) for (int i = (x),_##i = (y);i > _##i;i--)
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n, d;
cin >> n>> d;
vector<string> v(n);
FOR (i, 0, n) cin >> v[i];
int cnt = 0, mx = 0;
FOR (i, 0, d) {
bool ok = 1;
FOR (j, 0, n) {
if (v[j][i] == 'x') {
ok = 0;
}
}
if (ok) {
cnt ++;
} else {
mx = max(cnt, mx);
cnt = 0;
}
}
mx = max(mx, cnt);
cout << mx << "\n";
return 0;
}
C - Find it!
题意
给出有N个点N条边的有向图，问图中是否存在有向的环，如果存在多个，任意一个都可作为答案。
题解
使用链式前向星记录有向图，使用第一个dfs找到环中的一个点，由于进了有向环就不会再出这个环（这个是每个点只有一条出边保证的），所以再通过 dfs2遍历这个环即可。
对于如何找到环中的点，我们可以在dfs的过程中记录这个点是否在此次dfs中出现过，如果一个点出现了两次，说明我们进入了一个有向的环，这个出现两次的点一定在环中。
对于如何使用dfs2记录环中的点，类似于dfs，一直记录点是否出现过，边记录边放进数组中，如果一个点出现了两次，说明环已经遍历完了。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lowbit(x) ((x) & -(x))
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
#define SZ(x) (int)(x.size())
#define FOR(i, x, y) for (int i = (x), _##i = (y); i < _##i; i++)
#define FORD(i, x, y) for (int i = (x), _##i = (y); i > _##i; i--)
const int N = 2e5 + 10;
int h[N], nxt[N], to[N], idx;
void addedge(int u, int v) {
to[idx] = v;
nxt[idx] = h[u];
h[u] = idx++;
}
vector<int> ans;
bool mp[N];
bool first = 0;
int dfs(int u) {
if (mp[u]) {
return u;
}
mp[u] = 1;
for (int i = h[u]; ~i; i = nxt[i]) {
int v = to[i];
int t = dfs(v);
if (t) {
return t;
}
}
return 0;
}
void dfs2(int u) {
if (mp[u])
return;
mp[u] = 1;
ans.push_back(u);
for (int i = h[u]; ~i; i = nxt[i]) {
int v = to[i];
dfs2(v);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
memset(h, -1, sizeof h);
cin >> n;
FOR(i, 0, n) {
int t;
cin >> t;
addedge(i + 1, t);
}
FOR(i, 1, n + 1) {
memset(mp, 0, sizeof mp);
int t = dfs(i);
if (t) {
memset(mp, 0, sizeof mp);
dfs2(t);
cout << SZ(ans) << "\n";
FOR(i, 0, SZ(ans)) {
cout << ans[i] << " ";
}
cout << "\n";
return 0;
}
}
return 0;
}
D - Grid Ice Floor
题意
给定一个N*M的图，图中有两种格子.和#，保证最外一层都是#，现在你位于(2,2)（从1开始算），保证(2,2)是.。
现在开始移动，每次可以选择上下左右4个方向中的一个，方向选定后，除非下一个格子是#，否则一直沿着当前方向移动。遇到#后，可以再次移动。
问你最多能走过的多少个.。
题解
方向的编码
0表示上
1表示右
2表示下
3表示左
这样编码的好处就是对于方向op，可以通过op ^ 2来获得与op相反的方向。
使用vis[i][j][4]来记录在(i,j)这个点，上下左右4个方向是否都遍历过。
使用cnt[i][j]来记录(i,j)这个点是否遍历过。
由于是一直走一个方向，考虑记录方向op的dfs。
初始时给(2,2)这个点一个特殊的方向值来表示它是起点。
对于(2,2)这个点，4个方向哪个能走就走哪个方向，比如方向op，则记录vis[2][2][op] = 1;表示这个方向已经走过了。
对于下一个格子是#的情况，首先设当前坐标为(x,y)，当前方向是op，那么记录我们来的这条路已经走过了，即vis[x][y][op ^ 2] = 1;，再以这个点向4个方向扩散。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lowbit(x) ((x) & -(x))
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1 ) | 1)
#define SZ(x) (int)(x.size())
#define FOR(i,x,y) for (int i = (x),_##i = (y);i < _##i;i++)
#define FORD(i,x,y) for (int i = (x),_##i = (y);i > _##i;i--)
const int N = 2e2 + 10;
int ans = 0;
bool vis[N][N][4];
bool cnt[N][N];
int dx[4] = {-1,0,1,0};
int dy[4] = {0, 1, 0, -1};
void dfs(int x,int y,int op, vector<string>& g) {
if (!cnt[x][y]) {
cnt[x][y] = 1;
ans++;
}
if (op != -1) {
int tx = x + dx[op];
int ty = y + dy[op];
if (g[tx][ty] == '#') {
vis[x][y][op ^ 2] = 1;
FOR (i, 0, 4) {
if (!vis[x][y][i]) {
vis[x][y][i] = 1;
int txx = x + dx[i], tyy = y + dy[i];
if (g[txx][tyy] != '#') {
dfs(txx,tyy,i,g);
}
}
}
} else {
dfs(tx,ty,op,g);
return;
}
} else {
FOR (i, 0, 4) {
if (!vis[x][y][i]) {
vis[x][y][i] = 1;
int tx = x + dx[i], ty = y + dy[i];
if (g[tx][ty] != '#') {
dfs(tx,ty,i,g);
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> v(n);
FOR(i, 0, n) cin >> v[i];
dfs(1,1, -1, v);
cout << ans << "\n";
return 0;
}
E - Defect-free Squares
题意
在N*M的区域内，有k个洞。
问在这N*M的区域内，有多少个不同的无洞正方形区域。单独一个不是洞的点也是无洞的正方形区域。
题解
由于要对正方形内的数据进行统计，考虑二维前缀和。
对于一系列无洞正方形的左上角(i,j)，肯定存在一个值len，使得由(i,j)和(i+len,j+len)组成的正方形是一个无洞正方形，而(i,j)和(i+len+1,j+len+1)组成的正方形不是一个无洞正方形，发现具有二分的性质，于是二分寻找以(i,j)为左上角的正方形最大能有多大，并记录到答案中。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lowbit(x) ((x) & -(x))
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1 ) | 1)
#define SZ(x) (int)(x.size())
#define FOR(i,x,y) for (int i = (x),_##i = (y);i < _##i;i++)
#define FORD(i,x,y) for (int i = (x),_##i = (y);i > _##i;i--)
const int N = 2e5 + 10;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> v(n + 1, vector<int> (m + 1, 0));
ll ans = 0;
FOR (i,0,k) {
int a, b;
cin >> a >> b;
v[a][b] ++;
}
FOR (i, 1,n + 1) {
FOR (j, 1,m + 1) {
v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
}
}
FOR (i,1,n+1) {
FOR (j, 1, m + 1) {
int l = 0, r = min(n,m) ;
while (l < r) {
int mid = l + r >> 1;
int ti = i + mid, tj = j + mid;
if (ti > n || tj > m || v[ti][tj] - v[i-1][tj] - v[ti][j - 1] + v[i-1][j-1] > 0) r = mid;
else l = mid + 1;
}
ans += l;
}
}
cout << ans << "\n";
return 0;
}
- 题解 Beginner AtCoder Contest 311beginner atcoder contest 311 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334