比赛链接如下：

AtCoder Beginner Contest 420 - AtCoder

A - What month is it?

Problem Statement
You are given integers X and Y between 1 and 12, inclusive.

Find what month it will be Y months after month X (for example, month 1 is January).

Constraints
X and Y are integers between 1 and 12, inclusive.

解题思路：x月份的y个月后是几月

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){int x,y;cin>>x>>y;if((x+y)%12==0) { cout<<12<<'\n'; return; }cout<<(x+y)%12<<'\n';
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

B - Most Minority

Problem Statement
People 1,2,…,N (where N is odd) conducted M votes where each person chooses either 0 or 1.
Each person's vote for each round is given as N strings S1​,S2​,…,SN​ of length M consisting of 0 and 1, where the j-th character of Si​ represents person i's vote content for the j-th vote.

In each vote, people who were in the minority receive 1 point.
More precisely, points are given according to the following rules:

Suppose x people chose 0 and y people chose 1 in that vote.
If x=0 or y=0, everyone receives 1 point for that vote.
Otherwise, if x<y, only people who voted 0 in that vote receive 1 point.
Otherwise, only people who voted 1 in that vote receive 1 point.
Note that since N is odd, x=y never occurs.
After finishing M votes, find all people who have the highest total score from those votes.

Constraints
N is an odd number satisfying 1≤N≤99.
M is an integer satisfying 1≤M≤100.
Si​ is a string of length M consisting of 0 and 1.

解题思路：对每一轮投票（每列）统计 0 和 1 的数量；若某一方为 0 或 N（即全票同意），则全体加 1；否则少数一方的对应选手加 1。最后找出得分最高者并按编号）升序输出

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){int n,m;cin>>n>>m;vector<string> s(n);for(int i=0;i<n;i++) cin>>s[i];vector<int> sc(n,0);for(int j=0;j<m;j++){int cnt_0=0;for(int i=0;i<n;i++){if(s[i][j]=='0') cnt_0++;}int cnt_1=n-cnt_0;if(cnt_0==0||cnt_1==0){for(int i=0;i<n;i++) sc[i]++;}else if(cnt_0<cnt_1){for(int i=0;i<n;i++){if(s[i][j]=='0') sc[i]++;}}else{for(int i=0;i<n;i++){if(s[i][j]=='1') sc[i]++;}}}int mx=*max_element(sc.begin(),sc.end());bool f=true;for (int i=0;i<n;i++) {if (sc[i]==mx) {if (!f) cout<<' ';cout<<(i+1);f=false;}}cout<<'\n';
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

C - Sum of Min Query

Problem Statement
You are given length-N integer sequences: A=(A1​,A2​,…,AN​) and B=(B1​,B2​,…,BN​).

You are given Q queries to process in order. The i-th query (1≤i≤Q) is described as follows:

You are given a character ci​ and integers Xi​,Vi​. If ci​= A, change AXi​​ to Vi​; if ci​= B, change BXi​​ to Vi​. Then, output k=1∑N​min(Ak​,Bk​).

Constraints
1≤N,Q≤2×105
1≤Ai​,Bi​≤109
ci​ is either A or B.
1≤Xi​≤N
1≤Vi​≤109
All input values are integers.

解题思路：

维护数组 A,B 和当前答案 ans = Σ min(A[i],B[i])。每次修改某一位置前先从 ans 中减去该位置的旧贡献 min(A[x],B[x])，应用修改后再把新的贡献加回去，然后输出 ans。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){int n,q;cin>>n>>q;vector<ll> a(n+1),b(n+1);for(int i=0;i<=n;i++) cin>>a[i];for(int i=0;i<=n;i++) cin>>b[i];ll ans=0;for(int i=1;i<=n;i++) ans+=min(a[i],b[i]);for(int i=0;i<q;i++){char c; int x;ll v;cin>>c>>x>>v;ans-=min(a[x],b[x]);if(c=='A') a[x]=v;else b[x]=v;ans+=min(a[x],b[x]);cout<<ans<<'\n';}
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

D - Toggle Maze

Problem Statement
There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. The state of each cell is represented by a character Ai,j​, with the following meanings:

. : Empty cell.
# : Obstacle cell.
S : Start cell.
G : Goal cell.
o : Open door cell.
x : Closed door cell.
? : Switch cell.
Takahashi can move from his current cell to an adjacent cell (up, down, left, right) that is neither an obstacle cell nor a closed door cell in one operation.

Also, every time he moves to a switch cell, all open door cells become closed door cells, and all closed door cells become open door cells.

Determine whether he can move from the initial state of being at the start cell to being at the goal cell, and if possible, find the minimum number of operations required.

Constraints
1≤H,W≤500
H and W are integers.
Each Ai,j​ is one of ., #, S, G, o, x, ?.
S and G each appear exactly once in Ai,j​.

解题思路：

把每个格子分成两层 —— parity = 0 表示门为初始状态（o 开，x 关），parity = 1 表示门翻转后（o 关，x 开）。在 BFS 中把状态扩展为 (i,j,parity)，当走到 ? 时 parity 翻转。对移动前检查目标格子在当前 parity 下是否为可通行（不是 # 且不是当前为关闭状态的门）。最后取两层到达目标的最小步数（不可达输出 -1）。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){int H, W;cin >> H >> W;vector<string> a(H);for (int i = 0; i < H; ++i) cin >> a[i];int si=-1, sj=-1, gi=-1, gj=-1;for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j){if (a[i][j] == 'S') { si = i; sj = j; }if (a[i][j] == 'G') { gi = i; gj = j; }}const int INF = 1e9;vector<vector<vector<int>>> dist(2, vector<vector<int>>(H, vector<int>(W, -1)));queue<tuple<int,int,int>> q;dist[0][si][sj] = 0;q.emplace(si, sj, 0);int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};while (!q.empty()) {auto [i,j,p] = q.front(); q.pop();int d = dist[p][i][j];for (int k = 0; k < 4; ++k) {int ni = i + dx[k];int nj = j + dy[k];if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;char ch = a[ni][nj];if (ch == '#') continue;if (ch == 'o') {if (p != 0) continue; } else if (ch == 'x') {if (p != 1) continue; }int np = p ^ (ch == '?'); if (dist[np][ni][nj] == -1) {dist[np][ni][nj] = d + 1;q.emplace(ni, nj, np);}}}int ans = INF;if (dist[0][gi][gj] != -1) ans = min(ans, dist[0][gi][gj]);if (dist[1][gi][gj] != -1) ans = min(ans, dist[1][gi][gj]);if (ans == INF) cout << -1 << '\n';else cout << ans << '\n';
}int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

