dfs 第一次加訓詳解下

?P1706 全排列問題

思路

B3618 尋找團伙

思路

B3621 枚舉元組

思路

B3622 枚舉子集（遞歸實現指數型枚舉）

思路

B3623 枚舉排列（遞歸實現排列型枚舉）

B3625 迷宮尋路

思路

P6183 [USACO10MAR] The Rock Game S

總結

P10448 組合型枚舉

思路

P10483 小貓爬山

思路?

P8604 [藍橋杯 2013 國 C] 危險系數

思路

P9011 [USACO23JAN] Air Cownditioning II B

思路

P10294 [CCC 2024 J5] Harvest Waterloo

思路

?P1706 全排列問題

題目描述

按照字典序輸出自然數?1?到?n?所有不重復的排列，即?n?的全排列，要求所產生的任一數字序列中不允許出現重復的數字。

輸入格式

一個整數?n。

輸出格式

由?1～n?組成的所有不重復的數字序列，每行一個序列。

每個數字保留?5?個場寬。

輸入輸出樣例

輸入 #1復制
3
輸出 #1復制
    1    2    31    3    22    1    32    3    13    1    23    2    1
說明/提示

1≤n≤9。

思路

用dfs來寫，其實就是n個for循環而已，比如 3個數1 2 3來進行排列那就是for for for，然后前面的for現在的i不能被后面再用所以再來個visited，防止重新用了前面已經排的數

