###### tags: `小菜雞解題日記`
# 主題一 : 暴搜枚舉
### 內容
一開始我以為枚舉都是只有測資很小的時候能夠使用，但上完課才發現原來枚舉也是很需要技巧，像是配合一些剪枝或對答案二分搜等方法都可以大幅降低暴搜的複雜度。枚舉通常會是解題的最初的想法，有時候我們只需要改進一下枚舉的方式就會是答案了。
---
### [CF題單](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261)
#### **[A. multiplication 1](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/A)**
**解題心得** : 一題看起來隨便做都對的題目，但我因為少加判斷WA了4次:cry::cry:
**解題想法** : 答案不是$(a, c/a)$就是$(c/b, b)$
所以只有a, b都可以整除c時要把位數拆解做判斷。
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int a, b, c;
int count(int a, int b){
int ta, tb, cnt = 0, x = 3;
while(x--){
ta = a % 10;
tb = b % 10;
a/=10,b/=10;
if(ta != tb) cnt++;
}
return cnt;
}
signed main(void){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> a >> b >> c;
int ca = c/a;
if(c % a == 0 && ca >= 100 && ca <= 999 && count(b, ca) == 1){
cout << a << ' ' << ca << '\n';
} else {
cout << c/b << ' ' << b << '\n';
}
}
```
:::
**[B. Classical String Problem](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/B)**
**解題心得** : 一開始看錯題目以為是甚麼平衡樹模板題:cry:，但後來仔細看測資才發現這是題水題。
**解題想法** : 觀察一下測資就會發現不管怎麼操作，字串順序根本都不會變，所以只要記錄開頭的字元現在在第幾個就好了。
:::success
AC code
::: spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define ll long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
#define lo(x) (x&-x)
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
string str;
int s, q, n, x;
signed main(void){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> str;
cin >> q;
int now = 0;
n = sz(str);
while(q--){
char c;
cin >> c >> x;
if(c == 'A'){
x--;
int st = n - now;
cout << str[(st+x)%n] << '\n';
} else {
if(x > 0){
now += n - x;
} else{
now += (-x);
}
}
now %= n;
}
}
```
:::
**[C. xorequation 1](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/C)**
**解題心得** : 看起來有點可怕但其實就是回朔法枚舉的題目。
**解題想法** : 就單純DFS枚舉
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb push_back
#define ar array
#define ll long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, v, a[20];
vector<string> ans;
string t;
void dfs(int k, int now){
if(k == n){
if(now == v) ans.pb(t);
return;
}
for(int i = 0; i <= a[k]; i++){
t.pb(i+'0');
dfs(k+1, now^i);
t.pop_back();
}
return;
}
signed main(void){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> v;
for(int i = 0; i < n; i++) cin >> a[i];
dfs(0, 0);
cout << ans.size() << '\n';
for(int i = 0; i < sz(ans); i++){
for(int j = 0; j < n; j++){
cout << ans[i][j];
if(j != n-1) cout << "^";
else cout << "=" << v << '\n';
}
}
}
```
:::
**[D. Dreamoon and MRT](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/D)**
**解題心得** : 很有趣的題目，一開始我還看不出是枚舉。
**解題心得** : 因為座標範圍很小所以可以開陣列直接紀錄，然後把原點設大一點就不會跑到負的，然後再DFS搜索，這一題不能用for迴圈跑2 subset因為複雜度會多一個M(蠻邪惡的)。
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define ll long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const int mid = 3000000;
int m, d[30], ans = 25;
bitset<6000005> b;
void dfs(int k, int now, int p){
if(k == m){
if(ans > p) ans = p;
return;
}
int add = 0;
if(b[now+d[k]] == 0) add = 1;
b[now+d[k]] = 1;
dfs(k+1, now + d[k], p + add);
b[now+d[k]] = b[now+d[k]] ^ add;
add = 0;
if(b[now-d[k]] == 0) add = 1;
b[now-d[k]] = 1;
dfs(k+1, now - d[k], p + add);
b[now-d[k]] = b[now-d[k]] ^ add;
return ;
}
signed main(void){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> m;
for(int i = 0; i < m; i++) cin >> d[i];
b[mid] = 1;
dfs(0, mid, 1);
cout << ans;
}
```
:::
**[E. Count Simple Cycles Easy](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/E)**
**解題心得** : 這題困難版超難，但簡單版就是純暴搜。一開始沒發現這是簡單版所以沒解。
**解題想法** : 因為簡單環是只要邊的組合不同就是不同的環。所以我就想到了TMW的鄰接表法(看他打CSES用到的)，然後就可以開始暴搜，然後把走過的邊狀壓起來，最後再看有幾種不同的組合就好。
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int N = 50, M = 1e9+7;
int st, len, n, m, a, b, ans, res, ev[N], eu[N];
vector<int> g[N];
bitset<N> vis;
set<int> s;
void dfs(int u, int path, int p){
if(u == st && path != 0){
s.insert(path);
return;
}
for(int i : g[u]){
int v = ev[i]^eu[i]^u;
if(vis[v] || v == p) continue;
vis[v] = 1;
dfs(v, path | (1ll<<i), u);
vis[v] = 0;
}
return;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a >> b;
eu[i] = a;
ev[i] = b;
g[a].pb(i);
g[b].pb(i);
}
for(int i = 1; i <= n; i++){
st = i;
vis = 0;
dfs(i, 0, 0);
}
cout << s.size();
}
```
:::
**解題想法2** : 其實有更好的想法，因為我們上面的作法雖然可以求出正解，但其實做了很多次多餘的操作，同一個環會被跑到$2 * C$ 次(C是環大小)。如果我們每次都選擇環裡面最小的點當作起點和終點遍歷，也就是其他點都會大於起點編號，這樣我們每個環就只會跑到2次(因為是雙向邊)，但還有另一種狀況就是$(u \rightarrow v \rightarrow u)$這種狀況會被算到M次，最後要扣掉。
**PS** : 從原本的46ms降到了31ms :laughing:
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
int n, m, st, ans;
vector<int> g[55];
bitset<55> vis;
void dfs(int u){
for(int v : g[u]){
if(v == st){
ans++;
continue;
}
if(vis[v] || v < st) continue;
vis[v] = 1;
dfs(v);
vis[v] = 0;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
for(int i = 1; i <= n; i++){
st = i;
vis[i] = 1;
dfs(i);
vis[i] = 0;
}
ans-=m;
cout<<(ans>>1);
}
```
:::
**[F. NPY and arithmetic progression](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/F
)**
**解題心得** : 這題我想了很久，我一開始真的看不出來要怎麼暴搜(其實連題目都看不懂)。後來就硬著頭皮寫，最後還是寫出來了，但寫得很爛。
**解題想法** : 等差數列只有(1,2,3),(2,3,4)和(1,2,3,4)三種先優秀暴搜扣掉這三種，最後在判斷是不是剩下的每個數字都等於0或大於等於3。
:::success
AC 爛code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
int a[5], T;
bool ok = 0;
void dfs(){
if(a[0] + a[1] + a[2] + a[3] == 0){
ok = 1;
return;
}
int t[4];
for(int i = 0; i < 4; i++) t[i] = a[i];
int m1 = min({a[0], a[1], a[2]}), m2 = min({a[1], a[2], a[3]}), m3 = min(m1, m2);
if(m1 > 0 && m1 < 3){
m1 = 1;
a[0]-= m1; a[1]-= m1; a[2]-= m1;
dfs();
for(int i = 0; i < 4; i++) a[i] = t[i];
} else m1 = 0;
if(m2 > 0 && m2 < 3){
m2 = 1;
a[1]-= m2;a[2]-= m2;a[3]-= m2;
dfs();
for(int i = 0; i < 4; i++) a[i] = t[i];
} else m2 = 0;
if(m3 > 0 && m3 < 3){
m3 = 1;
for(int i = 0; i < 4; i++) a[i]-=m3;
dfs();
for(int i = 0; i < 4; i++) a[i] = t[i];
}
if(m1>0 || m2>0) return;
for(int i = 0; i < 4; i++){
if(a[i] >= 3){
a[i] = 0;
dfs();
a[i] = t[i];
}
}
return;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while(T--){
ok = 0;
cin >> a[0] >> a[1] >> a[2] >> a[3];
dfs();
if(ok) cout << "Yes\n";
else cout << "No\n";
}
}
```
:::
**[G. permutation 1](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/G)**
**解題心得** : 坑
**解題想法** : 坑
**[H. 最小點覆蓋問題](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/H)**
**解題心得** : 其實不是我解的，是老師上課教的(我一開始還想用枚舉點來做QQ)
**解題想法** : 既然不能枚舉點，那就沒舉邊吧。因為根據題目，我們只需要求出18以下的解，所以我們解答樹最多有 $2^{18}$ 個葉子節點，而樹的深度最深的情況就會是邊的數量，因此複雜度$O(2^{18}M)$，雖然看起來會TLE，但其實深度不會跑滿。
:::success
AC code 405ms
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int N = 505;
int n, m, id[N], ev[N], eu[N], a = 19;
bitset<N> cover;
vector<int> ans;
void dfs(int now, int c){
if(c >= a) return;
if(now == m){
if(c < a){
ans.clear();
a = c;
for(int i = 1; i <= n; i++)
if(cover[i]) ans.pb(i);
}
return;
}
if(cover[ev[now]] || cover[eu[now]]){
dfs(now+1, c);
} else {
if(id[ev[now]] >= 1 || id[eu[now]] == 0) cover[ev[now]] = 1, dfs(now+1, c+1), cover[ev[now]] = 0;
if(id[eu[now]] >= 1 || id[ev[now]] == 0) cover[eu[now]] = 1, dfs(now+1, c+1), cover[eu[now]] = 0;
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> ev[i] >> eu[i];
id[ev[i]]++;
id[eu[i]]++;
}
if(m > n * 18){
puts("-1");
return 0;
}
dfs(0, 0);
if(a>18){
puts("-1");
return 0;
}
cout<<a<<'\n';
for(int i : ans)
cout<<i<<' ';
}
```
:::
::: success
AC code + 剪枝 233ms
::: spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
const int N = 505;
int n, m, id[N], ev[N], eu[N], a = 19;
bitset<N> cover;
vector<int> ans;
void dfs(int now, int c){
if(c >= a) return;
if(now == m){
if(c < a){
ans.clear();
a = c;
for(int i = 1; i <= n; i++)
if(cover[i]) ans.pb(i);
}
return;
}
if(cover[ev[now]] || cover[eu[now]]){
dfs(now+1, c);
} else {
if(id[ev[now]] > 1 || id[eu[now]] == 1) cover[ev[now]] = 1, dfs(now+1, c+1), cover[ev[now]] = 0;
if(id[eu[now]] > 1 || id[ev[now]] == 1) cover[eu[now]] = 1, dfs(now+1, c+1), cover[eu[now]] = 0;
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> ev[i] >> eu[i];
id[ev[i]]++;
id[eu[i]]++;
}
if(m > n * 18){
puts("-1");
return 0;
}
dfs(0, 0);
if(a>18){
puts("-1");
return 0;
}
cout<<a<<'\n';
for(int i : ans)
cout<<i<<' ';
}
```
:::
**[I. Dreamoon and NightMarket](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/I)**
**解題心得** : 題目是要你求出第K大的子集，看起來很簡單其實還蠻困難的題目。
**解題想法** : 直接枚舉子集一定會TLE，因為題目有限制K會小於$10^6$，如果用枚舉再加入一些技巧的話是可行的。
1. 使用Priority Queue
2. 對答案二分搜
::: success
AC code Priority Queue
::: spoiler
```cpp=
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int, int>
using namespace std;
int n, k, p[200005], cnt, last;
priority_queue<pii, vector<pii>, greater<pii>> pq;
/*
void dfs(int now, int sum){
if(cnt == k) return;
if(now == n){
cnt++;
la = sum;
return;
}
}
*/
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i = 0; i < n; i++)
cin>>p[i];
sort(p, p+n);
pq.push({p[0], 0});
pii now;
while(k--){
now = pq.top();
//cout<<"now = "<<now.f<<'\n';
pq.pop();
if(now.s == n-1) continue;
pq.push({now.f + p[now.s+1], now.s+1});
pq.push({now.f - p[now.s] + p[now.s+1], now.s + 1});
}
cout<<now.f;
}
```
:::
:::success
AC code 對答案二分搜
:::spoiler
```cpp!
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
int n, k, a[200005], l, r, mid, cnt;
void dfs(int u, int sum){
if(u == n || cnt >= k) return;
if(sum + a[u] <= mid){
cnt++;
dfs(u+1, sum + a[u]);
dfs(u+1, sum);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i = 0; i<n; i++) cin>>a[i], r += a[i];
sort(a, a+n);
while(l < r){
mid = l + (r-l>>1);
cnt = 0;
dfs(0, 0);
if(cnt >= k) r = mid;
else l = mid + 1;
}
cout<<l;
}
```
:::
---
### 回家練習題
1.**[ABC 119C Synthetic Kadomatsu](https://atcoder.jp/contests/abc119/tasks/abc119_c)**
**解題心得** : 看到這個N的大小很容易就可以聯想到爆搜，原本想說要怎麼剪一下枝，後來想一下，直接 $O(4^N)$ 就可以過了。
**解題想法** : 對於每根竹子都只有四種狀態分給A, B, C 或不選，直接爆搜就好。先選好每個竹子屬於哪個狀態最後再做處理就好，吃了一次WA因為忘記判斷A, B, C都至少要選一根。
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
int n, a, b, c, p[15], l[15], ans = 1e18;
void dfs(int now){
if(now == n){
int res = -30, ta = 0, tb = 0, tc = 0;
for(int i = 0; i < n; i++){
if(p[i]) res += 10;
if(p[i] == 1) ta += l[i];
if(p[i] == 2) tb += l[i];
if(p[i] == 3) tc += l[i];
}
if(ta == 0 || tc == 0 || tb == 0) return;
res += abs(ta - a) + abs(tb - b) + abs(tc - c);
ans = min(ans, res);
return;
}
for(int i = 0; i <= 3; i++){
p[now] = i;
dfs(now+1);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>a>>b>>c;
for(int i = 0; i < n; i++)
cin>>l[i];
dfs(0);
cout<<ans;
}
```
:::
2.**[ABC 100D Patisserie ABC](https://atcoder.jp/contests/abc100/tasks/abc100_d)**
**解題心得** : 這題是一題非常酷的題目一開始覺得是貪心或是甚麼奇怪的數學。但後來想到國中數學老師說過的話 "遇到絕對值怎麼辦? 正負討論!"
**解題想法** : 枚舉三個參數的正負然後加起來進行排序，取和最大的M個相加。一開始我想說只要寫一個cmp來排序就好，但不知道為甚麼排出來的東西跟我想得不太一樣。但後來我改一下寫法就AC了。因為我懶得思考所以我就用3層迴圈枚舉正負。
::: success
AC code
::: spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
int n, m, x, y, z, ans, t[1005], p[1005];
struct food{
int a, b, c;
}e[10005];
bool cmp(int a, int b){
return t[a] > t[b];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i = 0; i < n; i++)
cin>>e[i].a>>e[i].b>>e[i].c;
for(x = -1; x <= 1; x += 2){
for(y = -1; y <= 1; y += 2){
for(int z = -1; z <= 1; z += 2){
int ta = 0, tb = 0, tc = 0;
for(int i = 0; i < n; i++) {
t[i] = (e[i].a * x + e[i].b * y + e[i].c * z);
p[i] = i;
}
sort(p, p+n, cmp);
for(int i = 0; i < m; i++)
ta += e[p[i]].a, tb += e[p[i]].b, tc += e[p[i]].c;
ans = max(ans, abs(ta) + abs(tb) + abs(tc));
}
}
}
cout<<ans;
}
```
:::
3. **[ABC 152D Handstand 2](https://atcoder.jp/contests/abc152/tasks/abc152_d)**
**解題心得** : 這是一題看起來很像數位dp的普通枚舉題，直接沒舉1 ~ n就可以了。
**解題想法** : 每個數字我們在意的只有他的首位和末位，所以只要開一個二維陣列 $num[10][10]$ ，然後枚舉1 ~ n把這些數的數量存下來就好，答案就會是 $\sum_{i=1}^{9}\sum_{j=1}^{9}num[i][j]$
:::success
AC code
:::spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int long long
#define wopen(x) freopen((x),"w",stdout)
#define ropen(x) freopen((x),"r",stdin)
using namespace std;
int n, r, ans, num[10][10];
int hd(int x){
int t;
while(x){
t = x % 10;
x /= 10;
}
return t;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++){
num[hd(i)][i%10]++;
}
for(int i = 1; i <= 9; i++){
for(int j = 1; j <= 9; j++){
ans += num[i][j] * num[j][i];
}
}
cout<<ans;
}
:::
4. **[TIOJ 2137](https://tioj.ck.tp.edu.tw/problems/2137)**
**解題心得** : 超少人解的一題，我因為忘記初始化debug了很久:cry:，還好最後有寫出來，聽說這題 IOIC 比賽的時侯好像沒人打出來，能自己打出來還蠻有成就感的:laughing:。(雖然這題跟上面的I好像差不多)
**解題想法** : 這題要你求出權重第K大的獨立點集。最小的一定是 0，所以可以直接判斷掉，之後就 枚舉 + 二分搜。二分搜的 mid 是這次枚舉的點集總權重的最大限制，在這個限制下如果可以枚舉超過 K 種可能就縮小限制，反之亦然。要注意的是枚舉時時間複雜度要是 $O(K)$，所以會用到一些狀壓的小技巧。
::: success
AC code
::: spoiler
```cpp=
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mem(x,val) memset(x,val,sizeof x)
#define pii pair<int,int>
#define pb emplace_back
#define ar array
#define int unsigned long long
using namespace std;
int n, T, s, ans, l, r, k, cnt, mid, x, w[65], b[65];
void dfs(int u, int sum, int bit){
if(cnt > k || u >= n) return;
dfs(u + 1ll, sum, bit);
if(mid < sum + w[u] || (bit & (1ll<<u))) return;
cnt++;
dfs(u + 1ll, sum + w[u], bit | b[u]);
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--){
cin >> n >> k;
l = 1e18;
ans = r = 0;
mem(b, 0);
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j++){
cin >> x;
b[i] |= (x<<j);
}
b[i] |= (1ll<<i);
}
for(int i = 0; i < n; i++) cin >> w[i], r += w[i], l = min(w[i], l);
if(--k == 0) {
cout << 0 << '\n';
continue;
}
mid = r;
cnt = 0;
dfs(0, 0, 0);
if(cnt < k) {
cout << -1 << '\n';
continue;
}
r += 10ll;
while(l < r){
mid = l + ((r-l)>>1ll);
cnt = 0;
dfs(0, 0, 0);
if(cnt < k) l = mid + 1ll;
else r = mid;
}
cout << l << '\n';
}
}
```
:::
Sign in with Wallet
Connect another wallet