---
###### tags: `2020 師大附中校隊培訓`
---
# 枚舉
## 2020 師大附中校隊培訓
#### joylintp
#### 10.27.2020
---
## 密密麻麻密碼鎖
### NPSC 2017 國中決賽
----
有一個六位數的密碼鎖
現在上面顯示的數字為 $\overline{abcdef}$
每次操作你可以把其中一位數加上1或減去1
（9加上1變成0；0減去1變成9）
求至少要 $k$ 次操作才能使六位數字皆相異
並列出所有 $k$ 次操作後六位數字皆相異的可能狀態
----
~~遞迴~~
~~動態規劃~~
### 窮舉
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int mn = 2147483647;
set<int> anslist;
for (int i = 12345; i < 1000000; i++)
{
int t = i, u;
set<int> s;
if (i < 100000)
s.insert(0);
while (t)
s.insert(t % 10), t /= 10;
int tmp = 0;
if (s.size() == 6)
{
t = i;
u = n;
while (t || u)
tmp += min(abs(t % 10 - u % 10), 10 - abs(t % 10 - u % 10)), t /= 10, u /= 10;
if (tmp < mn)
anslist.clear(), anslist.insert(i), mn = tmp;
else if (tmp == mn)
anslist.insert(i);
else;
}
}
cout << anslist.size() << ' ' << mn << '\n';
for (int i : anslist)
cout << setw(6) << setfill('0') << i << ' ';
return 0;
}
```
---
## 數獨
### Sprout No.62
----
* 遇到一個空格就枚舉所有可能
* 若沒有合法的數字就回到上一個空格
----
```cpp=
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
bool stop, crush;
int game[9][9], cnt_blk, ans[9][9];
pair<int, int> blank[30];
set<int> row[9], column[9], box[9];
int pos_box(int x, int y)
{
return x / 3 * 3 + y / 3;
}
void dfs(int id)
{
if (stop)
return;
if (id >= cnt_blk)
{
memcpy(ans, game, sizeof(int) * 81);
stop = true;
return;
}
int x = blank[id].first, y = blank[id].second;
for (int i = 1; i <= 9; i++)
if (!(row[x].count(i) || column[y].count(i) || box[pos_box(x, y)].count(i)))
{
game[x][y] = i, row[x].insert(i), column[y].insert(i), box[pos_box(x, y)].insert(i);
dfs(id + 1);
game[x][y] = 0, row[x].erase(i), column[y].erase(i), box[pos_box(x, y)].erase(i);
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
string s;
while (cin >> s)
{
if (s == "end")
break;
cnt_blk = 0;
stop = crush = false;
for (int i = 0; i < 9; i++)
row[i].clear(), column[i].clear(), box[i].clear();
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
game[i][j] = 0;
for (int i = 0; i < 30; i++)
blank[i] = mp(-1, -1);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
{
int t = s[i * 9 + j];
if (t == '.')
{
t = 0;
blank[cnt_blk++] = mp(i, j);
}
else
{
t -= '0';
if (row[i].count(t))
crush = true;
else
row[i].insert(t);
if (column[j].count(t))
crush = true;
else
column[j].insert(t);
if (box[pos_box(i, j)].count(t))
crush = true;
else
box[pos_box(i, j)].insert(t);
}
game[i][j] = t;
}
dfs(0);
for (int i = 0; i < 9; i++)
row[i].clear(), column[i].clear(), box[i].clear();
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
{
int t = ans[i][j];
if (t < 1 || t > 9)
crush = true;
if (row[i].count(t))
crush = true;
else
row[i].insert(t);
if (column[j].count(t))
crush = true;
else
column[j].insert(t);
if (box[pos_box(i, j)].count(t))
crush = true;
else
box[pos_box(i, j)].insert(t);
}
if (crush)
cout << "No solution.";
else
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cout << ans[i][j];
cout << '\n';
}
return 0;
}
```
---
## $N$ 皇后問題
### Zerojudge a160
----
* 對每一列枚舉放皇后的位置
* 若所有位置皆不合法則回到上一列
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
int ans[12][12], cnt, n;
bool r[12], d1[25], d2[25];
void dfs(int pos)
{
if (pos == n)
{
string str = "xQ";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << str[ans[i][j]];
cout << '\n';
}
cout << '\n';
cnt++;
return;
}
for (int i = 0; i < n; i++)
if (!(r[i] || d1[i + pos] || d2[i - pos + n - 1]))
{
ans[pos][i] = 1;
r[i] = d1[i + pos] = d2[i - pos + n - 1] = true;
dfs(pos + 1);
ans[pos][i] = 0;
r[i] = d1[i + pos] = d2[i - pos + n - 1] = false;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
while (cin >> n)
{
if (n == 0)
break;
cnt = 0;
for (int i = 0; i < 12; i++)
r[i] = false;
for (int i = 0; i < 25; i++)
d1[i] = d2[i] = false;
for (int i = 0; i < 12; i++)
for (int j = 0; j < 12; j++)
ans[i][j] = 0;
dfs(0);
cout << cnt << "\n\n";
}
return 0;
}
```
---
## 背包問題
----
有$n\ (1 \leq n \leq 20)$樣物品，
每個物品有自己的價值和重量$(1 \leq p_i, w_i \leq 10^9)$
現在有一個耐重$k (1 \leq k \leq 10^9)$的背包，
問在所有物品只能選擇全放進背包或全不放進背包的情況下，
背包內的物質總價值最高是多少？
----
* 枚舉物品的子集合
* 檢查子集合總重是否超過$k$並更新最高價格
----
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
pair<int, int> obj[20];
for (int i = 0; i < n; i++)
cin >> obj[i].first >> obj[i].second;
int ans = 0;
for (int i = 0; i < (1 << n); i++)
{
int t = i;
bool use[n];
for (int j = 0; j < n; j++)
use[j] = t % 2, t /= 2;
int tw = 0, tp = 0;
for (int j = 0; j < n; j++)
if (use[j])
tp += obj[j].first, tw += obj[j].second;
if (tw <= k)
ans = max(ans, tp);
}
cout << ans << '\n';
return 0;
}
```
---
## Next Permutation
----
```cpp=
bool my_next_permutation(vector<int> &num)
{
int n = num.size();
if(n == 1)
return false;
for(int i = n - 2, j = n - 1; i >= 0; i--, j--)
if(num[i] < num[j])
{
int k = n - 1;
while(num[i] >= num[k])
k--;
swap(num[i], num[k]);
reverse(num.begin() + j, num.end());
return true;
}
return false;
}
```
----
```cpp=
next_permutation(v.begin(), v.end()); // 將v變成下一個排列
```
```cpp=
prev_permutation(v.begin(), v.end()); // 將v變成前一個排列
```
---
## Lotto
### UVa 441, ZJ c074
----
* 枚舉大小為6的子集合
* 將use陣列內最後6個值設為1
* 以next_permutation遍歷所有大小為6的子集合
----
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
bool fir = true;
int n;
while (cin >> n)
{
if (!n)
return 0;
if (fir)
fir = false;
else
cout << '\n';
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
vector<bool> use(n);
for (int i = 0; i < 6; i++)
use[i] = true;
do
{
int cnt = 0;
for (int i = 0; i < n; i++)
if (use[i])
cout << v[i] << " \n"[cnt++ == 5];
} while (prev_permutation(use.begin(), use.end()));
}
return 0;
}
```
{"metaMigratedAt":"2023-06-15T14:47:39.290Z","metaMigratedFrom":"Content","title":"枚舉","breaks":true,"contributors":"[{\"id\":\"6b95215f-91a7-4eaf-bcfe-d43740108f96\",\"add\":8224,\"del\":0}]"}