#include<bits/stdc++.h>
using namespace std;
vector<int>path;
vector<vector<int>>res;
vector<bool> visited(100000); 
int n;
void dfs(){if(path.size()==n) {res.push_back(path); return ;}for(int i=1;i<=n;i++){if(!visited[i]){visited[i]=1;path.push_back(i);dfs();path.pop_back();visited[i]=0;}}
}int main(){cin>>n;dfs();for(auto i:res){for(auto j:i){printf("%5d", j); // 使用 printf 保證 5 個場寬  }cout<<endl;}
}

B3618 尋找團伙

題目描述

世界局勢風云變幻，你想辦一件大事。辦事自然要有人參與，你能從?n?個人里面挑選一部分人共襄盛舉。

要辦這件事，一共涉及?k?方面的能力，例如游說他人的能力、玩游戲的能力、睡覺的能力。每位人士都會具備某一些能力，例如機器貓就可能擅長睡覺、擅長玩游戲，而不擅長游說他人。

你的計劃很宏偉，因此你希望團隊擁有很全面的能力。不幸的是，如果團隊中有偶數個人擁有同一類能力，那么他們就會分成兩派，爭執不下，導致整個團隊喪失這方面的能力。相應地，如果這項能力只有奇數個人擁有，那么他們總能形成一個多數派，幫團隊去做這方面的工作。

需要注意的是，團隊擁有的每一項能力，對計劃的成功率的貢獻是不一樣的。第一項能力最重要，它的權重是?2k?1；第二項能力的權重是?2k?2；依次類推。第?k?項能力最不重要，權重只有?1。

計劃的成功率得分，即是團隊擁有的所有能力對應的權重之和。

你希望計劃成功率最大。因此，你需要選出合適的人士，來參與到你的宏圖偉業中。

輸入格式

第一行，兩個正整數?n,k。分別表示供你挑選的人的數量，以及能力的種類數。
接下來?n?行，每行表示每個人擁有的能力。這一行首先有一個整數?c，表示該人士擁有多少種能力；接下來是?c?個?[1,k]?之間的正整數，表示該人士擁有哪些能力。

輸出格式

僅一行，一個整數，表示計劃的成功率得分。

輸入輸出樣例

輸入 #1復制
5 5
1 1
1 2
1 3
1 4
1 5
輸出 #1復制
31
輸入 #2復制
3 5
3 1 2 3
4 2 3 4 5
2 3 4
輸出 #2復制
28
輸入 #3復制
3 5
2 1 2
3 5 3 2
3 4 2 5
輸出 #3復制
30
輸入 #4復制
21 60
0 
0 
3 60 27 48
0 
1 48
2 52 14
2 4 31
0 
0 
2 28 43
2 6 31
0 
1 7
3 45 6 48
0 
1 51
0 
2 28 20
2 37 51
1 8
53 59 39 29 23 53 27 13 16 44 34 38 24 9 32 58 54 31 1 7 45 3 30 36 17 48 42 22 18 21 6 11 25 33 37 52 10 60 49 57 2 28 8 14 5 47 4 41 35 43 50 46 26 12
輸出 #4復制
1152884121210322895
說明/提示

樣例解釋

第一組樣例，共 5 個人，每個人擁有的能力不一樣。最終選擇的結果是讓這 5 個人都參與計劃，得分?16+8+4+2+1=31。

第二組樣例，我們選擇只讓?1?參與。那么團隊具有能力?1,2,3，得分?16+8+4=28。

第三組樣例，我們讓?1,2,3?參與。由于團隊中有偶數個成員擁有能力?5，故團隊并不擁有能力?5。奇數個成員擁有能力?2，故團隊擁有能力?2。最終，團隊具有能力?1,2,3,4。得分?16+8+4+2=30。

數據規模與約定

對于?100%?的數據，有?n≤21,k≤60。

思路

很明顯就是選或不選某個人唄，然后搞個ans全局變量記錄答案，當每個人都搜索一遍后就ans搞一下，看看每個方案哪個ans最大就ok，這是整體思路，，，里面還需要一些位運算，好吧這個位運算的是看的題解，

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, a[21+10], ans;
void dfs(ll i,ll now) {if(i>n) {//都搜索過一遍后 ans=max(ans,now);return;}//異或的性質就是相同為0，不同為1，那相同就是偶數，奇數就是不同，//eg.比如選了1和3 那這個人的能力值就是101，另一個只選了3那就是100異或后就是001，正好符合題目要求 dfs(i+1,now^a[i]);//選這個人，抑或上他的分值,用來異或就不用再多考慮奇數偶數情況，因為上面說了異或的性質dfs(i+1,now);//不選
}
int main(){cin>>n>>k;//n個人，k個能力 for(ll i=1;i<=n;i++){int c;cin>>c;for(ll j=1;j<=c;j++) {int x;cin>>x;a[i]|=(1ll<<(k-x)); //記錄二進制分值，等價于a[i] += (1ull << (k - x))或a[i] += (1ull * pow(2, k - x))}}dfs(0,0);//第一個參數是第幾號人，因為第一個人也要判斷選或不選，所以從0開始，//第二個參數是當前的團伙的總能力值 cout << ans;return 0;
}

B3621 枚舉元組

題目描述

n?元組是指由?n?個元素組成的序列。例如?(1,1,2)?是一個三元組、(233,254,277,123)?是一個四元組。

給定?n?和?k，請按字典序輸出全體?n?元組，其中元組內的元素是在?[1,k]?之間的整數。

「字典序」是指：優先按照第一個元素從小到大的順序，若第一個元素相同，則按第二個元素從小到大……依此類推。詳情參考樣例數據。

輸入格式

僅一行，兩個正整數?n,k。

輸出格式

若干行，每行表示一個元組。元組內的元素用空格隔開。

輸入輸出樣例

輸入 #1復制
2 3
輸出 #1復制
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
輸入 #2復制
3 3
輸出 #2復制
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3
說明/提示

對于?100%?的數據，有?n≤5,k≤4。

思路

可以注意到輸出的類似于全排列，但是他能輸出 1 1,2 2，3 3說明for for兩個前面的for用了一個數后后面還可以用，那我們就不需要visited數組來保證一個數只用一次了，比前面的那個全排列還要簡單，只要記著dfs里面的basecase是path.size()==n就好，看代碼

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<vector<int>>res;
vector<int>path;
bool visited[6];//不需要用到
void dfs(){if((int)path.size()==n){res.push_back(path);return ;}for(int i=1;i<=k;i++){path.push_back(i);	dfs();path.pop_back();}}int main(){cin>>n>>k;dfs();for(auto i:res){for(auto j:i){cout<<j<<' ';}cout<<endl;}
}

B3622 枚舉子集（遞歸實現指數型枚舉）

題目描述

今有?n?位同學，可以從中選出任意名同學參加合唱。

請輸出所有可能的選擇方案。

輸入格式

僅一行，一個正整數?n。

輸出格式

若干行，每行表示一個選擇方案。

每一種選擇方案用一個字符串表示，其中第?i?位為?Y?則表示第?i?名同學參加合唱；為?N?則表示不參加。

需要以字典序輸出答案。

輸入輸出樣例

輸入 #1復制
3
輸出 #1復制
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY
說明/提示

對于?100%?的數據，保證?1≤n≤10。

思路

依舊是for for for組成，我們只要搞個數組里面放Y N，然后遍歷，然后遞歸層數就是由n決定，當存了n個for后就行，依舊不需要visited數組

#include<bits/stdc++.h>
using namespace std;
int n;
char a[2]{'Y','N'};
vector<string>res;
string path;
void dfs(){if((int)path.size()==n){res.push_back(path);return ;}for(int i=0;i<=1;i++){path.push_back(a[i]);	dfs();path.pop_back();}}
int main(){cin>>n;dfs();sort(res.begin(),res.end());for(auto i:res){for(auto j:i){cout<<j;}cout<<endl;}}

B3623 枚舉排列（遞歸實現排列型枚舉）

題目描述

今有?n?名學生，要從中選出?k?人排成一列拍照。

請按字典序輸出所有可能的排列方式。

輸入格式

僅一行，兩個正整數?n,k。

輸出格式

若干行，每行?k?個正整數，表示一種可能的隊伍順序。

輸入輸出樣例

輸入 #1復制
3 2
輸出 #1復制
1 2
1 3
2 1
2 3
3 1
3 2
說明/提示

對于?100%?的數據，1≤k≤n≤10。

思路

求排列方式，那就需要visited數組，在求排列的方式基礎上加了后就行，看代碼

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<vector<int>>res;
vector<int> path;
bool visited[15]={false};
void dfs(){if((int)path.size()==k){res.push_back(path);return ;}for(int i=1;i<=n;i++){if(!visited[i]){path.push_back(i);visited[i]=1;	dfs();visited[i]=0;path.pop_back();}}}
int main(){cin>>n>>k;dfs();for(auto i:res){for(auto j:i){cout<<j<<' ';}cout<<endl;}
}

B3625 迷宮尋路

題目描述

機器貓被困在一個矩形迷宮里。

迷宮可以視為一個?n×m?矩陣，每個位置要么是空地，要么是墻。機器貓只能從一個空地走到其上、下、左、右的空地。

機器貓初始時位于?(1,1)?的位置，問能否走到?(n,m)?位置。

輸入格式

第一行，兩個正整數?n,m。

接下來?n?行，輸入這個迷宮。每行輸入一個長為?m?的字符串，#?表示墻，.?表示空地。

輸出格式

僅一行，一個字符串。如果機器貓能走到?(n,m)，則輸出?Yes；否則輸出?No。

輸入輸出樣例

輸入 #1復制
3 5
.##.#
.#...
...#.
輸出 #1復制
Yes
說明/提示

樣例解釋

路線如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)

數據規模與約定

對于?100%?的數據，保證?1≤n,m≤100，且?(1,1)?和?(n,m)?均為空地。

思路

這個題用dfs，bfs都行，先來個bfs吧哈哈，我的隊列是用數組模擬的，數組模擬的常數時間會更快，這也算是bfs模版了，不是很難看看應該就行了，之后我也會寫關于bfs的文章

其實這個題根洪水填充差不多，只不過這個是一個點往外一直蔓延，看看能不能蔓延到最后一個點

多講點吧，用數組模擬的話，因為這是要存坐標，所以我們就需要一個二維的[0]存x,[1]存y

大家平時見到的控制上下左右的數組可能是兩個數組，我這里用了一個更方便一些，不懂得可以自己試一下就能理解了，不懂bfs的可以正好學學，這就純是一個模板

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010;
vector<string>grid(N);
bool visited[N][N];
int mv[5]={-1,0,1,0,-1};
int q[N][2];
int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>grid[i];}visited[0][0]=1;int l=0,r=0;q[r][0]=0;q[r++][1]=0;while(l<r){int size=r-l;for(int i=0,nx,ny,x,y;i<size;i++){x=q[l][0];y=q[l++][1];if(x==n-1&&y==m-1) {cout<<"Yes";return 0;}for(int k=0;k<=4;k++){nx=x+mv[k];ny=y+mv[k+1];if(nx>=0&&ny>=0&&nx<n&&ny<m&&!visited[nx][ny]&&grid[nx][ny]=='.'){visited[nx][ny]=true;q[r][0]=nx;q[r++][1]=ny;}}}}cout<<"No";return 0;
}

