P1469. 找筷子

发表于 分类于 阅读次数： Waline： 本文字数： 131 阅读时长 ≈ 1 分钟

考点

  • 位运算

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int n, ans, in;

int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  while (n--) {
    cin >> in;
    ans ^= in;
  }
  cout << ans;
  return 0;
}

思路

相同的数异或为零，那么剩下的就是答案了

一开始想着用哈希表计数来着，但是数太多直接炸了内存...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int n, in;

int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> in;
    ++mp[in];
  }
  for (auto it = mp.begin(); it != mp.end(); ++it) {
    if (it->second % 2) {
      cout << it->first;
      break;
    }
  }
  return 0;
}