A. green_gold_dog, array and permutation
题意：给你一个数组\(a\)，你要构造一个排列\(b\)，使得不同的\(a_i-b_i\)尽可能多。
我们按\(a_i\)从小到大分配\(n\)到\(1\)，这样\(a_i-b_i\)一定大于\(a_j-b_j\)\((a_i>a_j)\)。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<int> id(n);
std::iota(id.begin(), id.end(), 0);
std::sort(id.begin(), id.end(), [&](int i, int j) {
return a[i] > a[j];
});
std::vector<int> ans(n);
for (int i = 0; i < n; ++ i) {
ans[id[i]] = i + 1;
}
for (int i = 0; i < n; ++ i) {
std::cout << ans[i] << " \n"[i == n - 1];
}
}
B. XOR Palindromes
题意：给你一个长度为\(n\)的\(01\)串，问你对于每个\(x \in [1, i]\)，能否有一个恰好有\(x\)个\(1\)的\(01\)串和这个串异或后是回文串。
我们先看原串两边有几个不一样的，假设为\(cnt\)，那么\(x\)至少大于等于\(cnt\)。如果\(n\)是偶数，那么我们考虑每次两边同时变回文对应位置的，那么\(\frac{(x - cnt)}{2} <= \frac{n}{2} - cnt\)，如果是奇数，可以让中间的那个选择变也可以不变。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
std::string ans(n + 1, '0');
int cnt = 0;
for (int i = 0; i < n / 2; ++ i) {
cnt += s[i] != s[n - 1 - i];
}
for (int i = cnt, j = cnt; j <= n / 2; i += 2, ++ j) {
ans[i] = '1';
if (n % 2 && i + 1 <= n) {
ans[i + 1] = '1';
}
}
std::cout << ans << "\n";
}
C. Salyg1n and the MEX Game
题意：交互题。有一个集合，每次\(Alice\)加入一个数，\(Bob\)减去一个数。每次\(Bob\)减去的数小于\(Alice\)减去的数。问最后\(mex\)最大时多少。‘
诈骗题。假设我们已经让\(mex\)最大了，那此时\(Bob\)删掉一个数我们应该马上再加回来。然后发现我们只有第一次操作有机会让\(mex\)变大。所以第一次加入当前\(mex\)，后面\(Bob\)删什么我们加什么。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::set<int> s;
for (int i = 0; i < n; ++ i) {
s.insert(a[i]);
}
int mex = 0;
while (s.count(mex)) {
++ mex;
}
std::cout << mex << std::endl;
while (1) {
int x;
std::cin >> x;
if (x == -1) {
break;
}
std::cout << x << std::endl;
}
}
D. Cyclic Operations
题意：你有一个全零的数组，你要让他变成\(b\)，每次可以选择一个长度为\(k\)的序列\(l\)，序列里的数两两不同，然后让\(a_{l_i}=l_{(i+1)\%k+1}\)。问能不能变成\(b\)。
观察发现，如果我们像每个位置要变的数连边，那么会形成一个环，因为每个位置只能连一条出边，所以每条边只在一个环里。也有没在环里的点，但他最终会指向环，这种从环里面搞一些数来配合他就能填好。然后我们考虑怎么填好环里的数。发现如果环的大小不是\(k\)，则无法填好。于是判断每个环的大小即可。注意特判\(k=1\)的情况。
点击查看代码
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
-- a[i];
}
if (k == 1) {
for (int i = 0; i < n; ++ i) {
if (a[i] != i) {
std::cout << "NO\n";
return;
}
}
std::cout << "YES\n";
return;
}
std::vector<int> st(n, -1), b(n);
for (int i = 0; i < n; ++ i) {
if (st[i] == -1) {
int j = i;
int cnt = 0;
while (st[j] == -1) {
st[j] = i;
b[j] = cnt;
j = a[j];
++ cnt;
}
if (st[j] == i && cnt - b[j] != k) {
std::cout << "NO\n";
return;
}
}
}
std::cout << "YES\n";
}