下面是dfs，其實都差不多

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
bool visited[N][N];
int n,m;
vector<string> grid(N);
int mv[5]={-1,0,1,0,-1};
bool dfs(int x,int y) {// 到達終點if (x ==n-1&&y==m-1) {return true;}// 標記當前點已訪問visited[x][y]=true;for (int i=0;i<=4;i++) {int nx=x+mv[i];int ny=y+mv[i];if (nx>=0&&nx<n&&ny>=0&&ny<m&&grid[nx][ny]=='.'&&!visited[nx][ny]) {if (dfs(nx,ny)){return true;}}}return false;
}
int main(){cin>>n>>m;for (int i=0;i<n;i++) {cin>>grid[i];}// 起點或終點是墻，直接輸出Noif (grid[0][0]=='#'||grid[n-1][m-1]=='#') {cout<<"No"<<endl;return 0;}bool result=dfs(0, 0);cout <<(result?"Yes":"No")<<endl;return 0;
}

P6183 [USACO10MAR] The Rock Game S

題目描述

在奶牛回家休息和娛樂之前，Farmer John 希望它們通過玩游戲獲得一些智力上的刺激。

游戲板由?n?個相同的洞組成，這些洞最初都是空的。一頭母牛要么用石頭蓋住一個空的洞，要么揭開一個先前被蓋住的洞。游戲狀態的定義是所有洞是否被石頭覆蓋的情況。

