洛谷-P1469 找筷子 (位运算)

题意:给你一组数,求数组中唯一的出现次数为奇数的那个数.
题解:这题其实直接桶排一下就行了,但是最后一个点会TLE.

后来了解到这题可以用位运算来解决:

^(异或)运算符:用于比较两个二进制数的相应位。在执行按位异或运算时，如果两个二进制数的相应位都位1或两个二进制数的相应位都位0，则返回 0；如果两个二进制数的相应位其中一个为1，另一个为0，则返回 1.

所以很明显:a^a=0,直接讲所有数异或运算,最后得到的数就是答案.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int n,x;

int res;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n;

     while(n--){

         cin>>x;

         res^=x;

     }

     printf("%d\n",res);

    return 0;

}

巴特西

洛谷-P1469 找筷子 (位运算)

最新文章

热门文章