貌似这次很难，还好去吃烧烤了
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)
题目大意
<++>
解题思路
<++>
神奇的代码
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
