Thanks for your participation!
Problem A
Idea: Cirno_9baka
The answer is the number of $$$1$$$s modulo $$$2$$$.
We can get that by adding '-' before the $$$\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$$$ $$$1$$$, and '+' before the $$$\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$$$ $$$1$$$.
#include <bits/stdc++.h>
using namespace std;
char c[1005];
int main() {
int t;
scanf("%d", &t);
int n;
while (t--) {
scanf("%d", &n);
scanf("%s", c + 1);
int u = 0;
for (int i = 1; i <= n; ++i) {
bool fl = (c[i] == '1') && u;
u ^= (c[i] - '0');
if (i != 1) putchar(fl ? '-' : '+');
}
putchar('\n');
}
}
Problem B
Idea: Cirno_9baka
First, We can divide $$$n$$$ cells into $$$\left\lceil\frac{n}{k}\right\rceil$$$ segments that except the last segment, all segments have length $$$k$$$. Then in each segment, the colors in it are pairwise different. It's easy to find any $$$a_i$$$ should be smaller than or equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$.
Then we can count the number of $$$a_i$$$ which is equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$. This number must be smaller than or equal to $$$n \bmod k$$$, which is the length of the last segment.
All $$$a$$$ that satisfies the conditions above is valid. We can construct a coloring using the method below:
First, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil$$$, then we use color $$$i$$$ to color the $$$j$$$-th cell in each segment.
Then we pick out all colors $$$i$$$ that $$$a_i<\left\lceil\frac{n}{k}\right\rceil-1$$$ and use these colors to color the rest of cells with cyclic order(i.e. color $$$j$$$-th cell of the first segment, of second the segment ... of the $$$\left\lceil\frac{n}{k}\right\rceil$$$ segment, and let $$$j++$$$. when one color is used up, we begin to use the next color)
At last, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil-1$$$, and color them with the cyclic order.
This method will always give a valid construction.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
int fl = 0;
for (int i = 1; i <= m; ++i) {
int a;
scanf("%d", &a);
if (a == (n + k - 1) / k) ++fl;
if (a > (n + k - 1) / k) fl = 1 << 30;
}
puts(fl <= (n - 1) % k + 1 ? "YES" : "NO");
}
}
Problem C
Idea: Little09
We define $$$f_i$$$ to mean that the maximum $$$x$$$ satisfies $$$s_{i-x+1}=s_{i-x+2}=...=s_{i}$$$.
It can be proved that for $$$x$$$ players, $$$f_{x-1}$$$ players are bound to lose and the rest have a chance to win. So the answer to the first $$$i$$$ battles is $$$ans_i=i-f_i+1$$$.
Next, we prove this conclusion. Suppose there are $$$n$$$ players and $$$n-1$$$ battles, and $$$s_{n-1}=1$$$, and there are $$$x$$$ consecutive $$$1$$$ at the end. If $$$x=n-1$$$, then obviously only the $$$n$$$-th player can win. Otherwise, $$$s_{n-1-x}$$$ must be 0. Consider the following facts:
Players $$$1$$$ to $$$x$$$ have no chance to win. If the player $$$i$$$ ($$$1\le i\le x$$$) can win, he must defeat the player whose temperature value is lower than him in the last $$$x$$$ battles. However, in total, only the $$$i-1$$$ player's temperature value is lower than his. Because $$$i-1<x$$$, the $$$i$$$-th player cannot win.
Players from $$$x+1$$$ to $$$n$$$ have a chance to win. For the player $$$i$$$ ($$$x+1\le i\le n$$$), we can construct: in the first $$$n-2-x$$$ battles, we let all players whose temperature value in $$$[x+1,n]$$$ except the player $$$i$$$ fight so that only one player will remain. In the $$$(n-1-x)$$$-th battle, we let the remaining player fight with the player $$$1$$$. Since $$$s_{n-1-x}=0$$$, the player $$$1$$$ will win. Then there are only the first $$$x$$$ players and the player $$$i$$$ in the remaining $$$x$$$ battles, so the player $$$i$$$ can win.
For $$$s_{n-1}=0$$$, the situation is similar and it will not be repeated here.
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int T, n, ps[2];
char a[N];
void solve() {
scanf("%d %s", &n, a + 1);
ps[0] = ps[1] = 0;
for (int i = 1; i < n; ++i) {
ps[a[i] - 48] = i;
if (a[i] == '0')
printf("%d ", ps[1] + 1);
else
printf("%d ", ps[0] + 1);
}
putchar('\n');
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}