题解 | 异或和

import sys
class read:
    def __init__(self):
        self.num=0
        self.idx=0
        self.bytes=b''
        
    def get_next_byte(self):
        if self.idx>=len(self.bytes):
            self.bytes=sys.stdin.buffer.read(1<<20)
            self.idx=0
        self.idx+=1
        return self.bytes[self.idx-1]
    
    def get(self):
        while True:
            b=self.get_next_byte()
            if 48<=b<=58:
                self.num=self.num*10+(b-48)
            else:
                t=self.num
                self.num=0
                return t

r=read()
n=r.get()
ans=0
for _ in range(n):
    ans^=r.get()
print(ans)

#include <iostream>
#include <cstdio>
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int main() {
    int n = read();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x = read();
        ans ^= x;
    }
    printf("%d\n", ans);
    return 0;
}

核心思路

出现次数为奇数个的数字的异或和 = 整个数列所有数字的异或和

原理

偶数个相同数字异或 = 0

奇数个相同数字异或 = 该数字本身

因此所有数字异或时，偶数次出现的会抵消，奇数次出现的会保留

本题需要一个一个读入（并且使用快读），防止爆内存

代码如上