\(n\le 20\) (O
\(n\le 30, 50...\) (X
選擇合理範圍的的維度,
窮舉所有可能的答案
給你一個數字 \(N\),你要輸出所有正整數 pair(a, b)
使得 a/b = N, a, b 為五位數,且所有數字不能重複
以 N = 62 為例
答案有兩組
79546 / 01283 = 62
94736 / 01528 = 62
而 N = 61 沒有任何符合的解
窮舉所有 \(a, b\) 可能的範圍去判斷有沒有符合的
而可能出現的範圍為 00001 ~ 99999 因此 C 約為 10^5
複雜度 \(O(C^2) \to 10^{10}\) TLE
由於每種數字會出現剛好一次因此窮舉所有排列
0123456789 ~ 9876543210
再去判斷分出來的 a, b 所得到的 a/b 會不會等於 n
複雜度 O(N!)
10種數字,因此 \(10! = 3,628,800\)
複雜度是好的 AC!
生成所有排列可以使用 c++ STL 的 next_permutation()
把判斷函數寫在外面,程式碼比較乾淨
for(int i=0;i<10;i++){ vec.push_back(i) } do{ if(check(vec)){ ans.push_back(vec); } }while(next_permutation(vec.begin(),vec.end()));
只窮舉 b 去判斷 b * n 是否等於有相對應的 a
for(int b=0;b<100000 && b*n<100000;b++){ if(is_different_digit(a,b)){ ans.push_back(make_pair(a, b)); } }
只窮舉 b
複雜度跟 b 的範圍大小有關 \(10^5\)
給你三個數字 \(A, B, C (1 \le A, B, C \le 10000)\)
已知
\(x + y + z = A\)
\(x * y * z = B\)
\(x^2 + y^2 + z^2 = C\)
求出 \(x, y, z\),如有多組解則輸出 tuple(\(x, y, z\)) 字典序最小的
如果直接窮舉所有可能的 \(x, y, z\)
複雜度 \(O(10000^3) \to 10^{12}\) TLE
\(A, B, C (1 \le A, B, C \le 10000)\)
而如果只看第三個式子
\(x^2 + y^2 + z^2 = C\)
會發現當 \(x, y, z\) 超過\(\sqrt{10^5}\) 之後就會出過 \(C\)
所以 \(x, y, z\) 的範圍只會在 \([1, \sqrt{10000}]\) 之間
因此可以直接窮舉 x, y, z 在 \([1, \sqrt{10000}]\) 的範圍
複雜度 \(O(\sqrt{C}^{3}) = 10^6\)
枚舉多維度數值的方法。遞迴窮舉所有維度,並且在過程中避免不必要的窮舉(剪枝),以降低複雜度。
由於回溯法是窮舉所有維度,複雜度通常為指數 如 \(O(a^b)\)
因此如果是暴搜提通常題目的範圍都很小,像是 \(n\le 50\) 之類
遞迴找答案時,中間有可能遇到很多不合理的狀態(超出邊界) 而如果當下狀態不合法或者不可能走到答案,則可以直接跳過當下狀態,以避免不必要的窮舉
以 \(O(2^n)\) 為例,會發現在適當的地方剪枝可以減去很多不必要的可能
給你一個 8X8 的棋盤,要放 8 個皇后
而要讓這 8 個皇后彼此都不會攻擊到
而皇后可以攻擊同行同列以及同左右斜線的棋子
問你有幾種擺法 ?
上圖為一組合法解
總共 64 格,每次選 8 格判斷合法性
總共 \(\binom{64}{8}\) 種 = 4,426,165,368
\(\to\) TLE
所有皇后彼此不能攻擊到,代表同一行最多只能有一個皇后
因此可以窮舉每一行放一個皇后,並且避免不必要的窮舉
如果已經有同一列或者對角線有放皇后,則同一列、左右斜線不能再放
以第三行為例,能放的位置為下面四格,上面都會被其他皇后攻擊
總共 8 行,每行能放的位置隨著前面已經放的會越來越少
第一行可以放 8 個,第二行 7 個 …
複雜度 O(N!)
8! = 40,320
因此用陣列紀錄是否同一列、左右斜線是否有放過
斜線總共有 2N-1 條
同一條左上到右下的斜線,則x+y會是同一個值
同一條右上到左下的斜線,則x-y會是同一個值
bool row[N], add[15], sub[15]; void backtracking(int x){ if(x == 8){ ans++; // 遞迴到最後結束 return; } for(int i=0;i<8;i++){ if(!row[i] && !add[x+i] && !sub[(x-i+15)%15]){ row[i] = add[x+i] = sub[(x-i+15)%15] = 1; //標記放置的位置 backtracking(x+1); // 換下一行 row[i] = add[x+i] = sub[(x-i+15)%15] = 0; //移除放置的位置 } } } int main(){ backtracking(0); }
給你 7X7 的矩陣,一開始在左上角 (0, 0) 的位置
給你一條部分未知的路徑,從起點開始要走到右下角,
問你有幾條路徑可以使得每個點都剛好走一次?
??????R??????U??????????????????????????LD????D?
201
遞迴每格判斷是否為未知路經,是未知路徑的話窮舉四個方向
最差的情況每格都是 ?
複雜度為 \(O(4^{49} \times 49)\) // 49格窮舉四種方向, 每次遞迴傳下去字串 path 長度為 49
int ans = 0; bool calc(string path){} void dfs(int x, string path){ if(x == 49) ans += calc(path); if(path[x] != '?') dfs(x+1, path); else{ for(char i : "LRUD"){ path[x] = i; dfs(x+1, path); } } }; int main(){ cin >> path; dfs(0); cout << ans << endl; }
哪些部份可以省略 ?
void dfs(int x, string path){ }
會發現字串 path 可以放全域變數 不用每次遞迴都重新傳一次
直接修改全域變數的值,遞迴後記得要改回來原本的值
string path; void dfs(int x){ if(x == 49) ans += calc(); if(path[x] != '?') dfs(x+1); else{ for(char i : "LRUD"){ path[x] = i; dfs(x+1); path[x] = '?'; } } }
複雜度減少了每次傳參數的時間變成 \(O(4^{49})\)
走到甚麼情況可以不用繼續往下走
再想想還有什麼其他剪枝?
走的時候順便紀錄當前位置,如果超出邊界則不為合法解
void dfs(int x,int y,int d){ if(x<0 || x>=7 || y<0 || y>=7){ return; } }
紀錄每個點是否走過,走過視為牆壁
可以用一個 bool 陣列紀錄是否走過
bool vis[10][10]; void dfs(int x,int y,int d){ if(vis[x][y]) return; vis[x][y] = 1; ... }
當走到的格子前面那格為牆壁,但左右都還沒走過時,
代表會將還沒走過的區域分成兩塊,則代表會無解不必繼續走下去
除了以上四種剪枝,
再想想還有什麼其他剪枝 ?
通常這種爆搜的題目總狀態數都不會太大
以這題為例 \(7\times 7\),最多只有 49 種狀態
所以當題目 \(n\) 很小就要想想看是不是爆搜題
接著就是想要怎麼剪枝,避免所有不必要的窮舉
把每種狀態都當成一個節點,從狀態轉移當成一條邊
轉換成圖論問題去 BFS/DFS 求解
給你一段長度為 \(n (n \le 9)\) 的 permutation
每次操作可以選擇一段連續區間剪切到其他位置,求最少需要幾次可以讓序列變成升序序列
sample input
2 1 5 3 4 6
sample output
2
1 剪下移到最前面 [2, (1), 5, 3, 4, 6] \(\to\) [(1), 2, 5, 3, 4, 6]
(3,4) 剪下移到最前面 [1, 2, 5, (3, 4), 6] \(\to\) [1, 2, (3, 4), 5, 6]
總共 \(n! (n \le 9)\)種狀態,代表節點數 362,880 個節點
每次可以選一段區間,移到另一個地方,總共有 \(\binom{n+1}{2}\) 個不同的區間
且每次可以插入到 n-2 種不同的位置,邊數量為 \(n!\binom{n+1}{2}(n-2)\)
轉換圖論 BFS 找最近距離複雜度 \(O(V+E) = 114,307,200\)
可以再搭配一些剪枝
用當前步數判斷是否可能達到最佳答案
先定義非連續數量 h :對於一個序列 \(a\)
有幾個 \(i (1\le i < n)\) 符合 \(a[i]+1 \ne a[i+1]\)
序列 [1,4,2,3] 的 h 為 2
最終要使得序列為升序,也就是 h = 0(序列[1, 2, 3, 4, 5, 6, 7, 8, 9])
而對於一次的操作, h 最多減少 3
改變 A,B,C 區塊結尾的後繼
而最差的情況下最多需要做 8 個操作(序列[9, 8, 7, 6, 5, 4, 3, 2, 1])
每次最多可以讓 h 減少 3
假設我們做需要做最多的次數為 maxd,而當前做的次數為 d
若還可以做的次數 (maxd - d) * 3 < h
代表每次改變最多的非連續數量也就是3次,而用剩下的次數還做不完的話
則沒必要繼續做下去,因為一定不可能比答案小
則可以直接剪枝掉
void dfs(int x,int d){ if((maxd - d)*3 < calc_h()) return; }
可以用一個 map 把整個序列存起來,紀錄當前序列最少要幾次可以走到
如果比原本的次數還要多 那就沒必要繼續走下去了
否則更新原本的答案
map<vector<int>, int> dis;
void dfs(vector<int> arr, int d){
if(dis.count(arr) && dis[arr] <= d) return;
dis[arr] = d;
}
對於狀態我們通常會壓縮後再存起來
以上面題目為例,狀態為一個序列 [ 2, 1, 5, 3, 4, 6 ]
則其實我們可以直接把他壓成一個整數變成 215346 去代表這個狀態
n! 種可能的序列,每個序列有 n 個數字
原本要花 n! * n 的空間去儲存,現在只需要儲存 n! 個整數即可
而在每次BFS/DFS會判斷是否走過,如果狀態是用序列儲存需要花 \(O(N)\) 時間去比對是否相同,而轉成數字儲存只需要花 \(O(1)\) 即可比對是否相同
map<vector<int>,int> \(\to\) map<int,int>
題單可以用到此技巧來儲存
以八皇后為例,原本是用陣列去儲存是否走過也可以改成用整數
{0,1,0,0,0,1,1,0} 代表第1,5,6 (0-base) 格有走過
而直接用一個整數存起來 mask \(=70_{10} = 01000110_{2}\)
空間複雜度存原本 \(O(N)\) 變成 \(O(1)\)
要查詢第 \(i\) 格是否被用過則直接位元運算判斷 (mask>>i&1) 是否為 \(1\)
int 可以存 32 個位元
long long 可以存 64 個位元
有些很難的題目有時可能沒辦法在時限內AC,有一個毒瘤的技巧是時間剪枝
在程式一開始記錄時間,當在執行遞迴過程中判斷執行時間,當快到Time Limit 時,則直接回傳最佳值當作答案
#define SECs ((double)clock() / CLOCKS_PER_SEC) double startTime; void dfs(int x){ if(SECs - startTime > 0.95) return; } int main(){ startTime = SECs; dfs(0); }
通常不會用到時間剪枝
而且時間剪枝每次要判斷時間所以會增加運算成本
把所有可能分兩半,分別暴力枚舉所有可能
Given a set \(s\) of integers \(s_i\), your task is to determine how many different non-empty subsets sum up to a target value \(T\).
\(1 \le N \le 40\)
\(-10^9 \le s_i, T \le 10^9\)
6 0
-1 2 -3 4 -5 6
4
(2, 4, -1, -5), (2, 6, -5, -3), (4, -1, -3), (6, -5, -1)
sum up = 0
窮舉第 x 個數字要不要使用,複雜度 \(O(2^N)\)
void dfs(int x, int sum){ if(x == n) ans += sum == target; dfs(x+1, sum) // 不用第 x 個數字 dfs(x+1, sum+value[x]); // 用第 x 個數字 }
for(int i = 0; i <(1<<n); i++){ int sum = 0; for(int j = 0; j < n; j++){ if(i>>j&1) sum += arr[j]; } ans += sum == target; }
每個數字選或不選,總共有 \(2^N\) 種可能
N 的大小為 40
\(2^{40} = 10^{12} >> 10^8\)
TLE
把每種數字選或不選轉換成圖
以前三個數字 -1,2,-3 為例
狀態數會隨著 n 越大呈現指數成長
而如果我們把狀態拆兩半,一半重頭開始窮舉,一半從尾巴
則狀態數會從 \(2^n\) 變成 \(2 \cdot 2^{\frac{n}{2}}\)
\(\to\)
N = 40
\(2^{\frac{40}{2}} = 10^6\)
分別算完兩邊 subset 的答案儲存起來後,
判斷兩邊算出來的答案能不能加起來剛好等於 target value
(有部分細節沒處理)
map<int,int> mp; for(int i=0;i<(1<<(n/2));i++){ //iterate all subset of first half int sum=0; for(int j=0;j<n/2;j++){ if(i>>j&1) sum += arr[j]; // sum up all selected element } mp[sum]++; // save the sum to the STL map } for(int i=0;i<(1<<(n-n/2));i++){ //iterate all subset of second half int sum=0; for(int j=0;j<n-n/2;j++){ if(i>>j&1) sum += arr[n/2+j]; } if(mp.count(t-sum)) ans += mp[t-sum]; }
此題為2021-12-21 CPE第七題
了解概念就可以 10 分鐘AC了(X