Thank you for your participation!
Problem A
Idea: Cirno_9baka
The answer is the number of 1s modulo 2.
We can get that by adding '-' before the 2nd,4th,⋯,2k-th 1, and '+' before the 3rd,5th,⋯,2k+1-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 ⌈nk⌉ 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 ai should be smaller than or equal to ⌈nk⌉.
Then we can count the number of ai which is equal to ⌈nk⌉. This number must be smaller than or equal to nmodk, 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 ai=⌈nk⌉, then we use color i to color the j-th cell in each segment.
Then we pick out all colors i that ai<⌈nk⌉−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 ⌈nk⌉ 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 ai=⌈nk⌉−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");
}
}