当前位置：首页 > news >正文

（异或相消）猫猫数字异或和

news 文章来源：https://blog.csdn.net/m0_72496300/article/details/130556288 2024/11/15 22:50:25

E - Red Scarf (atcoder.jp)
刚入坑写的一道题被我拉出来对比分析了

我的思路：

垃圾运气选手凭借直觉乱搞猜出来的，没有思路。

题解思路：

由问题陈述中XOR的定义，我们可以看出计算3个或更多整数的XOR可以以任意顺序进行；例如，对于任意三个整数a、b、c，都有a ⊕ b ⊕ c = b ⊕ c ⊕ a = (a ⊕ b) ⊕ c = c ⊕ (a ⊕ b)。我们还可以看到，a ⊕ a = 0对所有整数a成立。结合起来，我们可以断言a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。

现在让我们继续讨论原问题。ai是猫喜欢的数字。设bi为第i只猫的整数。在这里，ai = b1 ⊕ . . . ⊕ bi−1 ⊕ bi+1 ⊕ . . . ⊕ bN。这可能有点突然，但我们将计算给定的N个值a1，…，aN的异或值。此值可以转换如下：

在这里插入图片描述

因此，对于每个i，似乎有bi = S ⊕ ai，因此问题已解决。问题陈述中有一个限制条件，“存在一组整数组合在围巾上与给定信息一致”，“输出”部分说明：“如果有多个可能的解，您可以打印任何一个；”然而，通过这个解决方案，对于任何N个整数a1，…，aN的组合，总是存在一组唯一的整数b1，…，bN使它满足。

流程：

切入点：n为even，
通过思考这个条件的意义，再结合ai是不包括bi的异或和，可以发觉ai的异或和有n-1个bi，奇数次，成对抵消后，剩下一个bi。

异或交换律-> 所有ai的异或，得到所有bi的异或 ->然后再异或ai，就得到了当前数字bi。

如果题目说有多个解，一般存在一种通解。

套路：异或类问题：

前提：

此类问题的前提似乎都非常简单
就是题目中出现了异或这个关键词。

应对：

even次数的异或可以互相抵消，所以一般可以通过列表达式来得到一种互相抵消得到所求的方法。

把刚入坑刷的一道题拉出来对比分析。

1）法斯特异或。（fast异或）

前提：求区间异或和。

：郑轻22级新生C语言周赛(3)——命题人：宋江、张永林、张纪龙复盘_22级c语言考试,我的作答:_Kanna_STELLA的博客-CSDN博客
求0到n的异或和，存在规律
n%4 == 0 时，结果是n，
n%4 == 1 时，结果是1
n%4 == 2 时，结果是n+1
n%4 == 3 时，结果是0
分别算出0-l和0-r的异或和，
再把二者异或起来，even次数的元素抵消，最终得到
l~r的异或和。

2）异或类问题，通过列表达式来找寻思路

#位运算 #异或