1.木棒
167. 木棒 - AcWing題庫
喬治拿來一組等長的木棒，將它們隨機地砍斷，使得每一節木棍的長度都不超過?5050?個長度單位。
然后他又想把這些木棍恢復到為裁截前的狀態，但忘記了初始時有多少木棒以及木棒的初始長度。
請你設計一個程序，幫助喬治計算木棒的可能最小長度。
每一節木棍的長度都用大于零的整數表示。
解題思路
我們先將所有木棒總長度與其中最長的木棍長度記錄下來。將記錄小木棍長度的數組排序，然后從最長的木棍枚舉每根木棒可能的長度，優化：根據這個小木棒能不能被sum整除來進行第一次判斷這個小木棒長度是否正確。進入bfs三個參數，u：構造了多少小木棍，cur：構造小木棍的長度，cnt：數組下標。
我們依次用斷掉的木棍來湊出我們枚舉的木棍長度并將當前枚舉的木棍標記為已使用，當前木棍湊不出來就取消當前木棍的已使用標記，此處可進行一個優化：當第一個木棍與最后一個木棍搜索失敗時，就一定搜不到了(第一個木棍搜不到了，那它就永遠湊不出來了。最后一個也是，肯定是將前面的都用完之后再用的最后一個，不行肯定就是失敗了) 優化：我們可以將長度相同的小木棍跳過，當當前湊的小木棍長度乘湊的小木棍根數等于木棒從長度時就return true; 當當前小木棍長度等于枚舉的小木棍長度時就進入下一個小木棍的枚舉。
AC代碼
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;int n;
int a[100];
int len=0,sum=0;
bool judge[100];
//u:構造了多少根小木棍,cur:構造小木棍的長度,cnt:數組下標
bool dfs(int u,int cur,int cnt)
{if(cur*u==sum)//湊夠了{//由于初始傳入的len所以當最后一次cur==len時，沒有經過下面u+1，所以u是剛好的// cout<<"u: "<<u<<endl;// for(int i=0;i<n;i++)// cout<<judge[i]<<' ';// cout<<endl;return true;}if(cur==len)//這根木棍達到len了，換下一根木棍return dfs(u+1,0,0);for(int i=cnt;i<n;i++){if(judge[i])continue;if(cur+a[i]<=len){judge[i]=true;if(dfs(u,cur+a[i],i+1))return true;//直接成功judge[i]=false;//失敗了，當沒用過}//第一個木棍就搜索不到答案,或者//最后一個木棍搜索失敗if(!cur||cur+a[i]==len){return false;}int j=i+1;while(j<n&&a[i]==a[j]) j++;i=j-1;//將重復的i跳過，排序的作用}return false;
}int main()
{while(scanf("%d",&n)&&n!=0){sum=0;len=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];//計算所有木棍總長度len=max(len,a[i]);//len肯定不能比零散的木棍小}memset(judge,false,sizeof(judge));sort(a,a+n,greater<int>());while(1){if(sum%len==0&&dfs(0,len,0))//傳入len的話{cout<<len<<endl;break;}len++;}}return 0;
}2. 飛機降落
4957. 飛機降落 - AcWing題庫
有?NN?架飛機準備降落到某個只有一條跑道的機場。
其中第?ii?架飛機在?TiTi?時刻到達機場上空，到達時它的剩余油料還可以繼續盤旋?DiDi?個單位時間，即它最早可以于?TiTi?時刻開始降落，最晚可以于?Ti+DiTi+Di?時刻開始降落。
降落過程需要?LiLi?個單位時間。
一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落。
請你判斷?NN?架飛機是否可以全部安全降落。
解題思路
我們可以用一個結構體來存儲輸入的到達的時刻與可以盤旋的時間與下降所需的時間(根據題目可以看出，下降所需時間不算在可以盤旋的時間里)我這里用pair<int,pair<int,int>>來存儲的，看起來會麻煩些。
bool dfs參數：cnt來記錄有多少飛機已經降落，ti表示當前的時刻(注意：會有當前時刻到達的飛機都降落完了，就要跳到下一個時間)
每一次都要從第一架飛機開始枚舉，看如果當前這架飛機沒有降落并且超過了到達時間+盤旋時間就失敗了返回false，判斷一下時間有沒有到沒有到就將時間改為降落時間(上面要用一個臨時變量記錄時間，這里改變的也是臨時變量)然后看這架飛機沒走過就將其標記為走過然后遞歸看這里讓這架飛機飛能不能讓飛機全飛完，不能就取消對這架飛機的標記。當降落的飛機==飛機總數時就返回true，根據返回值輸出 YES或NO
AC代碼
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
int n;
pair<int,pair<int,int>> car[15];
bool st[15];//判斷飛機是否降落//cnt判斷有幾架飛機降落了,ti是時間
bool dfs(int cnt,int ti)
{if(cnt==n) return true;for(int i=0;i<n;i++){int tmp=ti;//可能有的飛機沒到點需要改成到的時刻if(!st[i]&&ti>car[i].first+car[i].second.first)//這一架沒降落,并且時間超時return false;if(tmp<car[i].first)//現在沒到i這架飛機的到達時刻tmp=car[i].first;if(!st[i]){st[i]=true;if(dfs(cnt+1,tmp+car[i].second.second)) return true;st[i]=false;}}return false;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);//分別是到達的時刻，還能停留的時間，降落所需時間for(int i=0;i<n;i++)scanf("%d%d%d",&car[i].first,&car[i].second.first,&car[i].second.second);memset(st,false,sizeof st);if(dfs(0,0)) printf("YES\n");else printf("NO\n");}return 0;
}3. 母親的牛奶
1355. 母親的牛奶 - AcWing題庫
農夫約翰有三個容量分別為?A,B,CA,B,C?升的擠奶桶。
最開始桶?AA?和桶?BB?都是空的，而桶?CC?里裝滿了牛奶。
有時，約翰會將牛奶從一個桶倒到另一個桶中，直到被倒入牛奶的桶滿了或者倒出牛奶的桶空了為止。
這一過程中間不能有任何停頓，并且不會有任何牛奶的浪費。
請你編寫一個程序判斷，當?AA?桶是空的時候，CC?桶中可能包含多少升牛奶，找出所有的可能情況。
解題思路
這幾個桶只要有牛奶可以互相倒牛奶，只有兩種可能把要倒的桶倒滿或者把自己倒空
用一個結構體包含abc代表當前各個瓶子奶的容量，由于數據量很小所以我們可以用一個三維數組來存它的狀態，創建一個隊列存上面的結構體，枚舉一個瓶子倒一個瓶子接(不能是同一個瓶子)，根據要倒牛奶瓶子的牛奶量和要接牛奶瓶子的剩余空間，來更新隊列依次直到隊列空。
我們遍歷狀態數組，輸出所有當A瓶子為空時有過的C的值
AC代碼
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
struct node
{int a,b,c;//記錄當前a，b，c分別多少牛奶
};
int A,B,C;
bool st[25][25][25];//當值為true說明三個下標表示三個杯子分別盛的容量
queue<node> q;
int bfs(int a,int b,int c)
{q.push({a,b,c});//入隊int val[3]={A,B,C};st[a][b][c]=true;while(!q.empty()){node t=q.front();q.pop();for(int i=0;i<3;i++)//枚舉第i個桶向第j個桶里倒牛奶{for(int j=0;j<3;j++){if(i!=j)//不能自己給自己倒{int s[3]={t.a,t.b,t.c};if(s[i]==0)continue;//比較i個桶剩的牛奶，與第j桶還能放進去的牛奶，哪個更少int cmp=min(s[i],val[j]-s[j]);s[i]-=cmp;//i桶減去s[j]+=cmp;//j桶加上if(!st[s[0]][s[1]][s[2]]){st[s[0]][s[1]][s[2]]=true;q.push({s[0],s[1],s[2]});}}}}}
}int main()
{scanf("%d%d%d",&A,&B,&C);//分別能存儲的容量bfs(0,0,C);for(int j=0;j<=C;j++){for(int i=0;i<=B;i++){if(st[0][i][j])printf("%d ",j);}}return 0;
}4. 全球變暖
1233. 全球變暖 - AcWing題庫
你有一張某海域?N×NN×N?像素的照片，”.”表示海洋、”#”表示陸地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中”上下左右”四個方向上連在一起的一片陸地組成一座島嶼，例如上圖就有?22?座島嶼。
由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒。
具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒。
例如上圖中的海域未來會變成如下樣子：
.......
.......
.......
.......
....#..
.......
.......
請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒。
?解題思路
就是遍歷所有的大陸，查看陸地數量與臨海的陸地數量是否相同，其余就是普通的洪水覆蓋模板
AC代碼
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;int n;
char map[1010][1010];
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
queue<pair<int,int>> qu;
bool states[1010][1010];int cnt=0;
void bfs(int x,int y,int &sum1,int &sum2)
{qu.push({x,y});states[x][y]=true;while(!qu.empty()){auto t=qu.front();sum1++;qu.pop();bool falg=false;for(int i=0;i<4;i++){int a=t.first+dx[i];int b=t.second+dy[i];if(a<0||b<0||a>=n||b>=n) continue;if(states[a][b]) continue;//已經走過的if(map[a][b]=='.'){falg=true;//說明上一個鄰海continue;}qu.push({a,b});states[a][b]=true;}if(falg) sum2++;//統計臨海的數量}if(sum2==sum1)cnt++;}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){ cin>>map[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){ int cnt1=0;//記錄島嶼邊緣數量int cnt2=0;//記錄島嶼陸地數量if(!states[i][j]&&map[i][j]=='#')bfs(i,j,cnt1,cnt2);} }cout<<cnt<<endl;return 0;
}
會導致空指針嗎)
