AtCoder Beginner Contest 413

比賽鏈接如下：Denso Create Programming Contest 2025（AtCoder Beginner Contest 413） - AtCoder?

A - Content Too Large

Problem Statement
Takahashi has?N?items and one bag.

The size of the?i-th (1≤i≤N)?item is?Ai?, and the size of the bag is?M.

If and only if the total size of the items he is trying to put in the bag is at most?M, he can put all those items in the bag simultaneously.

If he can put all?N?items in the bag simultaneously, print?Yes; otherwise, print?No.

解題思路：

一次性將N件物品裝入大小為M的包中, 能裝進去, 輸出Yes, 否則, 輸出No

#include <bits/stdc++.h>
using namespace std;
void solve() {int n,m;cin>>n>>m;vector<int> a(n);int sum_a=0;for(int i=0;i<n;i++){cin>>a[i];sum_a+=a[i];}if(sum_a<=m){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
}
int main() {int t=1;// cin >> t;while (t--) {solve();}return 0;
}

?B - cat 2

Problem Statement
You are given?N?types of strings S1?,S2?,…,SN?.

You perform the following operation once:

Choose?distinct?integers?i?and?j?(1≤i≤N,1≤j≤N) and concatenate?Si??and Sj??in this order.
How many different strings can be obtained as a result of this operation?

If different choices of?(i,j)?result in the same concatenated string, it is counted as one string.

解題思路：

將兩個下標不同的字符串進行合并, 然后存入到一個set中, 輸出set的長度即可?

#include <bits/stdc++.h>
using namespace std;
void solve() {int n;cin >> n;vector<string> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}set<string> st;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j)continue;st.insert(a[i] + a[j]);}}cout << st.size() << '\n';
}
int main() {int t = 1;// cin >> t;while (t--) {solve();}return 0;
}

?C - Large Queue

Problem Statement
There is an empty integer sequence?A=(). You are given?Q?queries, and you need to process them in the given order. There are two types of queries:

Type?1: Given in the format?1 c x. Add?c?copies of?x?to the end of?A.
Type?2: Given in the format?2 k. Remove the first?k?elements from?A?and output the sum of the removed?k?integers. It is guaranteed that?k?is at most the length of?A?at that time.

解題思路：

兩種操作, 一種是在A的尾部添加c個x, 另一種是移除A的前k個元素, k的值不能超過A的長度, 同時輸出這個k個元素的總和，使用deque維護這個數組A, 然后t=1/2進行操作即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
void solve() {int q;cin >> q;deque<pll> dp;while (q--) {int t;cin >> t;if (t == 1) {ll c, x;cin >> c >> x;dp.emplace_back(c, x);} else {ll k;cin >> k;ll sum = 0;while (k > 0 && !dp.empty()) {auto& a = dp.front();ll c = a.first;  ll x = a.second;  if (c <= k) {sum += c * x;k -= c;dp.pop_front();} else {sum += k * x;a.first -= k;k = 0;}}cout << sum << "\n";}}
}
int main() {int t=1;// cin>>t;while(t--){solve();}return 0;
}

?D - Make Geometric Sequence

Problem Statement
You are given an integer sequence?A=(A1?,A2?,…,AN?)?of length?N. It is guaranteed that for any?i?(1≤i≤N),?Ai??is not?0.

Determine whether there exists a permutation?B=(B1?,B2?,…,BN?)?of?A?such that?B?forms a geometric sequence.

A sequence?S=(S1?,S2?,…,SN?)?is a geometric sequence if there exists a real number?r?such that?Si+1?=rSi??for all integers?1≤i<N.

Solve?T?test cases per input file.

解題思路：

判斷數組A的某個排列能否構成等比數列

1. 數組長度<=2的數列是等比數列

2. 數組元素相等, 公比q=1

3. 公比q正負交替的情況（互為相反數）

=> 只有兩個值，且互為相反數，數量差不大于1

4. 一般情況通過 b[i]^2 = b[i-1]*b[i+1]進行判斷

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
void solve() {int n;cin >> n;vector<ll> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}if (n <= 2) {cout << "Yes" << '\n';return;}bool f = true;for (int i = 1; i < n; i++) {if (a[i] != a[0]) {f = false;break;}}if (f) {cout << "Yes" << '\n';return;}set<ll> v(a.begin(), a.end());if (v.size() == 2) {auto it = v.begin();ll v1 = *it;it++;ll v2 = *it;if (v1 + v2 == 0) {ll c1 = 0, c2 = 0;for (ll x : a) {if (x == v1)c1++;elsec2++;}if (abs(c1 - c2) <= 1) {cout << "Yes" << '\n';return;}}}sort(a.begin(), a.end(), [](ll x, ll y) { return llabs(x) < llabs(y); });bool f_1 = true;for (int i = 1; i + 1 < n; i++) {ll x = (ll)a[i] * a[i];ll y = (ll)a[i - 1] * a[i + 1];if (x != y) {f_1 = false;break;}}if (f_1)cout << "Yes" << '\n';elsecout << "No" << '\n';
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?E - Reverse 2^i

