题解 P1469 【找筷子】

· · 题解

废话不多说，直接步入正题

算法一：用一个桶来标记一下，最后判断桶值%2为1(即多出来一只)的输出即可。
复杂度较大(注意：这里的较大是相对这道题其他算法所言的)
占用空间较大
(内存的限制已经把这个方法pass掉了)
算法二：sort一下，然后从头开始搜，搜到某个数的个数%2为1，则输出并跳出函数。
复杂度中等且不稳定
占用空间中等(很明显已经被pass了)
在描述算法三之前先普及一下位运算。
|(或)两个二进制数的或运算，即两个数的某个相同的位置上有1为1
例如：
1000101
1001111
1001111即为两个数的或运算值(对于第1,4,5,6,7位上在两个数中找得到1)
注意：若两个数的位数不相同，少的那个数用0补齐
例如：
1000111             1000111
10011  运算可以看成 0010011这两个数来运算
感性理解：对于每个位置上1为显性基因
怎样区分|与&运算：|符号像1，即1为显性基因(即或运算)
&(与)与|相反，0为显性基因，不理解的看上面的内容理解
^(异或)对于每个位置上进行不进位加法(进制为二进制)，即1+1=0,1+0=1,0+0=0
然后
算法三：对于两个相同的数，他们异或值为0
证明：两个相同的数转化为二进制数必然也相同，上面已经说过，对于每位上的加法，无非就两种0+0,1+1值均为零
当我们把所有输入的数异或一遍，是不是相同的数都齐齐殉情了，这就变成了0^那个多余的数，而某个数异或0得到的值还是它本身
即ans为所有数的异或值

AC代码(输入直接cin好像会T一个点，所以输入可以用printf或快读，也可以用如下优化)

#include<bits/stdc++.h>
#define itn int
#define ll long long
using namespace std;
int main(){
    int n,ans=0;
    ios::sync_with_stdio(0);cin.tie(0);//优化，可以减少输入时间复杂度
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        ans^=x;
}
    cout<<ans;

    return 0; 
}