E - Reachability Query

Problem Statement
You are given an undirected graph with N vertices and zero edges.
The vertices are numbered 1,2,…,N, and initially all vertices are white.
Process a total of Q queries of the following three types:

Type 1 : Add an undirected edge connecting vertices u and v.
Type 2 : If vertex v is white, change it to black; if it is black, change it to white.
Type 3 : Determine whether a black vertex can be reached from vertex v by traversing zero or more edges; report Yes if reachable, and No otherwise.
Constraints
All input values are integers.
1≤N≤2×105
1≤Q≤6×105
Type 1 queries satisfy the following constraints:
1≤u<v≤N
For each query, no edge connecting u and v has been added before that query.
Type 2,3 queries satisfy the following constraints:
1≤v≤N

解题思路：

使用并查集（DSU）维护联通分量，每个根节点记录该分量中黑色点的数量 black[root]。加入边时合并并把黑色计数相加；翻转颜色时更新所属分量的黑色计数；查询时只看当前结点所在分量的黑色计数是否大于 0。所有操作摊销近似 O(α(N))，可满足题目约束

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {int n;vector<int> p, sz;vector<int> black; DSU(int n=0): n(n), p(n+1), sz(n+1,1), black(n+1,0) {for (int i=1;i<=n;i++) p[i]=i;}int find(int x){if (p[x]==x) return x;return p[x]=find(p[x]);}void unite(int a,int b){a = find(a); b = find(b);if (a==b) return;if (sz[a] < sz[b]) swap(a,b);p[b]=a;sz[a]+=sz[b];black[a]+=black[b];}void add_black(int x, int delta){int r = find(x);black[r] += delta;}int get_black(int x){int r = find(x);return black[r];}
};
void solve(){int N, Q;cin >> N >> Q;DSU dsu(N);vector<char> is_black(N+1, 0); for (int qi = 0; qi < Q; ++qi) {int type;cin >> type;if (type == 1) {int u, v;cin >> u >> v;dsu.unite(u, v);} else if (type == 2) {int v;cin >> v;if (!is_black[v]) {is_black[v] = 1;dsu.add_black(v, 1);} else {is_black[v] = 0;dsu.add_black(v, -1);}} else if (type == 3) {int v;cin >> v;if (dsu.get_black(v) > 0) cout << "Yes\n";else cout << "No\n";}}
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

F - kirinuki 

Problem Statement
You are given an N×M grid. Each cell contains either . or #.
The information about the symbols written in the cells is given as N strings S1​,S2​,…,SN​, where the same symbol as the j-th character of Si​ is written in the cell at the i-th row from the top and j-th column from the left.
How many rectangular regions consisting of at most K cells have all cells containing .?

Formally, count the number of integer tuples (lx​,rx​,ly​,ry​) that satisfy the following conditions:

1≤lx​≤rx​≤N
1≤ly​≤ry​≤M
(rx​−lx​+1)×(ry​−ly​+1)≤K
For all integer pairs (i,j) satisfying lx​≤i≤rx​ and ly​≤j≤ry​, the cell at the i-th row from the top and j-th column from the left contains ..
Constraints
N, M, and K are integers.
1≤N,M≤5×105
1≤N×M≤5×106
1≤K≤N×M
Si​ is a string of length M consisting of . and #.

解题思路：不会

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<random>
#include<cassert>
using namespace std;
int N,M,K;
string S[5<<17];
const int L=2237;
int up[L];
int H[L];
int can[L];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);{cin>>N>>M>>K;for(int i=0;i<N;i++)cin>>S[i];}if(N<M){for(int i=N;i<M;i++)S[i].resize(N);for(int i=0;i<N;i++)for(int j=i+1;j<M;j++)swap(S[i][j],S[j][i]);for(int i=0;i<N;i++)S[i].resize(N);swap(N,M);}for(int l=1;l<=M;l++)can[l]=K/l;long ans=0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(S[i][j]=='#')up[j]=0;else up[j]++;const int x=up[j];for(int k=0;k<j;k++)H[k]=min(H[k],x);H[j]=x;for(int k=0;k<=j;k++)ans+=min(H[k],can[j-k+1]);}}cout<<ans<<endl;
}