Problem Statement
You are given a permutation?P=(P0?,P1?,…,P2N?1?)?of?(1,2,3,…,2N).

You can perform the following operation any number of times (possibly zero):

Choose non-negative integers?a,b?satisfying?0≤a×2b<(a+1)×2b≤2N, and reverse?Pa×2b?,Pa×2b+1?,…,P(a+1)×2b?1?. Here, reversing?Pa×2b?,Pa×2b+1?,…,P(a+1)×2b?1??means simultaneously replacing?Pa×2b?,Pa×2b+1?,…,P(a+1)×2b?1??with?P(a+1)×2b?1?,P(a+1)×2b?2?,…,Pa×2b?.
Find the lexicographically smallest permutation?P?that can be obtained by repeating the operation.

You are given?T?test cases, so find the answer for each.

解題思路：

你有一個長度為 2^n 的排列 P，你可以對它做若干次以下操作：

選擇兩個整數 a,b，滿足區間 [a?2^b,(a+1)?2^b?1] 在數組范圍內，把這個區間反轉。

你要找到經過若干次這種操作后，能得到的字典序最小的排列。

觀察可得：

每次反轉的區間長度必須是 2^b，并且是從 a?2^b?開始（即按塊劃分）。

實際上這與對二叉劃分結構的左右子樹進行翻轉是等價的。

