洛谷 P1469 找筷子

題目描述

經過一段時間的緊張籌備，電腦小組的“RP餐廳”終于開業了，這天，經理LXC接到了一個定餐大單，可把大家樂壞了！員工們齊心協力按要求準備好了套餐正準備派送時，突然碰到一個棘手的問題，筷子！CX小朋友找出了餐廳中所有的筷子，但遺憾的是這些筷子長短不一，而我們都知道筷子需要長度一樣的才能組成一雙，更麻煩的是CX找出來的這些筷子數量為奇數，但是巧合的是，這些筷子中隻有一隻筷子是落單的，其餘都成雙，善良的你，可以幫CX找出這隻落單的筷子的長度嗎？

輸入輸出格式

輸入格式：

第一行讀入一個數N，它代表CX找到的筷子的根數。

第二行是N個用空格隔開的數，代表筷子的長度。

輸出格式：

一行，落單的筷子的長度。

輸入輸出樣例

輸入樣例#1：

9
2 2 1 3 3 3 2 3 1
      

輸出樣例#1：

2      

說明

對于80%的資料，N<=100000；

對于100%的資料，N<=10000000。

吐槽

　　今天出聯考成績，我甚至保底的成績都沒達到……不說了……做道入門題緩和一下心情。

解題思路

　　看到這題的第一想法，快排，然後兩個兩個地往後推，複雜度$O(NlogN)$，炸了（雖然資料水可以過）。第二個想法，桶排，然後掃一遍，找出奇數，但是不知道最長的筷子有多長啊，emmmm，離散化吧，複雜度$O(NlogN)$，又炸了（雖然資料水，也可以過）。然後……居然就這樣沒思路了。看題解，學習到一個以前知道後來忘了的東西——a^a=0，0^a=a（^異或，即Xor）。于是把所有長度異或起來，最後結果就是答案了。

源代碼

1 #include<stdio.h>
 2 
 3 int main()
 4 {
 5     int ans=0,n;
 6     scanf("%d",&n);
 7     for(int i=1,j;i<=n;i++)
 8     {
 9         scanf("%d",&j);
10         ans^=j;
11     }
12     printf("%d",ans);
13     return 0;
14 }