CVBB ACM Team

题意:读错题直接劝退了。给出一个黑白方格，对于一个白格，如果同一列和同一行都没有黑格，那么可以将它涂黑，如果一个人没有格子可以涂了就输了。问先手能不能赢。

题解:每次会让全为白的行和全为白的列各减少$1$，取这两个的$min$判断奇偶即可。

题意:给出一个序列，每个元素还有$01$两种颜色。每次操作可以将不同颜色的两个元素交换，问能否经过数次操作将整个序列交换成有序的。

题解:只要有不同色的元素，就可以实现任意两个元素的互换，例如$a$是$0$，$bc$是$1$，只需要$a-b,a-c,a-b$即可。因此如果无序且只有一种颜色则无解，否则有解。

题意:给定两个$1$到$n$的排列，将其中一个变成它本身的循环同构，使得两个排列相同位置上数字相同的位置尽可能多。

题解:算出每一位移动多少位可以对应上，最后取最大值即可。

题意:给定一个方格图，每个格子上可能是空地、障碍、好人或坏人，问能否将一些空地题换成障碍使得所有好人都能走到右下角且所有坏人都走不到右下角。

题解:将所有坏人四角围杀然后从右下角dfs看能不能走到所有好人即可。

题意:从$n$个数里面选$k$个数，如果有至少$\max(1, k - 2)$个数的二进制位$i$是$1$，那么总权值增加$2^i$，求最大权值。$(1 \le n \le 500)$

题解:本质上就是找$3$个数使他们的$OR$最大，数据范围也在疯狂暗示，因为一旦加入了第四个数，那么前三个数某些位可能失效，而第四个数新增的某些位也必须前三个数有相应的位才能有效，因此从第四个开始越加越完蛋，选三个是最优的。注意要特判不到$3$个数的情况。

题意:给定字符串$s$和$t$，每次可以将$s$的任意一个前缀和相同长度的后缀交换位置，问$s$能不能变成$t$。

题解:可以发现一对位置对称的字符在交换后也是对称的，可以证明这是个充要条件（构造方法大致就是先把里面的换好，然后换外面的过程不会干扰里面）。因此开个map记录一下即可，注意奇数长度要特判一下中间的字符，这个字符无论如何交换也不会改变位置，因此必须一样。

题意:交互题。有一个长度为$n$的序列$a_i$，你需要求出对于每个下标$i$，除了$a_i$其它$a$里面元素的$OR$。每次询问$a$任意一个子集的$OR$，最多询问$13$次。$(2 \le n \le 1000)$

题解:这不是之前二分那题吗（狂喜）草好像做不了。因为$OR$是可重复贡献的，不用害怕元素重复带来的影响，因此我们可以考虑每次询问很多个元素的$OR$，然后通过特定的算法使得某几个询问的并集正好就是除了$a_i$的其它全部元素。首先有一个询问$2 \log n$次的方法，我们可以设$f_{x,0/1}$为所有下标第$x$位为$0/1$的元素的$OR$，合并答案时，对于一个下标$i$，如果第$x$位是$0$那么我们合并$f_{x,1}$，反之亦然。因为如果两个数字不同那么它们二进制下至少有一位不同，因此可以保证其它元素都被统计而自己没被统计。但是这个方法要询问$2 \log n = 20 > 13$次，不符合题意。我们发现我们的询问次数之所以前面有个$2$，是因为有可能出现两个数字在二进制下只有一位不同，这时候如果不维护$f_{x,0}$和$f_{x,1}$就无法获取完整信息了，我们如果可以让任意两个不同下标对应的编码至少有$2$位不一样，就可以避免这种情况发生。我们可以为每一个下标赋予一个两两不同的$13$位的$01$串，且每个串含有$1$的个数相同，这样就满足了上述条件。设$f_x$为所有下标对应编码的第$i$位为$1$的所有元素的$OR$，那么我们只用询问$13$次就可以了。另外还需要保证这个编码方法满足的不同编码数量要大于$n$，最大值为$\binom{13}{6}=1716>n$，满足条件。