游戲的目標是讓奶牛到達每個可能的游戲狀態一次，最后回到初始狀態。

以下是他們其中一次游戲的示例（空的洞用?O?表示，用石頭蓋住的洞用?X?表示）：

時刻洞 1 洞 2 洞 3 描述
0 O O O 一開始所有的洞都是空的
1 O O X 蓋上洞 3
2 X O X 蓋上洞 1
3 X O O 打開洞 3
4 X X O 蓋上洞 2
5 O X O 打開洞 1
6 O X X 蓋上洞 3
7 X X X 蓋上洞 1

現在牛被卡住玩不下去了！他們必須打開一個洞，然而不管他們打開哪個洞，他們都會到達一個他們已經到達過的狀態。例如，如果他們從第二個洞中取出巖石，他們將到達他們在時刻?2?已經訪問過的狀態（X O X）。

下面是一個 3 個孔的有效解決方案：

時間洞 1 洞 2 洞 3 描述
0 O O O 一開始所有的洞都是空的
1 O X O 蓋上洞 2
2 O X X 蓋上洞 3
3 O O X 打開洞 2
4 X O X 蓋上洞 1
5 X X X 蓋上洞 2
6 X X O 打開洞 3
7 X O O 打開洞 2
8 O O O 打開洞 1，恢復到原來的狀態

現在，奶牛們厭倦了這個游戲，它們想找你幫忙。

給定?n，求游戲的有效解決方案序列。如果有多個解決方案，則輸出任意一個。

輸入格式

僅一行，一個整數?n。

輸出格式

共?2n+1?行，每行一個長度為?n?的字符串，其中只包含字符?O?和?X，該行中的第?i?個字符表示第?i?個孔在此狀態下是被覆蓋還是未覆蓋，第一行和最后一行必須全部都是?O。

