博客 > Code Forces

Round #682 (div. 2)

题目链接

A

只要全为1, 必然满足.


B

这道题考察了一个二进制的进位原理. 首先这两个区间的和表示成二进制00000000, 每一个ai都能且只能把二进制表示中的一位+1, 如23+21+27= 10001010. 那么如果想要让两个区间值相同, 只有如下两种情况:


C

给出一个矩阵, 每个元素都可以选择加1或者不加, 目标是找到一个四边相邻的节点值都不同的加法, 保证有解.

看到加1或者不加, 可以考虑奇偶性.

任何一个奇数任何一个偶数. 因此只要把最后的矩阵构造成如下形状:

就可以了.


D

要把一个长度为n的数组a中的所有值通过每三个做异或后赋值变成全部相同的. 要求在n步内实现.

这题原来读错题了, 以为是找最优解(步数最小), 看了题解才反应过来是只要是n步内实现的任意方法都可以. 也就是随便构造一个能让数组所有值相同的办法就可以了.

这里有一些异或()运算的性质:

结合律&交换律
abc=a(bc)=bac=...
零律&一律
0a=a1a=a¯
归零律&自反性
aa=0baa=b0=b

根据这些性质, 我们构造这样一个方法:

Pi=j=1iaj ,

根据上述异或运算的性质可知

Pi+n=Pij=i+1i+naj

len(a)为奇数的情况

从左到右, 在第i次, 取下标为{2i1,2i,2i+1}的三个数进行异或和赋值, 也就是步长为2, 每次共用上次的最后一个元素.

len(a)=7为例, 处理过程如下:

1 2 3 4 5 6 7
第1次 P3 P3 P3 - - - -
第2次 P3 P3 P5 P5 P5 - -
第3次 P3 P3 P5 P5 P7 P7 P7

接下来, 我们利用自反性, 把成对的P3P5通过和P7异或来变成P7, 即可得到7个P7.

这种方法下, 第一过程需要(n12)步, 第二过程需要(n32), 总计(n2)步, 满足条件.

len(a)为偶数的情况

设最终处理后的数组各个下标元素均为X, 根据归零律, 有:

(XX)...(XX)=0...0=0=XX

由此可知, 如果把最终结果数组任意划分成两个奇数区间, 则两个区间内所有元素的异或必然都等于X.

我们通过自反性可知, 将此规律推演到初始数组里的两区间时依然成立, 因为aaa=a, 即多次的三数异或和赋值并不影响最终的异或结果.

为了方便, 我们把最后一个元素单独作为一个区间, 剩下的作为另一个区间. 以len(a)=8为例, 把区间划分为{a1,...,a7}{a8}, 易知:

{X=a8X=i=17ai=P7

P7可以用刚才提到的奇数时的情况求解.

同时也可逆推得到, 如果a8P7, 即P80, 则此题无解.


E

一个长度为n的数组a, 定义其长度大于3的子串为 alr={al,al+1,...,ar1,ar} , 求满足 alar=i=l+1r1ai (两边异或等于中间和) 的子串个数.

这场全是和二进制位相关的题. 官方题解用了一个巧妙的二进制剪枝办法, 两个指针的双层循环并没有变, 但是把暴力O(n2)强行优化成了O(nlog(ai)).

解法是这样的:

对一个任意的区间alr, 若中间和想要等于两边异或, 则一定有中间和的二进制最高位不大于alar的最高位, 这是本题剪枝的关键.

为了简化编程, 我们分别设定alar为最高位的参考端点, 两个方向各遍历一遍:

那么剪枝的优化程度又怎样估计呢?

实际上, 中间和的最高位超出边界元素的最高位, 是一件轻而易举的事. 先举一个最极端的例子: {...,16,16,8,8,4,4,2,2,1,1}, 在这个22n增长的例子中, 从左到右的遍历无法中途停下来, 但整个数组最多只能有60位(数据规模ai<230). 随着数组长度的增大, 容易发现, 最长的遍历区间长度也就只有60.

准确地讲, 这种区间扩张的时间复杂度是O(2log(max(ai))). 然后进一步考虑它的上层有两方向的左右端点的遍历, 再乘以2n即可.

如此可得最终解题的时间复杂度为O(nlog(ai)).

不能把比较最高位位置改成普通的比两数大小. 这就丢失了异或的特性(两数异或的最高位最高为两数中较大的数的最高位). 并不是中间和比左端点或者右端点大, 就不能等于左右端点的异或. 要把思维转变到二进制位模式上.

另外, 原来还想在求和上做点优化. 但是既然每个区间的和都需要计算再进行比对, 那么累加就是最快的(单次花费O(1)).

先建立数据结构, 再用最快也和累加相同的速度进行查询, 是彻头彻尾的反向优化. 用错地方了.


F

题目描述不太清楚, 而且好像是开放题. 先不做了.