[题解]异或三角形|2021蓝桥杯国赛|xor triangle
此文使用了mathjax,请等待公式加载
这是2021年蓝桥杯国赛A组C++的一道题目。
当时没有来得及写暴力对拍,只是测了示例过了,也就是说不确定是否正确。
首先考虑异或操作的特性,可以交换,所以不妨考虑 $a \geq b \geq c$的情况。随后根据三个数字异或为0,不难看出每一位的异或结果都是0。这也就是说每一位的三个数字只有两种可能,2个1一个0或三个0。不难知道a的首位一定是1,所以另外两个数字在此处必为一1一0。可由此用反证法证明3个数必不相等:
如果三个数相等,二进制下首位必相等,与首位一1一0矛盾。如果只有两个数相等,那么这两个数在2进制下必定同1同0。为了满足三个数异或为0,第三个数每一位都只能为0,得出第三数为0,无法形成三角形。