AtCoder Beginner Contest 313
貌似这次很难，还好去吃烧烤了
A - To Be Saikyo (abc313 A)
题目大意
给定\(n\)个数\(a_i\)，问第一个数要成为唯一的最大的数，应该加多少。
解题思路
找到后面的最大的数\(m\)，答案就是\(\max(0, m + 1 - a_0)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a)
cin >> i;
int ans = max(0, *max_element(a.begin() + 1, a.end()) + 1 - a.front());
cout << ans << '\n';
return 0;
}
B - Who is Saikyo? (abc313 B)
题目大意
给定\(m\)条关于 \(n\)个数的大小关系，问能否确定出最大的数。
解题思路
大小关系可以构成一张拓扑图，如果\(a > b\)则 \(a \to b\)。如果存在一个最大值，那么从该点出发可以到达所有点。
换句话说，最后看是否仅存在一个度数为 \(0\)的点。存在则其为最大的数。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> du(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
du[v]++;
}
int zero = count(du.begin(), du.end(), 0);
if (zero != 1)
cout << -1 << '\n';
else
cout << find(du.begin(), du.end(), 0) - du.begin() + 1 << '\n';
return 0;
}
C - Approximate Equalization 2 (abc313 C)
题目大意
给定\(n\)个数，要求进行尽量次数最小的操作，使得这些数的极差不超过 \(1\)。
操作为，选择两个数，一个\(+1\)一个\(-1\)。
解题思路
注意到一个性质，无论进行多少次操作，这\(n\)个数的和是不变的，设为 \(sum\)。
那最后极差不超过 \(1\)，且和为 \(sum\)，那自然就是所有数至少是 \(div = \lfloor \frac{sum}{n} \rfloor\)，其中有 \(mod = sum \% n\)个数要\(+1\)， 即为\(div + 1\)。
即最终的\(n\)个数是确定好的，那么自然小的数变成 \(div\)，大的数变成 \(div+1\)。于是排个序，每个数字变成目标数字的次数累加，即作个差就能得到答案了。注意要除以\(2\)，因为每次操作对应了两个数字的变化。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
LL sum = 0;
for (auto& i : a)
cin >> i;
sort(a.begin(), a.end());
sum = accumulate(a.begin(), a.end(), 0ll);
int div = sum / n;
int mod = sum % n;
LL cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += abs((div + (i + mod >= n) - a[i]));
}
cout << cnt / 2 << '\n';
return 0;
}
D - Odd or Even (abc313 D)
题目大意
交互题。
有\(n\)个 \(01\)数。
给定奇数\(k\)，每次可以问其中 \(k\)个数的异或值。
最多 \(n\)次请求，还原出这 \(n\)个数。
解题思路
考虑\(n=4,k=3\)的情况，发现可以问
1 2 31 2 41 3 4
三个请求结果的异或值就是\(a_1\)的值。因为 \(k\)为奇数，每次询问都包括 \(1\)，最终 \(1\)的次数是奇数，而其他的都有一次询问没有被包含，因此出现次数是偶数，异或都消失。答案就是 \(a_1\)的值。
同理，如果再加上 2 3 4，结合1 2 3和1 2 4，那就能得出\(a_2\)的值。
由此可以对前 \(k + 1\)个数 进行询问，每次询问剔除一个数，得到的\(k+1\)个结果，取\(k\)个始终包含第\(i\)个数的结果进行异或，得到的 就是\(a_i\)的值，因此我们可以得到前 \(k+1\)个数的值。
前 \(k+1\) 个数都知道了，要得到第 \(k+2\)个数，那就询问 \(3,4,...,k,k+1,k+2\)的异或值，再异或\(a_3,a_4,...,a_k,a_{k+1}\)就得到了 \(a_{k+2}\)的值。依次就可以得到剩下的所有数了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> ans(n);
auto solve = [&](int l, int r) {
vector<int> tmp(r - l);
vector<int> q;
for (int i = l; i < r; ++i) {
q.clear();
for (int j = l; j < r; ++j)
if (j != i)
q.push_back(j);
cout << "?";
for (auto& i : q)
cout << ' ' << i + 1;
cout << endl;
cin >> tmp[i - l];
}
for (int i = l; i < r; ++i) {
for (int j = l; j < r; ++j) {
if (j != i) {
ans[i] ^= tmp[j];
}
}
}
};
solve(0, k + 1);
for (int i = k + 1; i < n; i++) {
cout << "?";
for (int j = i; j > i - k; --j) {
cout << ' ' << j + 1;
}
cout << endl;
cin >> ans[i];
for (int j = i - 1; j > i - k; --j)
ans[i] ^= ans[j];
}
cout << "!";
for (auto& i : ans)
cout << ' ' << i;
cout << endl;
return 0;
}
E - Duplicate (abc313 E)
题目大意
给定一个数字字符串\(s\)，每次进行一次操作，问经历了多少次，最终的字符串的长度为\(1\)。
操作问，得到一个字符串\(t\)，依次对于 \(s\)的每个数\(s_i\) (除了最后一个)，重复 \(s_{i+1}\)次添加到字符串 \(t\)的末尾。
如果最终长度不能为\(1\)，则输出 \(-1\)。
解题思路
首先考虑何时\(-1\)。
每次操作实际上是删掉一个数，如果每次操作是生成一堆\(1\)的话，容易发现不会造成 \(-1\)的情况，但如果生成了其他的数，那就会叠罗汉一样不断增加，不如生成了\(2\)个\(2\) ，那它们会不断叠起来，而每次删除都只删一个数，那最终就会无限长了。
因此每个非\(1\)的数的后面一个数 一定是\(1\)，否则就会无限长。
考虑如何求答案，我们考虑消除每个数所需要的次数。
对于每个 \(1\)，自然会需要一次操作将其消除，
而对于一个非 \(1\)数\(x\)，其前一个数一定是个 \(1\)，那要考虑消除因它而产生的 \(1\)的次数。 由于我们每操作一次，这个\(x\)就会产生 \(x-1\)个 \(1\)出来，那当这个数 \(x\)变成最后一个数时，假设我们已经进行了 \(cnt\)次操作，包括消除这个 \(x\)的操作带来的一次 \(x-1\)个 \(1\)，我们需要 \((x - 1) \times (cnt + 1)\) 次操作，才能将这个数\(x\)以及其带来的所有 \(1\)消除掉。
而如何求 \(cnt\)，就是倒过来依次考虑每一个数消除所需要的次数累加。
即设 \(dp[i]\)表示消除 \(s[i,n]\)需要的次数，那么 \(dp[i] = dp[i + 1] + (s[i] - 1) \times (dp[i + 1] + 1) + 1\)
上述转移式就是三部分：
- 消除\(s[i + 1, n]\)的次数\(dp[i+1]\)
- 消除\(s[i]\)带来的所有 \(1\)的次数\((s[i] - 1) \times (dp[i + 1] + 1)\)
- 消除\(s[i]\)的次数\(1\)
最后答案就是\(dp[0]\)，初始条件\(dp[n + 1] = 0\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string s;
cin >> n >> s;
auto ok = [&]() {
for (int i = 0; i < n; ++i) {
if (s[i] != '1' && i + 1 != n && s[i + 1] != '1')
return false;
}
return true;
};
if (!ok())
cout << -1 << '\n';
else {
LL ans = 0;
for (int i = n - 1; i >= 1; --i) {
ans += 1ll * (s[i] - '1') * (ans + 1) + 1;
ans = ans % mo;
}
cout << ans << '\n';
}
return 0;
}
F - Flip Machines (abc313 F)
题目大意
<++>
解题思路
<++>
神奇的代码
G - Redistribution of Piles (abc313 G)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - Group Photo (abc313 Ex)
题目大意
<++>
解题思路
<++>
神奇的代码