在二叉樹的每一級都嘗試“原順序”或“左右塊交換”，遞歸比較返回最小結果

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
vector<ll> dfs(vector<ll>& a, int i, int j) {if (j == 0) {return {a[i]};}auto x = dfs(a, i, j - 1);auto y = dfs(a, i + (1 << (j - 1)), j - 1);vector<ll> m;m.insert(m.end(), x.begin(), x.end());m.insert(m.end(), y.begin(), y.end());vector<ll> t;t.insert(t.end(), y.begin(), y.end());t.insert(t.end(), x.begin(), x.end());if (m <= t) {return m;} else {return t;}
}
void solve() {int n;cin >> n;vector<ll> a(1 << n);for (int i = 0; i < (1 << n); i++) {cin >> a[i];}vector<ll> ans = dfs(a, 0, n);for (int i = 0; i < (1 << n); i++) {cout << ans[i];if (i < ans.size() - 1)cout << ' ';elsecout << '\n';}
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?F - No Passag??

Probl

em Statement
There is an?H×W?grid. Let?(i,j)?denote the cell at the?i-th row from the top and?j-th column from the left. Among these,?K?cells are goals. The?i-th goal?(1≤i≤K)?is cell?(Ri?,Ci?).

Takahashi and Aoki play a game using this grid and a single piece placed on the grid. Takahashi and Aoki repeatedly perform the following series of operations until the piece reaches a goal cell:

Aoki chooses an integer?a?between?1?and?4, inclusive.
Then, Takahashi chooses an integer?b?between?1?and?4, inclusive, where?a=b?must be satisfied. Let?(i,j)?be the cell where the piece is placed before the operation. Based on the chosen integer?b?and the piece's position, move the piece.
When?b=1: If?(i?1,j)?is within the grid, move the piece from cell?(i,j)?to cell?(i?1,j); if it is outside the grid, do nothing.
When?b=2: If?(i+1,j)?is within the grid, move the piece from cell?(i,j)?to cell?(i+1,j); if it is outside the grid, do nothing.
When?b=3: If?(i,j?1)?is within the grid, move the piece from cell?(i,j)?to cell?(i,j?1); if it is outside the grid, do nothing.
When?b=4: If?(i,j+1)?is within the grid, move the piece from cell?(i,j)?to cell?(i,j+1); if it is outside the grid, do nothing.
Takahashi's objective is to minimize the number of moves until the piece reaches a goal. Aoki's objective is to prevent the piece from reaching the goal; if that is impossible, his objective is to maximize the number of moves until the piece reaches a goal.

For all pairs of integers?(i,j)?satisfying?1≤i≤H,1≤j≤W, solve the following problem and find the sum of all solutions:

Start the game with the piece at cell?(i,j). Assume both players act optimally toward their respective objectives. If Takahashi can make the piece reach a goal, the solution is the minimum number of moves; otherwise, the solution is?0.

解題思路：

1.dp[i] 表示從 i 出發走到目標所需最小步數

2.用 Dijkstra 從目標反向擴展

3. Aoki 選 1~4 中一項，Takahashi 從剩下中選最優方向。確保最壞情況最優

4.?對于每個點，找出在任意 Aoki 決策下，Takahashi 的最小可行步數，再加一更新

5. 最后,? 累加所有的dp[i]

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
using pii = pair<int, int>;
const int dr[5] = {0, -1, 1, 0, 0};
const int dc[5] = {0, 0, 0, -1, 1};
void solve() {int H, W, K;cin >> H >> W >> K;vector<int> dp(H * W, INF);vector<char> g(H * W, 0);for (int i = 0; i < K; i++) {int r, c;cin >> r >> c;--r, --c;int id = r * W + c;g[id] = 1;dp[id] = 0;}auto fun = [&](int r, int c) { return r >= 0 && r < H && c >= 0 && c < W; };priority_queue<pii, vector<pii>, greater<>> pq;for (int i = 0; i < H * W; i++) {if (g[i])pq.emplace(0, i);}while (!pq.empty()) {auto [cost, id] = pq.top();pq.pop();if (cost > dp[id])continue;int r = id / W, c = id % W;for (int dir = 1; dir <= 4; dir++) {int nr = r + dr[dir], nc = c + dc[dir];if (!fun(nr, nc))continue;int ni = nr * W + nc;int d[4];for (int i = 0; i < 4; i++) {int ar = nr + dr[i + 1], ac = nc + dc[i + 1];if (fun(ar, ac))d[i] = dp[ar * W + ac];elsed[i] = INF;}int m1 = INF, m2 = INF;for (int i = 0; i < 4; i++) {if (d[i] < m1) {m2 = m1;m1 = d[i];} else if (d[i] < m2) {m2 = d[i];}}int w = 0;for (int i = 0; i < 4; i++) {int k = (d[i] > m1 ? m1 : m2);w = max(w, k);}int c = w >= INF ? INF : w + 1;if (c < dp[ni]) {dp[ni] = c;pq.emplace(c, ni);}}}long long ans = 0;for (int x : dp) {if (x < INF)ans += x;}cout << ans << '\n';
}
int main() {solve();return 0;
}

G - Big Banned Grid

Problem Statement
There is an?H×W?grid. Let?(i,j)?denote the cell at the?i-th row?(1≤i≤H)?from the top and?j-th column?(1≤j≤W)?from the left.

Each cell in the grid either has an obstacle placed on it or has nothing placed on it. There are?K?cells with obstacles: cells?(r1?,c1?),(r2?,c2?),…,(rK?,cK?).

Takahashi is initially at cell?(1,1)?and wants to reach cell?(H,W)?by repeatedly moving to an adjacent cell (up, down, left, right) that has nothing placed on it.

More precisely, he can repeat the following operation as many times as he likes:

Choose one of the following four operations and perform the chosen operation:
If?1<i?and cell?(i?1,j)?has nothing placed on it, move to cell?(i?1,j). Otherwise, do not move.
If?1<j?and cell?(i,j?1)?has nothing placed on it, move to cell?(i,j?1). Otherwise, do not move.
If?i<H?and cell?(i+1,j)?has nothing placed on it, move to cell?(i+1,j). Otherwise, do not move.
If?j<W?and cell?(i,j+1)?has nothing placed on it, move to cell?(i,j+1). Otherwise, do not move.
Determine whether he can move from cell?(1,1)?to cell?(H,W).

解題思路：

如果有一條線能將(1,1)和(H,W)在網格中分割成兩個獨立的塊, 兩點就無法形成通路

實現上, 我們可以,?

為四個邊界創建虛擬節點（編號k到k+3）：

k：上邊界（x=1）

k+1：下邊界（x=n）

k+2：左邊界（y=1）

k+3：右邊界（y=m）

如果障礙物在邊界上，將其與對應虛擬節點合并

遍歷每個障礙物，檢查它的8個方向（上下左右+對角線）

如果鄰域存在其他障礙物，合并它們的集合

最后, 如果存在下面四種情況就說明兩點被隔斷了

上邊界和下邊界連通（k和k+1）

上邊界和左邊界連通（k和k+2）

左邊界和右邊界連通（k+2和k+3）

下邊界和右邊界連通（k+1和k+3）

#include <bits/stdc++.h>
using namespace std;
class UnionFind {vector<int> fa, sz;
public:int cc;UnionFind(int n) : fa(n), sz(n, 1), cc(n) { iota(fa.begin(), fa.end(), 0); }int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }bool merge(int x, int y) {x = find(x), y = find(y);if (x == y)return false;if (sz[x] > sz[y])swap(x, y);fa[x] = y;sz[y] += sz[x];cc--;return true;}
};
void solve() {int n, m, k;cin >> n >> m >> k;map<pair<int, int>, int> mp;vector<pair<int, int>> p(k);UnionFind uf(k + 5);for (int i = 0; i < k; i++) {cin >> p[i].first >> p[i].second;mp[p[i]] = i;if (p[i].first == 1)uf.merge(i, k);if (p[i].first == n)uf.merge(i, k + 1);if (p[i].second == 1)uf.merge(i, k + 2);if (p[i].second == m)uf.merge(i, k + 3);}for (int i = 0; i < k; i++) {int x = p[i].first, y = p[i].second;for (int dx = -1; dx <= 1; dx++) {for (int dy = -1; dy <= 1; dy++) {if (dx == 0 && dy == 0)continue;auto it = mp.find({x + dx, y + dy});if (it != mp.end()) {uf.merge(i, it->second);}}}}bool ans = uf.find(k) == uf.find(k + 1) || uf.find(k) == uf.find(k + 2) ||uf.find(k + 2) == uf.find(k + 3) ||uf.find(k + 1) == uf.find(k + 3);cout << (ans ? "No" : "Yes") << '\n';
}
int main() {solve();return 0;
}