Preface
好耶,少见的难题。
题面
https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/
题解
大部分题解已经提到了:就是下面这个结论。
结论:最终构造出来的数列以
证明:
由题设:
所以我们有:
根据异或的交换律与结合律:
故
接下来思考一下最终构造出来的数列满足什么特征:
- 以
为一个周期 - 第一个周期异或和为 0
接下来看图说话:
在上图中
那么我们不妨一组一组按列处理,接下来是状态的设法:
思考转移方程:都是从上一列转移,但是有两种转移方式:
- 第
列全部修改 - 第
列部分修改,部分保留
设
注意:全部修改仍然有可能比部分修改更优,这是因为本题不是简单的贪心。具体可以见下一小节,我们可以构造出反例,证明贪心是错误的。
此外,我们还需要注意初值的设定。
构造贪心的反例
贪心?怎么贪心?那当然是每一列选择相同数量最多的,再把这个数量排序,相同数量最少的一列全部改变,使得最后异或值为 0。
但是这个反例是非常容易构造的。
第一列:
第二列:
第三列:
按照之前说的贪心,我们会选保留
4 条评论
博主看来是计算机科班生,不知道是本科生还是研究生呢?
是高中生 高三(
很强,对于算法方面的储备已经远超很多一流211大学科班生的水平了
嘛.... 毕竟以前是搞奥赛的(NOIP 省一退役