G - sqrt(n²+n+X)

Problem Statement
You are given an integer X.

Find all integers n such that n2+n+X​ is an integer.

Constraints
−1014≤X≤1014
The input value is an integer.

解题思路：

要求找到所有整数 n 使得 n2+n+X 为完全平方数），可以通过因式分解把问题转成对整数因子对的枚举：

令存在整数 m 使得 n2+n+X=m^2。整理得

(2n+1−2m)(2n+1+2m)=1−4X, 设 A=2n+1−2m,  B=2n+1+2m，则 A⋅B=D:=1−4X。枚举所有使得 A⋅B=D 的整数组合（包含负因子），通过 n=(A+B−2)/4 恢复 n，并检查整除条件即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {ll X;cin >> X;ll D = 1 - 4 * X;ll absD = D >= 0 ? D : -D;vector<ll> ans;for (ll d = 1; d * d <= absD; ++d) {if (absD % d != 0) continue;ll d2 = absD / d;for (int sign = -1; sign <= 1; sign += 2) {ll A = d * sign;ll B = D / A; auto mod4 = [&](ll x) -> int {int r = (int)(x % 4);if (r < 0) r += 4;return r;};if (mod4(A + B - 2) == 0 && mod4(B - A) == 0) {ll n = (A + B - 2) / 4;ans.push_back(n);}if (d != d2) {ll A2 = d2 * sign;ll B2 = D / A2;if (mod4(A2 + B2 - 2) == 0 && mod4(B2 - A2) == 0) {ll n2 = (A2 + B2 - 2) / 4;ans.push_back(n2);}}}}sort(ans.begin(), ans.end());ans.erase(unique(ans.begin(), ans.end()), ans.end());cout << ans.size() << '\n';for (int i = 0; i < ans.size(); ++i) {if (i) cout << ' ';cout << ans[i];}cout << '\n';
}
int main() {int t = 1;// cin >> t;while (t--) {solve();}return 0;
}

感谢大家的点赞和关注，你们的支持是我创作的动力！