比赛链接：https://atcoder.jp/contests/abc202/tasks
A - Three Dice
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c;
cin >> a >> b >> c;
cout << 21 - a - b - c << "
";
return 0;
}
B - 180°
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
reverse(s.begin(), s.end());
for (auto& ch : s) {
if (ch == '6') {
ch = '9';
} else if (ch == '9') {
ch = '6';
}
}
cout << s << "
";
return 0;
}
C - Made Up
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
for (int i = 0; i < n; i++) {
cin >> c[i];
--c[i];
}
map<int, int> mp;
for (int i = 0; i < n; i++) {
++mp[b[c[i]]];
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += mp[a[i]];
}
cout << ans << "
";
return 0;
}
D - aab aba baa
题意
给出 (a, b) 的个数， 找出字典序第 (k) 小的字符串。
题解
首先需要计算 (i) 个 (a) ， (j) 个 (b) 可以组成多少不同的字符串，这个问题等价于从 ((0,0)) 走到 ((i,j)) 有多少种不同的走法，即 (C_{i + j}^i) ，由于会溢出 long long ，所以亦可以用动态规划解决，即 (dp_{ij} = dp_{i - 1j} + dp_{ij - 1}) 。
然后逐位推导即可，因为是字典序第 (k) 小的字符串，所以先考虑当前位是否可以为 (a) 。如果当前位为 (a) ，那么剩下不同字符串的个数 (dp_{i-1j}) 应该大于等于 (k) ，否则当前位为 (b) ，同时减去当前位为 (a) 时 (dp_{i - 1 j}) 种字典序较小的情况。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
long long k;
cin >> a >> b >> k;
vector<vector<long long>> dp(a + 1, vector<long long> (b + 1));
dp[0][0] = 1;
for (int i = 0; i <= a; i++) {
for (int j = 0; j <= b; j++) {
if (i - 1 >= 0) {
dp[i][j] += dp[i - 1][j];
}
if (j - 1 >= 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
function<string(int, int, long long)> find_kth = [&](int a, int b, long long k) {
if (a == 0) {
return string(b, 'b');
}
if (b == 0) {
return string(a, 'a');
}
if (k <= dp[a - 1][b]) {
return string("a") + find_kth(a - 1, b, k);
} else {
return string("b") + find_kth(a, b - 1, k - dp[a - 1][b]);
}
};
cout << find_kth(a, b, k) << "
";
return 0;
}
E - Count Descendants
题意
给出一个有 (n) 个结点的树，有 (q) 次询问，每次询问中给出整数 (u,d) ，问结点 (u) 在多少条距离根节点为 (d) 的结点的最短路中。
题解
从根节点出发，给每个结点打上一个访问和离开的时间戳，如下图：
如果结点 (v) 在以结点 (u) 为根节点的子树上（即结点 (v) 到根节点 (1) 的最短路经过结点 (u) ），那么显然有 (in_u le in_v < out_u) ，所以记录不同深度中每个结点的访问时间 (in_i) ，每次询问从深度为 (d) 的所有 (in_i) 中二分查找 (in_u le in_i < out_u) 的结点个数即可。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> G(n);
for (int v = 1; v < n; v++) {
int u;
cin >> u;
--u;
G[u].push_back(v);
}
int timeStamp = 0;
vector<int> in(n), out(n);
vector<vector<int>> list(n);
function<void(int, int)> dfs = [&](int u, int dep) {
in[u] = timeStamp++;
list[dep].push_back(in[u]);
for (auto v : G[u]) {
dfs(v, dep + 1);
}
out[u] = timeStamp++;
};
dfs(0, 0);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int u, d;
cin >> u >> d;
--u;
cout << lower_bound(list[d].begin(), list[d].end(), out[u]) - lower_bound(list[d].begin(), list[d].end(), in[u]) << "
";
}
return 0;
}