枚舉（Enumerate)
枚舉是最直觀的演算法，列出所有可能的解，並判斷是否符合題目要求。容易寫出，但通常時間複雜度太大無法滿足題目時限。
通常在設計枚舉找出需要枚舉的參數，並選擇是要用迴圈或遞迴方式。如果評估時間複雜度的時候發現太大時，可搭配一些技巧來降低時間複雜度。
相對地，如果有些題目測資範圍小，時間複雜度大還是可以在時限內通過題目。
UVa 10167 - Birthday Cake
給定 個點，請找出一條線 ，的兩端各有 個點 ，且 為整數。
都只有，枚舉 只有 次方種可能，每次檢查 個點，約 種可能最多枚舉 次，不會超過時限。
判斷 在 的哪一側方法是將 代入 中(這裡假設 是固定的)。
特殊枚舉型態
集合
如果題目要求和集合有關係，可利用二進位表示一個集合，第 位代表第 樣物品選或不選 (0 或 1)。時間複雜度 ，若執行時限為 秒，枚舉大小最多約 。
有遞迴和二進位兩種實現方式，前者較簡單。
| void dfs(int idx, ...)
{
...
dfs(i+1, ...); // choose ith element
dfs(i+1, ...); // not to choose ith element
}
|
| const int N = 20; // max element size
for (int i = 1; i < (1 << n); ++i)
{
bitset<N> b(i);
for (int j = 0; j < n; ++j)if(b[j])
{
...
}
}
|
AtCoder Regular Contest 061 A - Many Formulas
給定一個數字 ，可以在數字任意位置加上 + 成為算式，請輸出所有算式結果的和。
範例：
首先把整數轉成序列 ()，方便對每一位數操作。枚舉加號的放置位置，遞迴枚舉維護三個變數：位置、最後一個加號之前的和，最後一個加號之後的值。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | vector<int> v;
int sz;
long long ans;
void dfs(int idx, long long sum, long long cur)
{
if (idx == sz)
{
ans += sum + cur;
return;
}
dfs(idx + 1, sum, cur * 10 + v[idx]); // not to choose +
dfs(idx + 1, sum + cur, v[idx]); // choose +
}
int main()
{
long long n;
cin >> n;
while (n)
{
v.emplace_back(n % 10);
n /= 10;
}
reverse(v.begin(), v.end());
sz = (int)v.size();
ans = 0;
dfs(0, 0, 0);
cout << ans / 2 << '\n';
}
|
順序
如果題目要求和順序有關係，可利用 <algorithm> 內的 next_permutation 或 prev_permutation 達到枚舉元素的先後順序。時間複雜度為 ，若執行時限為 秒，枚舉大小最多約 。
下面題目用於練習如何枚舉順序：
UVa 10098 - Generating Fast
給定一個字串，一個字串有 種排序，請依據字典序大小輸出所有排序。
這題須利用到 C++ <algorithm> 函式庫的 sort 和 next_permutation (可以參考這個網站)，前者用來求出第一小排序，後者找出下一個排序。
參考程式碼
| sort(s.begin(), s.end());
do{
cout << s << endl;
} while (next_permutation(s.begin(), s.end(), comp));
|
技巧
減少枚舉維度
找出需要枚舉的參數後，有些參數可能是和結果無關，或是可由其他參數推導出，移除該參數可降低時間複雜度。
UVa10976 - Fractions Again?
給定 ，請求出所有正整數解 ，使得 。
最直觀的解法是枚舉兩個參數 ，但其實只要知道 任意一項就可推出另外一項，有根據題目我們可以得出 在 之間（當 時， )，要枚舉的範圍較小，因此我們選擇枚舉 的算法，時間複雜度為
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | #include <iostream>
using namespace std;
#define N 10005
int main()
{
int n;
while (cin >> n)
{
int ans[N][2], ar = 0;
for (int i = n + 1; i <= 2 * n; i++)
{
int r = i - n;
if ((i * n) % r == 0)
{
ans[ar][1] = i;
ans[ar][0] = (i * n) / r;
ar++;
}
}
printf("%d\n", ar);
for (int i = 0; i < ar; i++)
printf("1/%d = 1/%d + 1/%d\n", n, ans[i][0], ans[i][1]);
}
}
|
雙指標
利用兩個指標線性遍歷陣列，得出答案。「雙指標」可為兩個指標或是兩個整數型態變數紀錄位置。
UVa 11078 - Open Credit System
給定一個長度為 的序列 ，求出一組 使得 最大。
首先會直觀的想到一個 的算法：枚舉 算出結果後取最大值。
接著可以想到對於每個數字 只要和 相減即可，設立一個變數 ，，答案 和 取最大值， 更新 次，時間複雜度 。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
vector<int> v(150005);
cin >> n;
for (int i = 0; i < n; ++i)
cin >> v[i];
int minj = 0, ans = v[1] - v[0];
for (int i = 1; i < n; ++i)
{
ans = max(ans, v[i] - v[minj]);
if (v[i] < v[minj])
minj = i;
}
cout << ans << '\n';
}
|
UVa11572 - Unique Snowflakes
給定一個長度為 的序列 ，求出最長序列，當中沒有重複的數字
我們可以設兩個指標，左指標和右指標，每次迭代右指標先往前一個位置，如果左右指標之間有重複的數字，就將左指標往前一個位置，直到沒有左右指標之間沒有重複的數字。利用 set 來維護是否有重複數字，時間複雜度 。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | #include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
int t, n;
cin >> t;
vector<int> v(1000000);
set<int> st;
while (t--)
{
st.clear();
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> v[i];
}
int ans = 0;
for (int L = 0, R = 0; R < n; ++R)
{
while (st.count(v[R]))
{
st.erase(v[L++]);
}
st.insert(v[R]);
ans = max(ans, R - L + 1);
}
cout << ans << '\n';
}
}
|
折半枚舉
枚舉所有集合的時間複雜度太大，把元素拆成二份分別枚舉再合併，能夠降低時間複雜度，這種技巧稱為「折半枚舉」 (Meet in the Middle)。
AtCoder Beginner Contest 184 F - Programming Contest
給定 個數字加起來，可以選任意多個數字，數字和不超過 的情況上，最大數字和為多少?
數字分成兩個集合 ，每一堆分別枚舉所有可能的數字和並排序，獲得 。
枚舉集合 的數字 ，找出 集合內小於等於 中最大的數 。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | vector<long long> v;
void dfs(set<long long> &s, int idx, int R, long long sum)
{
if (idx >= R)
{
s.insert(sum);
return;
}
dfs(s, idx + 1, R, sum);
dfs(s, idx + 1, R, sum + v[idx]);
}
int main()
{
IOS;
int n;
long long t, ans = 0;
set<long long> s1, s2;
cin >> n >> t;
for (int i = 0, x; i < n; ++i)
{
cin >> x;
v.emplace_back(x);
}
dfs(s1, 0, n / 2, 0);
dfs(s2, n / 2, n, 0);
for (auto &x : s1)
{
auto it = s2.upper_bound(t - x);
long long y = *(--it);
if (x + y <= t)
ans = max(ans, x + y);
}
cout << ans << '\n';
}
|
UVa01326 - Jurassic Remains
給定 串英文字串，請最多可以包含幾個字串，使得這些字串內每個字元都出現偶數次。
先把每個字串轉成一個二進位，第 位表示字串有（0: 偶數，1: 奇數）個字元 i (0:A, 1:B, ...)。如果有一堆字串內每個字元都出現偶數次，那麼他們的 xor 值 。
這題關於「集合」，可用二進位枚舉，加上判斷，時間複雜度 。
使用拆半枚舉，把前 和後 字串分別枚舉，分別把結果存在不同的 map 裡面，如果兩個 map 有相同的 xor 值，代表兩個集合的字串合起來，每個字元都出現偶數次。這種做法時間複雜度為
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 | #include <bits/stdc++.h>
using namespace std;
const int N = 30;
int bitcount(int x) { return x == 0 ? 0 : (x & 1) + bitcount(x >> 1); }
int main()
{
string s;
map<int, int> tb;
int n, a[N];
while (cin >> n)
{
memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++)
{
cin >> s;
tb.clear();
for (int j = 0; j < s.size(); j++)
a[i] ^= (1 << int(s[j] - 'A'));
}
int n1 = n / 2, n2 = n - n1, x, ans = 0;
for (int i = 0; i < (1 << n1); i++)
{
x = 0;
for (int j = 0; j < n1; j++)
{
if (i & (1 << j))
x ^= a[j];
}
if (!tb.count(x) || bitcount(i) > bitcount(tb[x]))
tb[x] = i;
}
for (int i = 0; i < (1 << n2); i++)
{
x = 0;
for (int j = 0; j < n2; j++)
{
if (i & (1 << j))
x ^= a[n1 + j];
}
if (tb.count(x) && bitcount(i) + bitcount(tb[x]) > bitcount(ans))
ans = (i << n1) ^ tb[x];
}
cout << bitcount(ans) << '\n';
bool o = 0;
for (int i = 0; i < n; i++)
{
if (ans & (1 << i))
{
if (o)
cout << ' ';
o = 1;
cout << i + 1;
}
}
cout << '\n';
}
}
|
UVa10125 - Sumsets
給定一個集合，請找到最大的 滿足 ， 皆相異。
直接枚舉的複雜度式 ，把式子移項成為 ，枚舉所有 的結果，再枚舉 ，當枚舉出一組 ，就檢查是否有符合條件的 。為了要判斷是否相異，要額外紀錄位置，題目要求最大的 ，因此由大往小枚舉 。
枚舉 和 的時間複雜度 ，檢查是否有符合條件的 的時間複雜度 ，整題時間複雜度 。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 | map<int, vector<pair<int, int>>> tb;
vector<int> v;
void sol()
{
for (int i = (int)v.size() - 1; i >= 0; --i)
{
for (int j = i - 1; j >= 0; --j)
{
int diff = v[i] - v[j];
if (tb.find(diff) == tb.end())
continue;
for (auto &item : tb[diff])
{
if (item.first != i && item.first != j &&
item.second != i && item.second != j)
{
cout << v[i] << '\n';
return;
}
}
}
}
cout << "no solution\n";
}
int main()
{
int n;
while (cin >> n, n)
{
v.clear();
tb.clear();
for (int i = 0, x; i < n; ++i)
{
cin >> x;
v.emplace_back(x);
}
sort(v.begin(), v.end());
for (int i = 0; i < (int)v.size(); ++i)
{
for (int j = i + 1; j < (int)v.size(); ++j)
{
int sum = v[i] + v[j];
if (tb.find(sum) == tb.end())
{
tb.insert({sum, vector<pair<int, int>>()});
}
tb[sum].push_back(make_pair(i, j));
}
}
sol();
}
}
|
剪枝
在使用遞迴枚舉時，當搜尋到一組解答，發現該組解和其延伸的解，皆無法達到達到需求，就停止搜尋，改搜尋其他組解，該技巧叫做「剪枝」。
明確地來說，以下狀況需使用剪枝：
- 發現解答是不合法的。
- 在最佳化問題，發現無法成為最佳解。
剪枝能減少枚舉數量，降低執行時間。
Qusetion
給定一個數字 ，要你求出有幾組正整數解 ，使得 。順序不同視為相同解，例如 和 視為相同組解。
- 為了避免算到重複組合，我們讓 。
- 設目前解總和為 ，最後一項為 ，下一項 就從 開始嘗試，當嘗試到 時，就停止嘗試。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | #include <iostream>
using namespace std;
int ans, tar;
void dfs(int mx, int sum)
{
if (sum == tar)
++ans;
for (int i = mx;; ++i)
{
if (sum + i > tar)
break;
dfs(i, sum + i);
}
return;
}
int main()
{
while (cin >> tar)
{
ans = 0;
dfs(1, 0);
cout << ans << '\n';
}
}
|
UVa 10364 - Square
給定 根木棍的長度，在不折斷木棍的情況下，是否可以排出正方形?
- 如果長度和不是 的倍數，或是最長長度大於長度和 ，答案皆為否定。
- 木棍依長度從大到小排序，由長的棍子開始選能少回溯次數。
- 如果如果將上當前棍子後，累積長度大於邊長，跳過當前棍子改嘗試更短的棍子。
- 用一個
bool 陣列 紀錄那些棍子是被用過的，避免棍子被重複枚舉。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | const int MXN = 30;
vector<int> v(MXN);
bitset<MXN> used;
int n,sum, avg;
bool dfs(int curSide, int curLength, int idx)
{
// cout << curSide << ' ' << curLength << ' ' << idx << '\n';
if(curLength == avg)
{
if(curSide == 3)
return true;
++curSide;
curLength = idx = 0;
}
for (int i = idx; i < n; ++i)
{
if(used[i] || curLength + v[i] > avg)
continue;
used[i] = true;
if(dfs(curSide, curLength + v[i], i + 1))
return true;
used[i] = false;
}
return false;
}
void solve()
{
sum = 0;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> v[i];
sum += v[i];
}
sort(v.begin(), v.begin() + n, greater<int>());
avg = sum / 4;
used.reset();
if (sum % 4 || v[0] > avg || !dfs(0, 0, 0))
cout << "no\n";
else
cout << "yes\n";
}
|
延伸閱讀
更多題目