算法入門課程（2）從枚舉開始的時間複雜度優化生活

· · 算法·理论

什麼是枚舉？

在數學和電腦科學理論中，一個集合的列舉是列出某些有窮序列集的所有成員的程式，或者是一種特定類型對象的計數。這兩種類型經常（但不總是）重疊。

列舉是一個被命名的整型常數的集合，列舉在日常生活中很常見，例如「星期」可以做為一個集合，而其枚舉如星期一、星期二、 星期三、星期四、星期五、星期六、星期日，以上稱作星期的枚舉。

通俗來說，列舉就是對一個對象的所有可能取到的值的集合

——Wikipedia

其實枚舉的概念應該是廣為人知的，在上一節課的習題中也出現了這個概念。

枚舉其實是所有算法中最基礎的一種，其實想必無需講解大家也都能理解，這節課的主要目的是拋磚引玉，讓大家去初步自己探索怎麼找到時間複雜度更為優秀的做法，從而對 OI 有更深刻的理解。

因此，某種意義上這節課更像是給腦子做做體育鍛煉？

習題 Part I

三元一次方程求整數解

給定正整數 A,B,C,K,N，求：

\begin{cases} Ax+By+Cz=K\\ x,y,z\in \mathbb{R}\cap[1,N] \end{cases}

的所有正整數解。

注意到 x,y,z 三個值都是可枚舉的，直接枚舉即可，時間複雜度為 \mathcal O(N^3)。

參考代碼：

for(int x=1;x<=N;x++)
for(int y=1;y<=N;y++)
for(int z=1;z<=N;z++)//枚舉三個未知數
{
    if(A*x+B*y+C*z==K)//判斷條件
        cout<<x<<' '<<y<<' '<<z<<endl;
}

統計最大正方形

給你一個 N\times N 的矩陣 A，你需要求出其中的一個其中的元素之和最大的正方形。

正方形是長等於寬的子矩陣。

子矩陣顯然是可以有限的，所以是可以枚舉的，那麼我們怎麼刻劃子矩陣來枚舉呢？

其實有兩種方法：

但其實，這題枚舉子矩陣是有很多無效枚舉的，因為我們要求的形狀是正方形，也就是 h=w。

我們可以選擇第二種枚舉方法這樣就可以只枚舉邊長了，那麼枚舉的時間複雜度為 \mathcal O(n^3)。

那麼枚舉正方形中的一個元素就簡單多了，我們直接累加和，然後拿總和拿來統計即可！

for(int t=1;t<=n;t++)//這是邊長
for(int x=t;x<=n;x++)
for(int y=t;y<=n;y++)//枚舉右下角
{
    int Sum=0;
    for(int i=x-t+1;i<=x;i++)
    for(int j=y-t+1;j<=y;j++)//枚舉矩陣內的點
        Sum+=A[i][j];//累加總和
    Ans=max(Ans,Sum);
}

其實這題可以做到 \mathcal O(N^3)，給你一點提示：如何快速計算一個正方形的和？我們下節課將科普這個東西。

習題 Part II

從這一部分開始我們要思考怎麼優化枚舉，事實上，第一個問題有很大的優化空間，你可以試著想一想。

統計符合條件的數對 1

給定一個正整數 n 與長度為 n 的正整數數組 A。

請統計所有滿足 A_i=A_j(j\leq i) 的二元組 (i,j) 的數量。

我們知道枚舉二元組的時間複雜度為 \mathcal O(N^2)，但是這個複雜度並不夠優秀，我們可以通過分析條件來觀察？

首先，我們只需要計數而不需要真的找出來所有的點對，其次，這個條件的形式很簡單啊。

for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
    if(A[i]==A[j])
        Ans++;    
}

以上是暴力的程序，其實仔細觀察，第二層循環做的事情就是找出 j\in [1,i] 中滿足 A_j=A_i 的 j 的數量。

事實上你會發現這樣很笨，因為完全可以將前面的某個數字出現的次數記錄在一個數組中呀！

嗯，你說的很有道理，事實上，如果我們將一個數字的出現次數記錄下來，那麼用於記錄次數的這個數組我們習慣稱為桶，這是一種很重要的思路，將來我們會經常用到。

那麼我們將“往前枚舉統計某一種值的次數”換成“用桶來記錄某種值的出現次數”就可以了，時間複雜度變為 \mathcal O(n)。

for(int i=1;i<=n;i++)
{
    Cnt[A[i]]++;
    Ans+=Cnt[A[i]];
}

統計符合條件的數對 2

給定一個正整數 n 與長度為 n 的正整數數組 A。

請統計所有滿足 i+j=A_i+A_j(j\leq i) 的二元組 (i,j) 的數量。

我們知道枚舉二元組的時間複雜度為 \mathcal O(N^2)，但是這個複雜度並不夠優秀，我們可以通過分析條件來觀察？

注意到式子兩邊都包含 i,j 兩個變量，這說明求解哪一邊都需要知道 i,j 的確切值才可以。

能不能變形使得枚舉一個量就可以呢？顯然可以，上面的式子我們可以變形為 A_i-i=A_j-j。

這個形式好看多了，我們設數組 B 滿足 B_i=A_i-i，我們發現對於 B 數組問題可以轉化為上一道題目。

Tips:B_i 可能為負數，且這題並沒有約束 A_i 的數據范圍，不方便開數組，解決辦法是使用 STL 容器 map 或者 unordered_map。

統計圓內的整點

在平面直角坐標系上有一個圓，圓心為 (a,b)，半徑為 R，求這個圓（包括圓上的點）包含了多少橫縱坐標都為整數的點。

顯然的思路是枚舉整點然後計算整點到圓心距離是否小於等於 R，滿足則計數。

我們顯然不能枚舉平面直角坐標系上的所有整點，這不是不可枚舉的，但是我們稍微明確一下條件就可以了。

根據簡單數學知識我們知道整點 (x,y) 必然滿足 x\in[a-R,a+R],y\in[b-R,b+R]。

我們枚舉這個範圍內的所有整點 (x,y) 即可，時間複雜度為 \mathcal O(R^2)，並不夠優秀。

仔細思考，對於一個直線來說，圓和直線的交集必然是一條線段、一個單點、空集。

後兩種情況我們可以不用管，那麼線段怎麼理解呢？說明一個固定的橫坐標，圓內整點的縱坐標必然是一段連續的數字。

高中生應該都知道題目中的圓可以用以下表達式表示：

(x-a)^2+(y-b)^2=R^2

如果我們已經枚舉了橫坐標 x，那麼自然可以得到 y 的最大值 \max 與最小值 \min（顯然小數取整即可）。

那麼對於這個 x，需要統計的整點數量就是 \max-\min+1。

這樣時間複雜度可以做到 \mathcal O(R)。

統計符合條件的數對 3

給出一個長度為 n 的數組 A，請找到一個數對 (i,j) 其中1\leq i<j \leq n,A_i<A_j，使得A_i+A_j 最大。

這題其實純純詐騙題（如果一個題看似複雜，其實經過一個簡單處理之後變得很簡單，就戲稱為詐騙題）。

我們感覺 A_i<A_j 的限制很難做到，但其實我們這麼想，如果我枚舉了 A_i，兩個條件都只有一個目的：

所以其實我們只需要記錄後面最大的數字就可以了，記錄一個變量，然後我們倒序枚舉 i 即可。

int Mx=0;
for(int i=n;i>=1;i--)
{
    if(Mx>A[i])Ans=max(Ans,Mx+A[i]);
    Mx=max(Mx,A[i]);
}

時間複雜度為 \mathcal O(n)。