alan23273850 的刷題筆記
d244: 一堆石頭
Tags: bitmask
出處：https://zerojudge.tw/ShowProblem?problemid=d244
提交：https://zerojudge.tw/Submissions?problemid=d244&account=allllllan123456
問題：給你一堆正整數，大部分的數字出現的次數都是三的倍數，只有一個數字 $x$ 出現的次數是三的倍數減一。請你找出 $x$。
解法：這題的標準解法實在巧妙！一般人大概會想到 map 的解法，但是好好利用位元運算其實可以在線性時間內完成本題。考慮 int 範圍下的某個特定位元，對於那些出現次數剛好為三的倍數的數值，它們在該位元的總和也必為三的倍數；那剩下那一個出現次數為三的倍數減一的數字 $x$，如果它在該位元的值為 0，該位元的總和仍然為三的倍數；反之如果它在該位元的值為 1，就會造成該位元的總和變成三的倍數再餘 2。由此可見，只要在輸入每個數字的時候都順便維護每個位元各自的總和分別除以 3 的餘數，最後就能判定餘 0 的位元為 $x$ 的 0-bit，餘 2 的位元為 $x$ 的 1-bit。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 unsigned n, cnt[2]={0};
6 while (cin >> n) { // FSM: 00 -> 01 -> 10 -> 11
7 cnt[1] |= cnt[0] & n; // #1 + #1 -> 1#
8 cnt[0] ^= n; // #0 + #1 -> #1 and #1 + #1 -> #0
9 unsigned t = cnt[1] & cnt[0]; // if 11, t = 1. That is, 11 -> 00 in the following two lines.
10 cnt[1] ^= t; // 1# -> 0#
11 cnt[0] ^= t; // #1 -> #0
12 }
13 cout << cnt[1] << '\n'; // take the 1# bits together
14 return 0;
15}