Codeforces Round 912 (Div. 2)

A. Halloumi Boxes

大致题意

有一个数组，每次允许选择其中一段长度不超过 $k$ 的字串进行翻转，问是否可能将其排序好

思路

最有用的翻转就是两个值，那就是冒泡了，所以要么本身有序，要么 $k \geq 2$ 就行了

AC code

B. StORage room

大致题意

有一个矩阵，其中的每一项 $M_{i,j} = a_i | a_j$，问是否能得到原始数组的其中一种可能

思路

即然是 $M_{i,j} = a_i | a_j$，那么反过来可以得到 $a_i = M_{i,0} & M_{i,1} & M_{i,2} \dots$

这不一定是原始解，但是一定是正确的解。还原后再验证一下矩阵对不对就行了

AC code

C. Theofanis’ Nightmare

大致题意

一个数组，其中有负值，将其拆成多个字串，然后按照原始顺序从左往右编号，从 1 开始编号

然后将每个字串内求和，乘上其的编号，最后再相加，问如何拆最大

思路

从最后一个值看，假如其为 $c$，那么如果其独立出去，和不独立出去，和前面的段合并，那么得到的差值就是 $c$，因为 $(n + 1) \times c - (n) \times c$

所以，如果 $c > 0$ 那么这样做是有意义的，反之则应该尽力避免拆

类推可以得到，如果当前值即之后的所有值加起来是 $< 0$，那么不要拆，反之则拆即可

AC code

D1. Maximum And Queries (easy version)

大致题意

有一个数组，允许每次给其中一个值 $+1$，最多执行 $k$ 次，问最终得到的数组的每一项进行位与运算，问最大值可以是多少

思路

要从位运算上下思路

如果一个值的某个位不是 1，那么如果通过 $+1$ 的方式把它变成 1，带来的后果就是更低位置的都会归零

所以我们需要从高位开始枚举位置，假设把这个位置大家都变成 1，那么就可以带来结果上的增长，但是会需要消耗一定的 $k$

注意一旦消耗过 $k$，那么再试图对这个值进行累加的时候，要把低位都认为是 0 了

AC code

E. Geo Game

大致题意

有两个人博弈，二维屏幕上有一些点，其中一个固定为起始点，两个人轮流指定下一个点，不可以是之前选中的点，直到所有点都被走到

然后求算路径的欧几里得距离的平方和，问能否保证是偶数或者是奇数

思路

仔细思考就会发现很像是一笔画问题

如果某个点与开始点的欧几里得距离是奇数，我将其归为一类 A，另外的点为另外一类 B。那么显然，同一个类内的点相互走并不会变化结果的奇偶性。
但是不同类的路径就会变化奇偶性。非常巧的是，因为每个点都会被进入一次和出去一次，
所以理论如果要回到开始点，那么最终一定是偶数，因为一旦进入 A 类，就一定要回去 B 类，即每个 A 类的点会产生两条路径，也就是最终没有变化奇偶性

那么我们可以得到，如果 A 类点作为最后一个点，那么路径就是奇数的，否则就是偶数，然后再根据博弈再去模拟即可

AC code

Generated by RSStT. The copyright belongs to the original author.

Source