A. green_gold_dog, array and permutation
题意：给出一个长为\(n\)的数组\(a\)，找到一个长为\(n\)的排列\(b\)，使得\(a\)与\(b\)对应位置上的元素的差尽可能大
Solution
将数组\(a\)排序，然后令排列\(n,n-1,...,2,1\)对应到对应的元素即可
struct node
{
int x, id;
bool operator<(const node &t) const &
{
return x < t.x;
}
}e[N];
int b[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> e[i].x;
e[i].id = i;
}
sort(e+1,e+1+n);
for(int i=1;i<=n;i++)
{
b[e[i].id]=n-i+1;
}
for(int i=1;i<=n;i++)
{
cout<<b[i]<<" \n"[i==n];
}
}
B. XOR Palindromes
题意：给出一个长为\(n\)的01串\(s\)，定义实数\(x\)为\(good\)，有以下条件
存在一个长为\(n\)的含有\(x\)个1的01串\(l\)，在把\(s_i\)替换成\(s_i \oplus l_i\)后，\(s\)变成回文串
对于每一个\(0\le t\le n\)，如果存在\(good\)实数，输出1，反之输出0
Solution
假设\(s\)在对称位置有\(cnt1\)个不同对数，\(cnt2\)个相同对数，则至少需要\(cnt1\)个1才能使得\(s\)变为回文
然后我们考虑\(n\)的奇偶性
对于偶数的情况，我们发现，从\(cnt1\)出发，每次必须选择一对相同对数，才能维护\(s\)的回文状态，一直到\(cnt1+2cnt2\)为止，并且对于中间的第\(x\)个，如果\((x-cnt1)\)是奇数，则不合法，反之合法
对于奇数数的情况，则是到\(cnt1+2cnt2+1\)为止，并且对于中间所有的都是合法的
然后把已经是回文的情况特判一下即可
void solve()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
vis[i] = 0;
string s;
cin >> s;
int cnt2 = 0, cnt1 = 0;
for (int i = 0; i < n / 2; i++)
{
if (s[i] != s[n - i - 1])
cnt1++;
else
cnt2++;
}
string t = s;
reverse(t.begin(), t.end());
if (t == s)
{
if (n % 2 == 0)
{
for (int i = 0; i <= n; i++)
{
if (i & 1)
cout << "0";
else
cout << "1";
}
}
else
{
for (int i = 0; i <= n; i++)
cout << "1";
}
cout << "\n";
return;
}
cout << "0";
for (int i = 1; i <= n; i++)
{
if (i < cnt1)
cout << "0";
else
{
if (n & 1)
{
if (i - cnt1 <= 2 * cnt2 + 1)
cout << "1";
else
cout << "0";
}
else if (i - cnt1 <= 2 * cnt2 && (i - cnt1) % 2 == 0)
cout << "1";
else
cout << "0";
}
}
cout << "\n";
//cout << cnt1 << " " << cnt2 << "\n";
}
C. Salyg1n and the MEX Game
题意：给出一个集合\(S\)，Alice先手，Alice每次可以加入一个数\(x(0\le x\le 1e9)\)，Bob每次可以删除一个\(y(0\le y\le 1e9)\)，其中\(y<x\)，如果不能删除，则返回-1，进行若干次使得MEX(S)最大。
Solution
假设从0开始最高的是到\(n\)，那么我们可以加入\(n+1\)，则Bob必须删除一个小于它的数，然后我们可以把那个数加回来，这样就能使得MEX(S)最大
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int pos = -1;
for (int i = 1; i <= n; i++)
{
if (a[i] == pos + 1)
{
pos++;
}
}
pos++;
int y;
cout << pos << endl;
cin >> y;
while (y != -1)
{
pos = y;
cout << pos << endl;
cin >> y;
}
}
D. Cyclic Operations
题意：有一个数组\(a\)，一开始全0，现在可以进行下面操作无数次
选择一个长为\(k\)的数组\(l\)(对于\(1\le i \le n\)，都有\(1\le l_i \le n\)，且它们是完全不同的)，然后令\(a_{l_i}\)变为\(l_{(i\%k)+1}\)
现在给出一个数组\(b\)，问\(a\)能否经过若干次操作变为\(b\)
Solution
考虑到每次操作其实是生成了一个长为k的环，而在已经在环上数进行操作，则其实是将其拆开并再生成一个环，所以我们可以把它变成一个图，直接bfs，然后看每个点能否到达一个长为k的环，这样就可以判断了
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
vis[i] = 0;
b[i] = 0;
}
if (k == 1)
{
for (int i = 1; i <= n; i++)
{
if (a[i] != i)
{
cout << "NO\n";
return;
}
}
cout << "YES\n";
return;
}
else
{
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
int pos = i;
int idx = 1;
int flag = 0; //flag感觉好像没啥用（
set<int> v;
while (!vis[pos])
{
v.insert(pos);
vis[pos] = 1;
b[pos] = idx;
pos = a[pos];
idx++;
}
if (v.count(pos))
{
int x = idx - b[pos];
if (x != k)
{
cout << "NO\n";
return;
}
flag = 1;
}
else
{
flag = 1;
}
if (!flag)
{
/*for (int i = 1; i <= n; i++)
cout << b[i] << " \n"[i == n];*/
cout << "NO\n";
return;
}
}
/* for (int i = 1; i <= n; i++)
cout << b[i] << " \n"[i == n];*/
cout << "YES\n";
}
}
E. Salyg1n and Array
题意：有一个数组\(a\)，长为\(n\)，给出一个数字\(k\)，\(n,k\)均为偶数，且有\(1\le k \le n \le k^2 \le 2500\)，现在每次询问\(i\)可以得到\(a_i \oplus a_{i+1} \oplus...\oplus a_{i+k-1}\)，询问后，询问的部分会反转，求\(a_1 \oplus a_{2} \oplus...\oplus a_{n}\)
Solution
我们先经过若干次操作直接询问，可以得到\(a_1\oplus a_{2} \oplus...\oplus a_{mk}\)
剩下\(k+x\)个，每次询问后都会反转
假设询问的重叠部分长为\(a\)，未重叠的则为\(b\)，\(c\)表示一共进行了这么多次操作，则有
\[\begin{cases} a+b=k\\ a+bc=k+x \end{cases} \]其中\(c\)必须是奇数，这样我们就可以得到剩余部分的异或和
枚举\(a\)即可，最多操作次数为51次
void solve()
{
int n, k;
cin >> n >> k;
if (n % k == 0)
{
int ans = 0;
for (int i = 1; i <= n / k; i++)
{
cout << "? " << (i - 1) * k + 1 << endl;
int x;
cin >> x;
ans ^= x;
}
cout << "! " << ans << endl;
}
else
{
int ans = 0;
for (int i = 1; i <= n / k - 1; i++)
{
cout << "? " << (i - 1) * k + 1 << endl;
int x;
cin >> x;
//x = 1;
ans ^= x;
}
int res = n - (n / k - 1) * k;
int st = (n / k - 1) * k;
for (int i = 1; i < k; i++)
{
int x = i, y = k - i;
if ((res - i) % y == 0)
{
int z = (res - i) / y;
if (z & 1)
{
// cout << z << endl;
for (int i = 1; i <= z; i++)
{
cout << "? " << st + (i - 1) * y + 1 << endl;
int xx;
cin >> xx;
//xx = 1;
ans ^= xx;
}
cout << "! " << ans << endl;
return;
}
}
}
}
}