輸入輸出樣例

輸入 #1復制
3
輸出 #1復制
OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO
說明/提示

樣例 1 說明

見題目描述。

數據規模與約定

對于?100%?的數據，有?1≤n≤15。

時刻	洞 1	洞 2	洞 3	描述
0	O	O	O	一開始所有的洞都是空的
1	O	O	X	蓋上洞 3
2	X	O	X	蓋上洞 1
3	X	O	O	打開洞 3
4	X	X	O	蓋上洞 2
5	O	X	O	打開洞 1
6	O	X	X	蓋上洞 3
7	X	X	X	蓋上洞 1

時間	洞 1	洞 2	洞 3	描述
0	O	O	O	一開始所有的洞都是空的
1	O	X	O	蓋上洞 2
2	O	X	X	蓋上洞 3
3	O	O	X	打開洞 2
4	X	O	X	蓋上洞 1
5	X	X	X	蓋上洞 2
6	X	X	O	打開洞 3
7	X	O	O	打開洞 2
8	O	O	O	打開洞 1，恢復到原來的狀態

總結

這段代碼通過深度優先搜索的方式，生成一個格雷碼序列。格雷碼的特點是相鄰的兩個碼之間只有一個位不同。代碼首先輸出全'O'的狀態，然后遞歸地翻轉每一位，生成新的格雷碼狀態。使用?vis?數組來避免重復訪問相同的狀態，從而保證生成的是一個有效的格雷碼序列。ans數組存儲生成的序列，最后output函數負責按要求輸出。

實際上這段代碼找到的是一種特殊的格雷碼序列，它從全'O'開始，每次只翻轉一位，直到遍歷完所有可能的狀態。由于題目要求"找到一組即可"，所以找到任何一種滿足條件的格雷碼序列就可以直接輸出并退出。

