AtCoder Beginner Contest 417

A A Substring

You are given an N-character string S consisting of lowercase English letters.
Output the string of N?A?B characters obtained by removing the first A characters and the last B characters from S.

翻譯：

給定一個由 N 個小寫英文字母組成的字符串 S。
輸出 S 字符串移除前 A個字符，后 B 個字符后的字符串。

分析：使用string中的 s.erase(pos, k) 刪除 s中的從 pos 下標開始的連續 k個元素。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f;void solve() {int n, a, b;string s;cin >> n >> a >> b >> s;s.erase(0, a);s.erase(s.size()-b, b); cout << s;
}int main() {int T = 1; while (T--) solve();return 0;
}

B Search and Delete

Takahashi has an integer sequence $A=(A_1,A_2,\dots ,A_N)$ of length N.
It is guaranteed that A is non-decreasing.

Takahashi performs M operations on this integer sequence.
In the i-th operation $(1\le i\le M)$, he performs the following operation:

If the sequence A contains $B_i$ as an element, select one such element and delete it. If no such element exists, do nothing.
Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.

Find A after performing M operations.

翻譯：

高橋有一個長度為 N 的整數序列 $A=(A_1,A_2,\dots ,A_N)$。
保證 A 是非遞減的。

高橋對這個整數序列執行 M 次操作。在第 i $(1\le i\le M)$ 次操作中，他執行以下操作：

如果序列 A 包含 $B_i$ 作為元素，選擇其中一個這樣的元素并刪除它。如果不存在這樣的元素，則不執行任何操作。
注意，由于 A 是非遞減的，操作后的序列無論選擇哪個元素都是唯一確定的，并且仍然保持非遞減。

執行 M 次操作后找到 A 。

分析：數據范圍很小，直接暴力模擬即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f;void solve() {int n, m;cin >> n >> m;vector<int> a(n + 1), b(m + 1);for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= m; i++) cin >> b[i];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (b[i] == a[j]) {a[j] = -1;break;}}}for (int i = 1; i <= n; i++) {if (a[i] != -1)cout << a[i] << ' ';}
}int main() {int T = 1; while (T--) solve();return 0;
}

C Distance Indicators

You are given an integer sequence $A=(A_1,A_2,...A_N)$ of length N.

Find how many pairs of integers (i,j) ($1\le i<j\le N$) satisfy $j?i=A_i?A_j$.

Constraints：$1\le N\le 2\times 10^5,1\le A_i\le 2\times 10^5(1\le i\le N)$。

翻譯：

你被給定一個長度為 N 的整數序列 $A=(A_1,A_2,...A_N)$。

找出有多少對整數 (i,j) ($1\le i<j\le N$) 滿足 $j?i=A_i?A_j$。

約束：$1\le N\le 2\times 10^5,1\le A_i\le 2\times 10^5(1\le i\le N)$。

分析：數據范圍較大，枚舉復雜度為 $O(n^2)$，考慮將原式變形：移項得 $j?a_j=i+a_i\ge 2$，可以發現左右兩邊均是與當前位置有關的信息。

使用標記數組 $st[i+a[i]]++$ 表示 $i+a[i]$ 出現的次數加一。

由于答案的更新在 st 更新前，所以保證了 $j<i$。

答案需要開 long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, inf = 0x3f3f3f3f;void solve() {ll n, ans = 0;cin >> n;vector<int> a(n + 1), st(N << 1, 0);for (int i = 1; i <= n; i++) {cin >> a[i];if (i - a[i] >= 2)ans += st[i - a[i]];st[i + a[i]]++;}cout << ans << "\n";
}
int main() {int T = 1; while (T--) solve();return 0;
}

D Takahashi’s Expectation

翻譯：

分析：

E A Path in A Dictionary

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, …, vertex N, and the i-th $(1\le i\le M)$ edge connects vertices $U_i$ and $V_i$.

Find the lexicographically smallest simple path from vertex X to vertex Y in G.
That is, find the lexicographically smallest among the integer sequences $P=(P1,P2,\dots ,P_{\mid P\mid })$ that satisfy the following conditions:

• $1\le P_i\le N$
• If $i\ne j$, then $P_i\ne P_j$.
• $P_1=X$ and $P_{\mid P\mid }=Y$.
• For $1\le i\le \mid P\mid ?1$, there exists an edge connecting vertices $P_i$ and $P_{i+1}$.

One can prove that such a path always exists under the constraints of this problem.

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

翻譯：
給定一個簡單的連通無向圖 G ，它有 N 個頂點和 M 條邊。
G 的頂點編號為頂點 1、2 、… 、N ，第 i 條 $(1\le i\le M)$ 邊連接頂點 $U_i$ 和 $V_i$。
?在 G 中，找到從頂點 X 到頂點 Y 的字典序最小的簡單路徑。
也就是說，找到滿足以下條件的整數序列 $P=(P1,P2,\dots ,P_{\mid P\mid })$ 中字典序最小的序列：

• $1\le P_i\le N$
• 如果 $i\ne j$, 那么 $P_i\ne P_j$.
• $P_1=X$ 且 $P_{\mid P\mid }=Y$.
• 對于 $1\le i\le \mid P\mid ?1$, 存在一條邊連接頂點 $P_i$ 和 $P_{i+1}$.

可以證明，在問題的約束條件下，這樣的路徑總是存在。
給出了 T 個測試用例，所以找出每個的答案。

分析：建圖后按節點升序排序，dfs 遍歷即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, inf2 = 1e18;
vector<int> G[N];
int a[N], n, m, x, y, p;
bool st[N], flag;void dfs(int u) {if (flag) return;st[u] = 1, a[++p] = u;if (u == y) {for (int i = 1; i <= p; i++)cout << a[i] << " \n"[i == p];flag = 1; return;}for (auto& v : G[u]) {if (st[v]) continue;dfs(v);}--p;
}
void solve() {cin >> n >> m >> x >> y;p = 0, flag = 0;memset(st, 0x00, sizeof st);for (int i = 1; i <= n; i++) G[i].clear();for (int i = 1, u, v; i <= m; i++) {cin >> u >> v;G[u].push_back(v), G[v].push_back(u);}for (int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end());dfs(x);
}
signed main() {int T = 1;cin >> T;while (T--) solve();return 0;
}

F Random Gathering

G Binary Cat