題目簡介

• 來源：1033 貪吃的松鼠 - CCUT應用OJ，魔改自 Leetcode 137. 只出現一次的數字 II。
• 題意：給定長度為 \((n-1)\times m+k\) 的正整數序列，其中 \(n-1\) 個數出現 \(m\) 次，有且僅有 1 個數出現 \(k\) 次，輸出這個出現 \(k\) 次的數。
• 數據范圍：\(n\le 10^5,1<m\le 9,k<m\)，序列值域上界為 \(2^{30}\)；時空限制：3s/256M
• 注：若無特殊說明，博主的代碼模板如下。博主通過定義solve函數處理多組測試用例。博主在后文均只給出solve函數。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ln '\n'
#define fi first
#define se second

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    while(cin>>...){//此處即為處理多組測試用例，...換為實際輸入變量
       solve();
    }
    return 0;
}

題解

樸素想法

定義權值數組 \(cnt[i]\)，用于統計 \(i\) 的出現次數，之后遍歷 \(cnt\) 數組，找出出現 \(k\) 次的元素并輸出即可。
但由于序列值域上界高達\(2^{30}\)，以 \(\texttt{int}\) 型數組為例，需約 \(4\text{GB}\) 內存，因此無法開下這么大的數組。此想法不可行。

解法1：哈希表

如果你學過 C++，那么則可使用 unordered_map一發AC。

void solve(){
    unordered_map<int, int> cnt;
    int id;
    for (i64 i = 0; i < 1LL * m * (n - 1) + k; i++) {
        cin >> id;
        cnt[id]++;
    }
    for (auto i : cnt) {
        if (i.se != m) {
            cout << i.fi << ln;
            break;
        }
    }
}

解法2：二進制優化

• 核心思想：若除了一個數以外，其余數都出現了相同次數(設 \(m\) 次)，則可通過統計二進制每一位上 \(1\) 的出現次數，并對 \(m\) 取模，從而得到那個特殊數。
• 數學證明：
  • 考察整數\(x_i\)，將其按二進制進行位權展開(由于題中值域上界為\(2^{30}\)，故\(31\)位足夠表示)：\(x_i = \sum_{j=0}^{30} b_{i,j} \cdot 2^j, \quad b_{i,j} \in \set{0,1}\)
  • 統計每一位上 \(1\) 出現的次數：\(A_j = \sum_{i=1}^{m(n-1)+k} b_{i,j}\)，其可被拆為兩部分：\(A_j = \underbrace{\sum_{x \in S_m} m \cdot b_{x,j}}_{\text{出現 m 次的數貢獻}} + \underbrace{k \cdot b_{x^*,j}}_{\text{出現 k 次的異常數貢獻}}\)
  • 模運算具有如下性質：\((a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m\)，因此通過取模即可將異常數的貢獻保留。
  • 對每一位計數 \(A_j \bmod m\)：\(A_j \bmod m = \Big(\sum_{x \in S_m} m \cdot b_{x,j} + k \cdot b_{x^*,j}\Big) \bmod m\)，并且 \(m \cdot b_{x,j} \equiv 0 \ (\text{mod } m)\) 對任何 \(b_{x,j} \in {0,1}\) 都成立。故得：\(A_j \bmod m = (k \cdot b_{x^*,j}) \bmod m\)
  • 由于題目給出 \(k < m\)，故：
    \[k \cdot b_{x^*,j} \bmod m =\begin{cases}0, & b_{x^*,j} = 0 \\k, & b_{x^*,j} = 1\end{cases} \]
    得證。

也就是說，模運算把“其他所有出現 m 次的數”完全消掉，只剩下那個出現 k 次的數的二進制痕跡。將其轉換為十進制，即為最終答案。

void solve(){
	int a[35]={0};
    for(int i = 0;i < m * (n-1) + k ; i++){
        int num;
        scanf("%d",&num);
        for(int j = 0; j < 31; j++){
            if(num & (1 << j)) a[j] ++; // 循環左移，統計二進制中每一位上1的出現情況
            a[j] %= m;// 邊統計邊取模，防止爆了
        }
    }
    int ans = 0;
    for(int j = 0;j < 31;++j)
        if(a[j] != 0) ans += pow(2,j); // 還原出異常值即可
    printf("%d\n",ans);
}