總而言之，該程序使用DFS算法巧妙地探索格雷碼空間，并用vis數組進行狀態標記避免重復，最終找到并輸出一個合法的格雷碼序列。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[20];//記錄格雷碼一個a[i]記錄0或1
int vis[1<<20];//記錄每一個格雷碼的是否走過 
int ans[1<<20][20];//記錄每一個狀態的格雷碼 
void output(){for(int i=1;i<=1<<n;i++){for(int j=1;j<=n;j++){cout<<(ans[i][j]?'X':'O');}cout<<endl;}
} 
int calc(){//將當前格雷碼轉化為10進制用來存儲狀態 int res=0;for(int i=1;i<=n;i++){res=res*2+a[i];}return res;
}
void dfs(int pos){if(pos==(1<<n)){output();exit(0) ;}for(int i=1;i<=n;i++){a[i]=!a[i];//從第一位開始到第n位，每個都翻轉一遍看哪個狀態沒走過if(vis[calc()]){a[i]=!a[i];//如果走過就翻轉回去 continue;} vis[calc()]=1;//沒走過現在走過了for(int j=1;j<=n;j++){ans[pos][j]=a[j];//把翻過的a[i]給存到最終答案這里 } dfs(pos+1);vis[calc()]=0;//回溯a[i]=!a[i]; }
}
int main(){cin>>n;for(int i=1;i<=n;i++) cout<<'O';cout<<endl;vis[0]=true;//提前輸出了，000不能再走了dfs(1);//從001開始搜素return 0; 
}

P10448 組合型枚舉

題目描述

從?1～n?這?n?個整數中隨機選出?m?個，輸出所有可能的選擇方案。

輸入格式

兩個整數?n,m?,在同一行用空格隔開。

輸出格式

按照從小到大的順序輸出所有方案，每行?1?個。

首先，同一行內的數升序排列，相鄰兩個數用一個空格隔開。

其次，對于兩個不同的行，對應下標的數一一比較，字典序較小的排在前面（例如?1 3 5 7?排在?1 3 6 8?前面）。

輸入輸出樣例

輸入 #1復制
5 3
輸出 #1復制
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
說明/提示

對于所有測試數據滿足?0≤m≤n?,?n+(n?m)≤25。

思路

組合嘛，他不能重復，也就是說1 2 3有了后，就不能有2 3 1等等，所以就是我們要的是1 2 3

1 2 4 ，1 2 5,1 3 4,1 3 5,1 4 5,2 3 4這樣子，每個數必須比前面那個大，這樣就保證每次組合都是新的，不重復，我們也不會少某個組合

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>path;
vector<vector<int>>res;
bool visited[100];
void dfs(int start){if(path.size()==m){res.push_back(path);return;}for(int i=start;i<=n;i++){path.push_back(i);dfs(i+1);//從i+1開始我們就能保證后面的一定比前面那個大了path.pop_back();}
}
int main(){cin>>n>>m;dfs(1);for(auto i:res){for(auto j:i){cout<<j<<' ';}cout<<endl;}
}

P10483 小貓爬山

題目描述

Freda 和 rainbow 飼養了?N(N≤18)?只小貓，這天，小貓們要去爬山。經歷了千辛萬苦，小貓們終于爬上了山頂，但是疲倦的它們再也不想徒步走下山了

Freda 和 rainbow 只好花錢讓它們坐索道下山。索道上的纜車最大承重量為?W，而?N?只小貓的重量分別是?C1?,C2?,…CN?。當然，每輛纜車上的小貓的重量之和不能超過?W(1≤Ci?,W≤108)。每租用一輛纜車，Freda 和 rainbow 就要付?1?美元，所以他們想知道，最少需要付多少美元才能把這?N?只小貓都運送下山？

輸入格式

第一行包含兩個用空格隔開的整數，N?和?W。接下來?N?行每行一個整數，其中第?i+1?行的整數表示第?i?只小貓的重量?Ci?。

輸出格式

輸出一個整數，最少需要多少美元，也就是最少需要多少輛纜車。

輸入輸出樣例

輸入 #1復制
5 1996
1
2
1994
12
29
輸出 #1復制
2

思路?

裝箱問題：將?n?個物品裝入若干個容量為?m?的容器，要求每個容器內物品總重量不超過?m，目標是找到使用最少容器數量的方案。

直接看代碼吧

#include<bits/stdc++.h>
using namespace std;
int n,m,cat[20],ans=20,w[20];
void dfs(int u,int v){if(v>=ans) return ;//如果當前用的纜車數大于等于之前記錄的最少纜車數量，那就直接返回不用再裝了 if(u==n){//已經全搜過了就不用再搜了，同時更新答案ans=v;return; }//第一種選擇，用之前用過的纜車 for(int i=0;i<v;i++){if(w[i]+cat[u]<=m){w[i]+=cat[u];dfs(u+1,v);w[i]-=cat[u];}}//第二種，用新的w[v]=cat[u];dfs(u+1,v+1);//繼續去搜索之后的貓 
}
int main(){cin>>n>>m;ans=n;for(int i=0;i<n;i++){cin>>cat[i];}sort(cat,cat+n,greater<int>());dfs(0,0);cout<<ans;return 0;
}

P8604 [藍橋杯 2013 國 C] 危險系數

題目描述

地道的多個站點間有通道連接，形成了龐大的網絡。但也有隱患，當敵人發現了某個站點后，其它站點間可能因此會失去聯系。

我們來定義一個危險系數?DF(x,y)：

對于兩個站點?x?和?y(x=y),?如果能找到一個站點?z，當?z?被敵人破壞后，x?和?y?不連通，那么我們稱?z?為關于?x,y?的關鍵點。相應的，對于任意一對站點?x?和?y，危險系數?DF(x,y)?就表示為這兩點之間的關鍵點個數。

本題的任務是：已知網絡結構，求兩站點之間的危險系數。

輸入格式

輸入數據第一行包含?2?個整數?n(2≤n≤1000)，m(0≤m≤2000)，分別代表站點數，通道數。

接下來?m?行，每行兩個整數?u,v(1≤u,v≤n,u=v)?代表一條通道。

最后?1?行，兩個數?u,v，代表詢問兩點之間的危險系數?DF(u,v)。

輸出格式

一個整數，如果詢問的兩點不連通則輸出??1。

輸入輸出樣例

輸入 #1復制
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

思路

遍歷圖，從初始點dfs然后把所有能走到終點的路都走一遍，記錄有幾條路，記錄每個節點走幾次，如果有節點走的次數跟路徑相同，那就說明這個節點是每條路都要走的，哪題一消失，那我們包到不了終點，這個就是關鍵點

#include<bits/stdc++.h>
using namespace std;
int n,m;
int M;
int cnt;
bool visited[1010];
int ans[1010];
int ans1;
int x,y; 
void dfs(int x,vector<vector<int>>& graph){if(x==y){cnt++;for(int i=1;i<=M;i++){//遍歷一下所有編號，可能有的編號不存在//所以判斷一下是否存在 ans[i]+=visited[i]?1:0;}return; }visited[x]=1;for(auto i:graph[x]){if(!visited[i]) dfs(i,graph);}visited[x]=false;//這節點走完就回溯 
} 
int main(){cin>>n>>m;vector<vector<int>>graph(1010);while(m--){int u,v;cin>>u>>v;graph[u].push_back(v);graph[v].push_back(u);M=max(max(M,u),v);//記錄一下最大節點的編號 }cin>>x>>y;dfs(x,graph);//從u開始搜索 for(int i=1;i<=M;i++){if(ans[i]==cnt) ans1++;} cout<<ans1-1;//減去初始點 
}

P9011 [USACO23JAN] Air Cownditioning II B

題目描述

農夫約翰的?N?頭奶牛?(1≤N≤20)?住在一個谷倉里，谷倉里有連續的牛欄，編號為?1?100?。奶牛?i?占據了編號?[si?,ti?]?的牛欄。不同奶牛占據的牛欄范圍是互不相交的。奶牛有不同的冷卻要求，奶牛?i?占用的每個牛欄的溫度必須至少降低?ci??單位。

谷倉包含?M?臺空調，標記為?1?M?(1≤M≤10)。第?i?臺空調需要花費?mi??單位的金錢來運行?(1≤mi?≤1000)?，如果運行，第?i?臺空調將牛欄?[ai?,bi?]?所有牛欄的溫度降低?pi?（1≤pi?≤106）。空調覆蓋的牛欄范圍可能會重疊。

請幫助農夫約翰求出滿足所有奶牛需求要花費的最少金錢。

輸入格式

第一行兩個整數，分別為?N?和?M。

第?2?至?(N+1)?行，每行三個整數，分別為?si?、ti??和?ci??。

第?(N+2)?至?(M+N+1)?行，每行四個整數，分別為?ai?、bi?、pi??和?mi?。

輸出格式

一個整數，表示最少花費的金錢。

顯示翻譯

題意翻譯

輸入輸出樣例

輸入 #1復制
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5
輸出 #1復制
10
說明/提示

樣例解釋 1

一種花費最少的可能解決方案是選擇那些冷卻區間為?[2,9]?、[1,2]?和?[6,9]?的空調，成本為?3+2+5=10?.

對于?100%?的數據，1≤N≤20，?1≤M≤10,?1≤ai?,bi?,si?,ti?≤100,?1≤ci?,pi?≤106，?1≤mi?≤1000。

思路

就是一路兩搜索，選或不選這個空調，就好，只不過多注意細節，可以利用差分，我這里就沒用

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,k,ans=1e9;//n頭牛，m個空調
//第i頭牛占據s[i]到t[i]的牛欄 ，每頭牛i占的柵欄必須降低c[i]
//第i個空調需要花M[i],第i個空調能讓a[i]到b[i]降低p[i] 
int s[N],t[N],c[N],a[N],b[N],p[N],M[N],w[N];
bool check(){for(int i=1;i<=k;i++){//如果還有某個牛所處區域的空調沒到達c[i]//因為我們是預處理最開始都等于c[i]所以這里是判斷是否大于0 if(w[i]>0) return false; }return 1; 
}
void dfs(int deep,int s){if(deep>m){//如果搜索完一遍if(check())ans=min(ans,s);return;}for(int i=a[deep];i<=b[deep];i++) w[i]-=p[deep];dfs(deep+1,s+M[deep]);//選這個空調  for(int i=a[deep];i<=b[deep];i++) w[i]+=p[deep];dfs(deep+1,s);//不選當前這個第deep號空調
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i]>>t[i]>>c[i];k=max(k,t[i]);for(int j=s[i];j<=t[i];j++){w[j]+=c[i];}}for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>p[i]>>M[i];dfs(1,0);cout<<ans;
}

P10294 [CCC 2024 J5] Harvest Waterloo

題目描述

有一款新出現的廣受歡迎的收割模擬游戲叫做 Harvest Waterloo。游戲在一塊矩形南瓜地上進行，南瓜地里有成捆的干草和不同大小的南瓜。游戲開始時，一個農民在其中一個南瓜的位置上。

農民通過在整片土地上向左、向右、向上或向下移動來收割南瓜。農民不能斜著移動，不能穿過干草，也不能離開田地。

你的工作是確定農民收獲的南瓜的總價值。其中一個小南瓜值?1?美元，一個中等大小的南瓜值?5?美元，而一個大南瓜值?10?美元。

輸入格式

輸入的第一行是一個整數?R>0?表示南瓜地的行數。

第二行是一個整數?C>0?表示南瓜地的列數。

接下來?R?行描述了整個南瓜地。每行包含?C?個字符并且每個字符要么表示一個南瓜，要么表示干草：S?表示小南瓜，M?表示中等大小的南瓜，L?表示一個大南瓜，*?表示干草。

下一行包含一個整數?A?滿足?0≤A<R，最后一行是一個整數?B?滿足?0≤B<C。表示農民一開始在第?A?行第?B?列的位置。南瓜地的左上角稱為第?0?行第?0?列。

輸出格式

輸出一個整數?V?表示農民能夠收割的南瓜的總價值。

輸入輸出樣例

輸入 #1復制
6
6
**LMLS
S*LMMS
S*SMSM
******
LLM*MS
SSL*SS
5
1
輸出 #1復制
37
輸入 #2復制
6
6
**LMLS
S*LMMS
S*SMSM
***SLL
LLM*MS
SSL*SS
2
4
輸出 #2復制
88
【數據范圍】

本題采用捆綁測試。

對于所有數據，保證?1≤R,C≤105，1≤R×C≤105。

下面的表格顯示了?15?分的分配方案：

分值描述范圍
1 南瓜地很小并且不存在干草。 R×C≤100
4 南瓜地很小并且干草把南瓜地分割為一些矩形區域。 R×C≤100
5 南瓜地很小并且干草可以在任意位置。 R×C≤100
5 南瓜地可能很大并且干草可以在任意位置。 R×C≤105

分值	描述	范圍
1	南瓜地很小并且不存在干草。	R×C≤100
4	南瓜地很小并且干草把南瓜地分割為一些矩形區域。	R×C≤100
5	南瓜地很小并且干草可以在任意位置。	R×C≤100
5	南瓜地可能很大并且干草可以在任意位置。	R×C≤105

思路

依舊是簡單點洪水填充問題，直接看代碼

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
vector<string> grid(N);
void dfs(int i,int j){if(i<0||j<0||i==n||j==m||(grid[i][j]!='L'&&grid[i][j]!='M'&&grid[i][j]!='S'))return;if(grid[i][j]=='L') grid[i][j]='l';if(grid[i][j]=='S') grid[i][j]='s';if(grid[i][j]=='M') grid[i][j]='m';dfs(i,j+1);dfs(i,j-1);dfs(i+1,j);dfs(i-1,j);}
int l,s,m1;
int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>grid[i];}int x,y;cin>>x>>y;dfs(x,y);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='l') l+=10;if(grid[i][j]=='m') m1+=5;if(grid[i][j]=='s') s++;}}cout<<l+m1+s;
}