Codeforces 1710A Color the Picture
题意：一张图是一个 $n \times m$ 的矩阵，$k$ 种颜色，第 $i$ 种颜色能用 $a_i$ 次，称一张图是美的当且仅当每个格子的上下左右四个格子中有三个颜色与它相同（超出边界时认为与另一边相邻），问是否存在一种构造方式使得图是美的
手玩一下样例说明，猜想合法的构造方式中颜色一定要以占据大于等于2个相邻行/相邻列的色块这一形式出现（这一点通过分析一个非常简单的例子也可以发现，比如 n 行 1 列的情况）
然后问题就变得很简单了。我们分别讨论行和列的情况，如果一种颜色在对行的讨论中无法填满 2 行或在列的讨论中无法填满 2 列，这种颜色一定就是不可使用的，我们只需要考虑使用能填满至少 2 行或 2 列的颜色。很容易意识到存在构造方式的一个必要条件是这些颜色能填满的行数或列数大于等于 n 或 m。观察第三个样例能发现一个corner case，如果填充完一些颜色后剩余未涂色的行或列只剩下 1 行/列，而没用过的颜色都只够填充 2 行/列，则会导致既没有已经用过的颜色可用又没法新采用一种颜色从而无法构造成功。在总行数/总列数为偶数时，这一情况不会出现（如果剩下 1 行/列说明肯定有一种颜色涂了奇数行/列，我们擦掉这种颜色的一行/列就可以空出未涂色的 2 行，在总行数/总列数为奇数时，不难发现只要存在一种颜色能填充 3 行/列，就可以通过有意选用它把剩下的构造转化为总行数/总列数为偶数的情况
#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T> inline T read(){
T sum = 0;
int fl = 1,ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}
constexpr int maxn = 1e5 + 5;
int t;
int n,m,k;
int a[maxn];//手玩样例的说明猜想合法的构造方式中颜色一定要以占据大于等于2个相邻行/相邻列的色块出现.行和列的讨论本质是一样的
//考虑何时合法,显然,如果一个颜色的数量不够填充大于等于2行/列,那它对此时讨论到的情况没有贡献,由此得知合法的一个必要条件是够填充大于等于2行/列的颜色能填充的完整行数/列数之和大于等于总行数/总列数
//通过第三个样例,我们发现即使上述条件成立,但由于总行数/总列数减去一些颜色能填充的最大行数/列数后剩下了1行/1列,而还没用过的颜色又都只够填充2行/2列,导致既没有已经用过的颜色可用又没法新采用一种颜色从而无法构造成功.总行数/总列数为偶数时,显然不存在这样的情况,因此考虑为奇数的情况,不难发现,只要存在一种颜色可以填充至少3行/3列,那么我们就可以通过用这种颜色替换已经填充好颜色的2行/2列以及剩下的最后1行/1列从而成功构造.
void Solve(){
bool flag = false;
n = read<int>();
m = read<int>();
k = read<int>();
for(int i = 1; i <= k; i++){
a[i] = read<int>();
}
int N = n;
if(n % 2){
bool all2 = true;
for(int i = 1; i <= k; i++){
if(a[i] / m >= 3) all2 = false;
if(a[i] / m >= 2) N -= (a[i] / m);
}
if(N <= 0 && !all2) flag = true;
}else{
for(int i = 1; i <= k; i++){
if(a[i] / m >= 2) N -= (a[i] / m);
}
if(N <= 0) flag = true;
}
int M = m;
if(m % 2){
bool all2 = true;
for(int i = 1; i <= k; i++){
if(a[i] / n >= 3) all2 = false;
if(a[i] / n >= 2) M -= (a[i] / n);
}
if(M <= 0 && !all2) flag = true;
}else{
for(int i = 1; i <= k; i++){
if(a[i] / n >= 2) M -= (a[i] / n);
}
if(M <= 0) flag = true;
}
puts(flag ? "Yes" : "No");
}
signed main(){
t = read<int>();
while(t--) Solve();
return 0;
}
题意：给一个整数 $n$ ，构造一个长 $n$ 的非负整数串，满足串中元素各不相同且小于 $2^{31}$ 时奇数位置与偶数位置的元素的各自的异或和相等
对于与异或和相关的构造，我们一般从二进制位的角度进行考虑。奇数位的元素与偶数位的元素异或和相等，说明异或和对应的二进制位上 1 出现的次数模 2 同余。我们不必试图凭空构造出一个满足该条件的串（这样的尝试明显更加难以切入），而可以考虑先随便生成一个串，再试图通过调整其中的元素来满足构造的要求。
我们先随便丢一个串进去 （比如把 1 到 n 依次放在 1 到 n 的每一个位置上），然后进行检查。如果刚好满足了构造要求当然任务就完成了，然而大多数时候是不会这么凑巧的。
很明显，对于奇数位和偶数位的元素的每一个二进制位，上面 1 所出线的次数模 2 的余数要么相等，要么不相等，采用二进制的思想，我们可以把全部二进制位的相等情况压缩成一个数 x （比如，第 i 位奇偶性不相等则设 x 的第 i 个二进制位为1）
接下来考虑如何调整原串中的元素。我们当然希望刚刚求出的这个数 x 能派上用场。这时可以发现，我们如果保证随便生成的串中有元素为 0 ，在 x 没有出现在串中的情况下把这个为 0 的位置直接设置为 x 就可以完成构造，因为一开始该位置为 0 是不会对异或和的二进制位贡献 1 的，替换为 x 恰能给一类（奇数或偶数）位置每个 1 数目模 2 不同余的二进制位增加 1 ，将它转换为模 2 同余的情况。那当 x 在串中出现过应该怎么办呢？我们可以在用这个数替换 0 的位置后，在它和串中一个与它的值不同的数的二进制位左侧同时加上 1 （当然具体左多少位应该保证加完后的两个数原来都没有出现（比如最初生成的串范围是 [0,n) ，那 1 就要加在第log2(n) + 1位），这样原串的奇数位置和偶数位置在新增的 1 所在的二进制位上 1 的数目模 2 同余（如果加 1 的两个位置同奇偶，那么有一种奇偶性的位置该位有 2 个 1 ，另一种则有 0 个 1 ，反之，奇数位置和偶数位置的该位各有一个 1，因此该位 1 数目一定是同奇偶的），不会导致异或和结果不同
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline T read(){
T sum = 0;
int fl = 1,ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}
constexpr int maxn = 2e5 + 5;
int t,n;
int ans[maxn];
int num1[20],num2[20];//奇数和偶数
void Solve(){
memset(num1,0,sizeof(num1));
memset(num2,0,sizeof(num2));
n = read<int>();
int mv = (log2(n) == (int)log2(n) ? log2(n) : log2(n) + 1);
for(int i = 0; i < n; i++){
ans[i] = i;
for(int k = 0; k < 20; k++){
if(i % 1 == 0){
num1[k] += (i >> k) & 1;
}else num2[k] += (i >> k) & 1;
}
}
bool flag = true;
for(int i = 0; i < 20; i++){
//cout << num1[i] << ' ' << num2[i] << endl;
if(num1[i] % 2 != num2[i] % 2){
flag = false;
break;
}
}
if(!flag){
int x = 0;
for(int i = 0; i < 20; i++){
if(num1[i] % 2 != num2[i] % 2){
x |= (1 << i);
}
}
if(x >= n){//先放0-n-1,如果有某个二进制位的1数目不同奇偶,说明可以把一个数的这一位换成1使得他们同奇偶(从0开始可以很方便的操作),把所有这样的位设为1得到一个数,显然把0换成这个数就可以使得奇数位置和偶数位置的数的每一个二进制位中1的数目同奇偶
ans[0] = x;//如果替换为的数没出现过,直接把0换成得到的数就可以了
}else{//如果这个数出现过,我们可以通过在它和一个与它值不同的已经存在的数的二进制位左侧同时加一个1从而在避免重复的同时不影响各个二进制位上1个数的奇偶性(如果那个值不同的数所在位置与它同位奇数,则奇数位值这一新增的二进制位上1出现2次,与偶数位出现0次同偶,反之奇数位和偶数位值这一二进制位上1各出现1次,同奇)
ans[0] = (1 << mv) + x;
ans[(x - 1 == 0 ? x + 1 : x - 1)] += (1 << mv);
}
}
for(int i = 0; i < n; i++){
printf("%d ",ans[i]);
}
puts("");
}
int main(){
t = read<int>();
while(t--) Solve();
return 0;
}
Codeforces 1758B XOR = Average
题意：构造一个长度为 $n$ 的序列 $a_1,…,a_n (a_i \in [1,1e9])$ ，满足 $a_1\oplus a_2\oplus\cdots\oplus a_n = \frac{a_1 + \cdots a_n}{n}$
很容易想到因为同一个数异或奇数次的结果就是这个数本身，因此当 n 为奇数时输出 n 个一样的数就可以了
接下来考虑 n 为偶数时的情况，我们知道，任何一个偶数都一定能被分解为 2 的某个幂次与一个奇数的乘积，因此我们只需要构造出 n 为 2 的幂次时的解，根据 n 为奇数时的结论将这个序列重复某个奇数次即可
那么，应该如何构造 n 为 2 的幂次时的答案序列呢？考虑当 n 为偶数时一个各位置上的数相同的序列的异或和为 0 ，是因为整个序列中这个数二进制表示中的每一位上 1 的总数一定是一个偶数。很明显，把其中一个数中的一个为 1 的位变成 0 就能保证异或结果不为 0 了。再考虑将序列中一个数的二进制中某个为 1 的位变成 0 后如何保证平均数不变。因为二进制是满 2 进 1，因此我们只需要在序列中的两个数中恰好比这一位低一位的位置加 1 就可以保证总和不发生改变。为了方便，我们选用一个 2 的幂作为进行操作前的初始序列（因为只有最高位为 1 ，不需要考虑把两个数的次高位加 1 时引发进位的问题），然后就可以轻易构造出答案
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline T read(){
T sum = 0;
int fl = 1,ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}
constexpr int maxn = 1e5 + 5;
int t;
int n;
int ans[maxn];
void Solve(){
n = read<int>();
if(n % 2){
for(int i = 1; i <= n; i++){
printf("%d ",1);
}
puts("");
}else{
int pw = 1,cnt = 0;
while(n % (pw * 2) == 0){
pw *= 2;
cnt++;
}
for(int i = 1; i <= pw; i++){
ans[i] = (pw == 2 ? pw : pw / 2);
}
if(pw == 2) cnt++;
ans[1] &= (~(1 << (cnt - 1)));
ans[1] |= (1 << (cnt - 2));
ans[2] |= (1 << (cnt - 2));
for(int j = 1; j <= n / pw; j ++){
for(int i = 1; i <= pw; i++){
printf("%d ",ans[i]);
}
}
puts("");
}
}
int main(){
t = read<int>();
while(t--) Solve();
return 0;
}
//1 : 1
//2 : 1 3
//4 : 1 2 2 3
//2 : 11 01把一个位置设为0的代价是低位两个1.
//4 : 01 11 10 10