alan23273850 的刷題筆記
e319: 小王的积木 Again!
Tags: bitmask
出處：https://zerojudge.tw/ShowProblem?problemid=e319
提交：https://zerojudge.tw/Submissions?problemid=e319&account=allllllan123456
問題：給你一堆 int 範圍內的整數，大部分的數字都出現三次，只有一個數字 $x$ 只出現一次。請你找出 $x$。
解法：這題是 zerojudge 基礎例題 d244 的簡易版，差別僅在於該例題的特異數之出現次數為三的倍數餘 2，而本題的特異數出現次數為三的倍數餘 1，因此最後取值的時候就要用 cnt[0] 而非 cnt[1]。另外本題有額外限制記憶體大小為 5 MB，故 I/O 只能使用簡單的 scanf 和 printf。
延伸：原基礎例題有限定數字為正，那為什麼這題推廣到負數之後也可以使用同樣作法呢？
1#include <cstdio>
2
3int main() {
4 int n, cnt[2]={0}; scanf("%d", &n);
5 while (scanf("%d", &n) == 1) { // FSM: 00 -> 01 -> 10 -> 11
6 cnt[1] |= cnt[0] & n; // #1 + #1 -> 1#
7 cnt[0] ^= n; // #0 + #1 -> #1 and #1 + #1 -> #0
8 unsigned t = cnt[1] & cnt[0]; // if 11, t = 1. That is, 11 -> 00 in the following two lines.
9 cnt[1] ^= t; // 1# -> 0#
10 cnt[0] ^= t; // #1 -> #0
11 }
12 printf("%d\n", cnt[0]); // take the #1 bits together
13 return 0;
14}