目錄

?B4158 [BCSP-X 2024 12 月小學高年級組] 質數補全

思路

B4279 [藍橋杯青少年組國賽 2023] 數獨填數、

思路

P5198 [USACO19JAN] Icy Perimeter S

思路

P5429 [USACO19OPEN] Fence Planning S

思路?

P6111 [USACO18JAN] MooTube S

思路

P6207 [USACO06OCT] Cows on Skates G

P6591 [YsOI2020] 植樹

思路

總結

P6691 選擇題

思路

P7228 [COCI 2015/2016 #3] MOLEKULE

思路

P7995 [USACO21DEC] Walking Home B

思路?

P8838 [傳智杯 #3 決賽] 面試

思路

P9304 「DTOI-5」3-1

思路?

P10095 [ROIR 2023] 斐波那契乘積 (Day 1)

思路

P10386 [藍橋杯 2024 省 A] 五子棋對弈

思路?

P10490 Missile Defence System

思路

P10477 Subway tree systems

思路

P12317 [藍橋杯 2024 國 C] 樹的結點值

思路

---

?B4158 [BCSP-X 2024 12 月小學高年級組] 質數補全

題目描述

Alice 在紙條上寫了一個質數，第二天再看時發現有些地方污損看不清了。

• 在大于?1?的自然數中，除了?1?和它本身以外不再有其他因數的自然數稱為質數

請你幫助 Alice 補全這個質數，若有多解輸出數值最小的，若無解輸出??1。

例如紙條上的數字為?1?（??代表看不清的地方），那么這個質數有可能為?11,13,17,19，其中最小的為?11。

輸入格式

第一行?1?個整數?t，代表有?t?組數據。

接下來?t?行，每行?1?個字符串?s?代表 Alice 的數字，僅包含數字或者??，并且保證首位不是???或者?0。

輸出格式

輸出?t?行，每行?1?個整數代表最小可能的質數，或者??1?代表無解。

輸入輸出樣例

輸入 #1復制

10
1*
3**
7**
83*7
2262
6**1
29*7
889*
777*
225*

輸出 #1復制

11
307
701
8317
-1
6011
2917
8893
-1
2251

輸入 #2復制

10
4039***
2***5*5
4099961
25**757
7***0**
1***00*
41811*9
6***0*7
8***1**
6561*59

輸出 #2復制

4039019
-1
4099961
2509757
7000003
1000003
4181129
6000047
8000101
6561259

說明/提示

數據范圍

∣s∣?代表?s?串的長度，對于所有數據，1≤t≤10,1≤∣s∣≤7，s?中僅包含數字或者??，并且保證首位不是???或者?0。

本題采用捆綁測試，你必須通過子任務中的所有數據點以及其依賴的子任務，才能獲得子任務對應的分數。

子任務編號	分值	∣s∣	特殊性質	子任務依賴
1	35	≤7	s?中沒有??
2	30	≤4
3	24	≤7	s?中至多包含?1?個??	1
4	11	≤7		1,2,3

思路

這題我看了題解，整體思路我是會的，就像之前寫的題一樣，看有幾個*然后對每個*都for循環就好，唯一的一點就是要用個數組記錄哪些索引是*，最開始我把這玩意忘了，然后一直差點意思，還有就是那個字符串轉為數字的函數，剩下看代碼吧也沒啥講的

#include<bits/stdc++.h>
using namespace std;
bool isPrime(string nums) {int num=atoi(nums.c_str());if (num <= 1) return false;if (num == 2) return true;if (num % 2 == 0) return false;for (int i = 3; i * i <= num; i += 2) {if (num % i == 0) return false;}return true;}
string s;
int pos[10],p;
bool flag=false; 
void dfs(int t,string str){if(flag) return;if(t>p){if(isPrime(str)){cout<<str<<endl;flag=1;}return ;}int c=pos[t];//取出現在要更改的*的索引if(c==0){for(int i=1;i<=9;i++){str[c]=i+'0';dfs(t+1,str);str[c]='*';}}else{for(int i=0;i<=9;i++){str[c]=i+'0';dfs(t+1,str);str[c]='*';}}
}
int main(){int t;cin>>t;while(t--){cin>>s;p=0;for(int i=0;i<s.size();i++){if(s[i]=='*'){pos[++p]=i;//用pos數組記錄每一個*的索引 }}flag=false;if(p==0){if(isPrime(s)) cout<<s<<endl;else{cout<<-1<<endl;;}}else{dfs(1,s);if(!flag) cout<<-1<<endl;}}}

---

B4279 [藍橋杯青少年組國賽 2023] 數獨填數、

題目背景

本題使用的數獨均較為簡單，不接受 hack 數據，感興趣的同學可以查看?此題目?的說明/提示部分。

題目描述

數獨是源自 18 世紀瑞士的一種數學游戲。玩家需要根據?9×9?網格上的已知數字，將剩余的所有空格填上數字，使得：

1. 每一行包含數字?1～9?且不重復；
2. 每一列包含數字?1～9?且不重復；
3. 每一個?3×3?方塊（粗線劃分）包含數字?1～9?且不重復。

輸入格式

共有?9?行，表示未完成的數獨：

• 每行包含?9?個字符（字符只能為?1～9?的數字和?.）；
• .?表示數獨上的空格；
• 題目數據保證數獨有效且答案唯一。

輸出格式

輸出?9?行，表示已完成的數獨：

• 每行?9?個數字，數字之間沒有空格及其他字符。

輸入輸出樣例

輸入 #1復制

17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.

輸出 #1復制

174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734

思路

其實和八皇后差不多，就是一個一個看數，還需要個check函數來檢查這個數行不行，不行就回溯沒啥很難的地方，就是注意dfs函數返回值是bool，有時候會因為這個返回值的原因，我們最終這個函數一直運行不下去看代碼吧

#include<bits/stdc++.h>
using namespace std;
vector<string>grid(9);
bool check(int i,int j,char k){
//看這一行是否滿足for(int col=0;col<9;col++){if(grid[i][col]==k) return false;}
//看列是否滿足for(int row=0;row<9;row++){if(grid[row][j]==k) return false;}
//看九宮格滿足不int row=(i/3)*3;int col=(j/3)*3;for(int new_row=row;new_row<row+3;new_row++){for(int new_col=col;new_col<col+3;new_col++){if(grid[new_row][new_col]==k) return false;}}return true;
}
bool dfs(){for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(grid[i][j]=='.'){for(char k='1';k<='9';k++){if(check(i,j,k)){grid[i][j]=k;if(dfs())return true;grid[i][j]='.';}}return false;//這9個都不行的話說明前面出錯了，就false}}}return true;
}
int main(){for(int i=0;i<9;i++){cin>>grid[i];}if(dfs()){for(int i=0;i<9;i++){cout<<grid[i]<<endl;}	}}

---

P5198 [USACO19JAN] Icy Perimeter S

題目背景

USACO 一月月賽銀組第二題

題目描述

Farmer John 要開始他的冰激凌生意了！他制造了一臺可以生產冰激凌球的機器，然而不幸的是形狀不太規則，所以他現在希望優化一下這臺機器，使其產出的冰激凌球的形狀更加合理。 機器生產出的冰激凌的形狀可以用一個?N×N（1≤N≤1000）的矩形圖案表示，例如：

##....
....#.
.#..#.
.#####
...###
....##

每個?.?字符表示空的區域，每個?#?字符表示一塊?1×1?的正方形格子大小的冰激凌。

不幸的是，機器當前工作得并不是很正常，可能會生產出多個互不相連的冰激凌球（上圖中有兩個）。一個冰激凌球是連通的，如果其中每個冰激凌的正方形格子都可以從這個冰激凌球中其他所有的冰激凌格子出發重復地前往東、南、西、北四個方向上相鄰的冰激凌格子所到達。

Farmer John 想要求出他的面積最大的冰激凌球的面積和周長。冰激凌球的面積就是這個冰激凌球中?#?的數量。如果有多個冰激凌球并列面積最大，他想要知道其中周長最小的冰激凌球的周長。在上圖中，小的冰激凌球的面積為?2，周長為?6，大的冰激凌球的面積為?13，周長為?22。

注意一個冰激凌球可能在中間有“洞”（由冰激凌包圍著的空的區域）。如果這樣，洞的邊界同樣計入冰激凌球的周長。冰激凌球也可能出現在被其他冰激凌球包圍的區域內，在這種情況下它們計為不同的冰激凌球。例如，以下這種情況包括一個面積為?1?的冰激凌球，被包圍在一個面積為?16?的冰激凌球內：

#####
#...#
#.#.#
#...#
#####

同時求得冰激凌球的面積和周長十分重要，因為 Farmer John 最終想要最小化周長與面積的比值，他稱這是他的冰激凌的“冰周率”。當這個比率較小的時候，冰激凌化得比較慢，因為此時冰激凌單位質量的表面積較小。

輸入格式

輸入的第一行包含?N，以下?N?行描述了機器的生產結果。其中至少出現一個?#?字符。

輸出格式

輸出一行，包含兩個空格分隔的整數，第一個數為最大的冰激凌球的面積，第二個數為它的周長。如果多個冰激凌球并列面積最大，輸出其中周長最小的那一個的信息。

輸入輸出樣例

輸入 #1復制

6
##....
....#.
.#..#.
.#####
...###
....##

輸出 #1復制

13 22

思路

很簡單哈，就是給你輸入的這個矩陣的周圍都加一圈‘ .’，因為我們要求周長實際上九算出每個#周圍有幾個' . '，然后我們每次dfs就看一下新更新后的面積和周長跟以前以前的誰大誰小就好?，這還是洪水填充，，，自認為寫的很漂亮的代碼哈哈，，其實很容易就RE了我最開始設的resize是110，然后就RE了后來改為n+2就AC了很緊湊吧這個數據范圍

#include<bits/stdc++.h>
using namespace std;
vector<vector<char>>grid;
int ans_point,ans_ice;
int n;
void dfs(int i,int j){if(i<0||j<0||i>n||j>n||grid[i][j]!='#') return;grid[i][j]='x';//冰淇淋變成xans_ice++;if(grid[i+1][j]=='.') ans_point++;if(grid[i-1][j]=='.') ans_point++;if(grid[i][j-1]=='.') ans_point++;if(grid[i][j+1]=='.') ans_point++;dfs(i+1,j);dfs(i-1,j);dfs(i,j+1);dfs(i,j-1);
}
int main(){cin>>n;grid.resize(n+2,vector<char>(n+2,'.'));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>grid[i][j];}}int ans_point1=ans_point;int ans_ice1=ans_ice;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(grid[i][j]=='#'){dfs(i,j);}if(ans_ice>ans_ice1){ans_ice1=ans_ice;ans_point1=ans_point;}else if(ans_ice1==ans_ice){if(ans_point<ans_point1){ans_point1=ans_point;}}ans_ice=0;ans_point=0;}}cout<<ans_ice1<<' '<<ans_point1;
}

---

P5429 [USACO19OPEN] Fence Planning S

題目描述

Farmer John 的?N?頭奶牛，編號為?1…N?（?2≤N≤105?），擁有一種圍繞“哞網”，一些僅在組內互相交流卻不與其他組進行交流的奶牛小組，組成的復雜的社交網絡。

每頭奶牛位于農場的二維地圖上的不同位置?(x,y)?，并且我們知道有?M?對奶牛(?1≤M<105?)會相互哞叫。兩頭相互哞叫的奶牛屬于同一哞網。

為了升級他的農場，Farmer John 想要建造一個四邊與?x?軸和?y?軸平行的長方形圍欄。Farmer John 想要使得至少一個哞網完全被圍欄所包圍（在長方形邊界上的奶牛計為被包圍的）。請幫助 Farmer John 求出滿足他的要求的圍欄的最小可能周長。有可能出現這一圍欄寬為?0?或高為?0?的情況。

輸入格式

輸入的第一行包含?N?和?M?。以下?N?行每行包含一頭奶牛的?x?坐標和?y?坐標（至多?108?的非負整數）。以下?M?行每行包含兩個整數?a?和?b?，表示奶牛?a?和?b?之間有哞叫關系。每頭奶牛都至少存在一個哞叫關系，并且輸入中不會出現重復的哞叫關系。

輸出格式

輸出滿足 Farmer John 的要求的圍欄的最小周長。

輸入輸出樣例

輸入 #1復制

7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 6

輸出 #1復制

10

思路?

因為可能有好幾個圖，然后我們要找最小周長，所以我們就要對每個沒有遍歷過的點都dfs，然找到最小周長，用一個vis數組來標識是否遍歷過就好

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int U,D,L,R,ans=INT_MAX,n,m;//U就是up，D就是down， 
bool vis[N];
//建圖 
struct edge{int to;int next;
}graph[N*2];
int head[N],cnt;
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;
} 
//用結構體的話就省一個數組也是比較方便哈 
struct cow{int x,y;
}a[N];
void dfs(int x){vis[x]=1;U=max(U,a[x].y),D=min(D,a[x].y);R=max(R,a[x].x),L=min(L,a[x].x);for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;if(!vis[to]){dfs(to);} }
}
int main(){cin >>n>>m;for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;while(m--){int x,y;cin>>x>>y;add_edge(x,y),add_edge(y,x);}for(int i=1;i<=n;i++) if(!vis[i]){	//沒遍歷過說明是另一張圖U=D=a[i].y,L=R=a[i].x;  dfs(i);ans=min(ans,((U-D)+(R-L))<<1);}cout<<ans;return 0;
}

---

P6111 [USACO18JAN] MooTube S

題目背景

本題與?金組同名題目?在題意上一致，唯一的差別是數據范圍。

題目描述

在業余時間，Farmer John 創建了一個新的視頻共享服務，他將其命名為 MooTube。在 MooTube 上，Farmer John 的奶牛可以錄制，分享和發現許多有趣的視頻。他的奶牛已經發布了?N?個視頻（1≤N≤5000），為了方便將其編號為?1…N?。然而，FJ 無法弄清楚如何幫助他的奶牛找到他們可能喜歡的新視頻。

FJ 希望為每個 MooTube 視頻創建一個“推薦視頻”列表。這樣，奶牛將被推薦與他們已經觀看過的視頻最相關的視頻。

FJ 設計了一個“相關性”度量標準，顧名思義，它確定了兩個視頻相互之間的相關性。他選擇?N?1?對視頻并手動計算其之間的相關性。然后，FJ 將他的視頻建成一棵樹，其中每個視頻是節點，并且他手動將?N?1?對視頻連接。為了方便，FJ 選擇了?N?1?對，這樣任意視頻都可以通過一條連通路徑到達任意其他視頻。 FJ 決定將任意一對視頻的相關性定義為沿此路徑的任何連接的最小相關性。

Farmer John 想要選擇一個?K?值，以便在任何給定的 MooTube 視頻旁邊，推薦所有其他與該視頻至少有?K?相關的視頻。然而，FJ 擔心會向他的奶牛推薦太多的視頻，這可能會分散他們對產奶的注意力！因此，他想設定適當的?K?值。 Farmer John希望得到您的幫助，回答有關?K?值的推薦視頻的一些問題。

輸入格式

第一行輸入包含?N?和?Q（1≤Q≤5000）。

接下來的?N?1?行描述了 FJ 手動比較的一對視頻。 每行包括三個整數?pi?，qi??和?ri?（1≤pi?,qi?≤N，1≤ri?≤109），表示視頻?pi??和?qi??已連接并且相關性為?ri?。

接下來的?Q?行描述了 Farmer John 的?Q?個問題。每行包含兩個整數，ki??和?vi?（1≤ki?≤109，1≤vi?≤N），表示 FJ 的第?i?個問題詢問中當?K=ki??時，第?vi??個視頻推薦列表中將推薦的視頻數。

輸出格式

輸出?Q?行。在第?i?行，輸出 FJ 的第?i?個問題的答案。

輸入輸出樣例

輸入 #1復制

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

輸出 #1復制

3
0
2

思路

也是一個很簡單的一個搜索題，只不過題上那個有一點表達不當可能，我先說一下整體思路吧

就是題上要找與vi相連的至少相關性為ki的節點，我最開始是直接搜索，只要能連起來的相關性大于等于ki的都給計算進去，但是發下樣例出來不對，然后又讀一遍題，發現如果最開始相連的那個節點的相關性小于ki了那我們就不能走這條路了，就不能錯這個節點繼續搜。還有就是每次記得memset清除一下臟數據，其他沒啥，看代碼就行

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
//建圖 
int n,q,ans;
bool visited[N];
struct edge{int to;int next;int w; 
}graph[N*2];
int head[N],cnt;
void add_edge(int u,int v,int w){cnt++;graph[cnt].w=w;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;
} 
void dfs(int x,int k){for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;if(!visited[to]){visited[to]=true;if(graph[i].w>=k){ans++;dfs(to,k);} }}
}
int main(){cin>>n>>q;n--;while(n--){int u,v,w;cin>>u>>v>>w;add_edge(u,v,w);add_edge(v,u,w);}while(q--){int k,u;cin>>k>>u;memset(visited,0,sizeof(visited));ans=0;//都清0，防止上一次搜索的臟數據visited[u]=true;//最開始就已經走過來，先初始化一下，防止之后再走 	dfs(u,k);cout<<ans<<endl;}
}

---

P6207 [USACO06OCT] Cows on Skates G

題目描述

本題使用 Special Judge。

Farmer John 把農場劃分為了一個?r?行?c?列的矩陣，并發現奶牛們無法通過其中一些區域。此刻，Bessie 位于坐標為?(1,1)?的區域，并想到坐標為?(r,c)?的牛棚享用晚餐。她知道，以她所在的區域為起點，每次移動至相鄰的四個區域之一，總有一些路徑可以到達牛棚。

這樣的路徑可能有無數種，請你輸出任意一種，并保證所需移動次數不超過?100000。

輸入格式

第一行兩個整數?r,c。

接下來?r?行，每行?c?個字符，表示 Bessie 能否通過相應位置的區域。字符只可能是?.?或?*。

• .?表示 Bessie 可以通過該區域。
• *?表示 Bessie 無法通過該區域。

輸出格式

若干行，每行包含兩個用空格隔開的整數，表示 Bessie 依次通過的區域的坐標。

顯然，輸出的第一行是?1 1?，最后一行是?r c。

相鄰的兩個坐標所表示的區域必須相鄰。

輸入輸出樣例

輸入 #1復制

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

輸出 #1復制

1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8

說明/提示

【數據范圍】

對于?100%?的數據，1≤r≤113，1≤c≤77。

思路?

第一眼我想用bfs但是咱這個文章是dfs所以我就繼續dfs了，唯一比較容易想不好的就是，怎樣輸出，我們用一個全局變量flag，如果輸出了就一直返回就行，我們還要用一個數組來記錄坐標，看代碼吧不多說了? 其實還可以用一個dist數組記錄到達每一個位置最短距離，然后進行比較，這樣我們可以求得到達最終點的最短路徑，有點類似dj算法，只不過dj用的是堆

#include<bits/stdc++.h>
using namespace std;
const int N=120;
int r,c;
bool visited[120][90],flag;
char grid[120][90];
int cd[100010][2];
void dfs(int i,int j,int step){if(i<1||j<1||i>r||j>c||visited[i][j]||grid[i][j]=='*') return;if(flag) return;cd[step][0]=i;cd[step][1]=j;if(i==r&&j==c){for(int t=1;t<=step;t++){cout<<cd[t][0]<<' '<<cd[t][1]<<endl;;}flag=true;return;}visited[i][j]=true;dfs(i+1,j,step+1);dfs(i-1,j,step+1);dfs(i,j-1,step+1);dfs(i,j+1,step+1);
}
int main(){cin>>r>>c;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>grid[i][j];}}dfs(1,1,1);return 0;
}

---

P6591 [YsOI2020] 植樹

題目背景

Ysuperman 響應號召，決定在幼兒園里植樹。

題目描述

Ysuperman 有一棵?n?個節點的無根樹?T。如果你不知道樹是什么，TA 很樂意告訴你，樹是一個沒有環的無向聯通圖。

既然樹是無根的，那就沒有辦法種植。Ysuperman 研究了很久的園藝，發現一個節點如果可以成為根，它必須十分平衡，這意味著以它為根時，與它直接相連的節點，他們的子樹大小都相同。

你作為幼兒園信息組一把手，Ysuperman 給你一棵樹，你能在?1s?內找到所有可能成為根的節點嗎？

輸入格式

第一行一個正整數?n，表示樹的節點個數。

此后?n?1?行，每行兩個正整數?ui?,vi?，表示樹上有一條直接連接?ui?,vi??的邊。保證每條邊只會給出一次。

輸出格式

不超過?n?個從小到大的整數，用空格隔開，表示每一個可能成為根的節點。

輸入輸出樣例

輸入 #1復制

2
1 2

輸出 #1復制

1 2 

輸入 #2復制

4
1 2
2 3
3 4

輸出 #2復制

1 4 

輸入 #3復制

9
1 2
1 3
4 1
5 1
1 6
1 9
8 1
1 7

輸出 #3復制

1 2 3 4 5 6 7 8 9 

說明/提示

樣例說明

樣例說明?1。

以?1?為根時，與?1?直接相連的點有?{2}，因為只有一個所以大小全部相同。

以?2?為根時，與?2?直接相連的點有?{1}，因為只有一個所以大小全部相同。

所以答案為?1,2。

樣例說明?2

以?1?為根時，與?1?直接相連的點有?{2}，因為只有一個所以大小全部相同。

以?2?為根時，與?2?直接相連的點有?{1,3}，子樹大小分別為?{1,2}，不相同。

以?3?為根時，與?3?直接相連的點有?{2,4}，子樹大小分別為?{2,1}，不相同。

以?4?為根時，與?4?直接相連的點有?{3}，因為只有一個所以大小全部相同。

所以答案為?1,4。

數據范圍

本題采用捆綁測試。

subtask	n	分數
1	≤5000	40
2	≤106	60

對于?100%?的數據，滿足?1≤n≤106。

提示

由于輸入輸出量較大，你可能需要快速輸入/輸出。

---

思路

這題不是很難，算每個子樹有多大應該都會吧，前面有個道路修建題也是求子樹大小，就是用dfs求就好，記得在搜索時給子樹大小先初始化為1，因為子樹也自帶一個根節點哈，然后我用的是鏈式前向星沒加速也過了，一萬年給的n確實有點大了，超過1e5我們就用鏈式前向星速度比較快，然后如果你用的是鄰接表你加速一下也能過，推薦用鏈式前向星，這個確實比較好，還有個難點就是，最后要統計該節點所連的子樹大小是否都相同那里，如果這個節點連的是他的父親，那就等于n-sizes[u]，所有節點就、減去這個節點的樹的大小就行，如果不是父親，那就直接=這個節點所連節點樹的大小，你們看代碼應該就能看懂，看不懂仔細想想就行，不是很難，最后記得是從小到大，用一個res數組存起來，sort一下

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=1e6+10;
struct edge{int to;int next;
}graph[N*2];
int cnt,head[N];
int sizes[N],fat[N];//記錄每個樹枝上的孩子有幾個,記錄每個節點他爹是誰 
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;
}
void dfs(int u,int fa){fat[u]=fa;sizes[u]=1;for(int i=head[u];i;i=graph[i].next){int to=graph[i].to;if(to==fa) continue;dfs(to,u);sizes[u]+=sizes[to];}
}
vector<int>res;//記錄想要的答案 
signed main(){cin>>n;//特判一下n=1，因為n等于說明就是只有一個節點 if(n==1) {cout<<1;return 0;}for(int i=1;i<n;i++){int u,v;cin>>u>>v;add_edge(u,v);add_edge(v,u);}//隨便哪個開始搜索都行 dfs(1,0);//遍歷一遍得到sizes，和fa數組for(int u=1;u<=n;u++){unordered_set<int> sz;for(int i=head[u];i;i=graph[i].next){int to=graph[i].to;if(to==fat[u]){sz.insert(n-sizes[u]);}else{sz.insert(sizes[to]);}}if(sz.size()==1)res.push_back(u);}sort(res.begin(),res.end());for(auto i:res){cout<<i<<' ';}}

總結

突然想總結一下? ?就是圖嘛，我們有時候會用visited數組存一下我們走過的路，有時候會弄個父節點防止我們走重復的路，第一種情況是無向有環時我們就需要visited，第二種是無向無環，大家可以自己腦子里思考一下就知道了，有向圖好像不太需要這倆玩意，因為這個文章到現在好像就遇到一個有向圖，然后沒有用這倆，之后再說吧

---

P6691 選擇題

題目背景

小 L 喜歡邏輯推理。

一天，他在一本由英國哲士沃·協德編寫的《我也不知道為什么要叫這個名字的一本有關邏輯學的書》中翻到了一道奇特的問題，但他并不會做。他知道你善于用程序解決問題，于是決定讓你來幫助他完成這些問題。

題目描述

這是一道有?n?個選項的選擇題，每個選項的內容都很獨特。第?i?個選項的內容的形式如下：

• 第?ai??個選項是正確/錯誤的

小 L 認為這種題目的答案不一定是唯一的，所以他想問題這道題有多少種合法的答案（可以全部正確或全部錯誤）。他還想問你這么多答案中，正確選項最多和最少的答案分別有多少個正確選項。

當然，如果這道題不存在合法的答案，你可以直接回答小 L?No answer。

輸入格式

第一行有一個正整數?n，表示選項個數。

接下來?n?行，每行有兩個整數?ai?,opti?，描述一個選項。其中當?opti?=1?時，表示這個選項的內容為?第?ai??個選項是正確的；當?opti?=0?時，表示這個選項的內容為?第?ai??個選項是錯誤的。

輸出格式

如果沒有答案滿足這道選擇題，輸出No answer。

否則輸出三行，每行一個正整數，分別為合法答案數及正確選項最多和最少的答案分別有多少個正確選項。其中合法答案數要對?998244353?取模。

輸入輸出樣例

輸入 #1復制

4
2 1
4 0
1 1
2 0

輸出 #1復制

2
3
1

輸入 #2復制

10
4 1
7 0
2 0
3 1
7 1
5 0
9 1
10 1
8 0
1 1

輸出 #2復制

No answer

說明/提示

對于樣例一，一共有下面?2?種正確答案：

• 第?1,2,3?個選項是正確的。
• 第?4?個選項是正確的。

其中正確選項最多的答案有?3?個選項正確，正確選項最少的答案有?1?個選項正確。

數據范圍

對于?10%?的數據，n≤10。
對于?30%?的數據，n≤100。
對于?60%?的數據，n≤103。
對于?100%?的數據，n≤106,1≤ai?≤n,i=ai?,opti?∈{0,1}。

思路

這題我看題解寫的，因為我沒看出來這是二分圖，看不出來的話想寫出來就很難了，思路就是，我們從第i題開始，隨便染個色（1,0都行）然后開始搜索，搜索這個節點與預期染的色不一樣的話就強制終止程序cout<<"No answer";?exit(0);就這樣，，，，我再但多說一下dfs里面的過程

他的兩個參數分別是要染的節點，和期待染這個節點的顏色，然后如果這個節點我們染過了，那我們就看看這個節點染過的顏色和現在預期染的顏色一不一樣一樣就說明染的沒毛病，不對就說明執行不下去，無法形成二分圖，然后如果沒染過我們就給他染上然后開始準備對他的鄰接點搜索，

唯一比較重點的是，我們要染的色是通過異或來實現，這道題是第 i 個人說第 ai? 個人說的話是真話或是假話。這個真話假話就作為權值，如果第i個人是真話，那么真^（真或假）就由括號里的決定，也就是我們期待染的色，如果是1（真）^（真）1就變成0了，所以我們要真^(!)。還有因為你染一次色把顏色反轉過來就又是一個方案了，所以我們要乘2，然后可能還有多個聯通塊，所以我們就要用個t記錄有幾個聯通快，然后算一下方案數,,

我再詳細說一下異或那里，如果當前節點的狀態是1，與鄰接節點的權重是0，那就是真碰上假，那這個to的期望狀態就一

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10; 
struct edge{int to;int next;int w;
}graph[N*2];
int cnt,head[N];
void add_edge(int u,int v,int w){cnt++;graph[cnt].to=v;graph[cnt].w=w;graph[cnt].next=head[u];head[u]=cnt;
}
int n,color[N],sum[2];// color記錄節點染色情況，sum統計顏色數量
bool visited[N];       // 訪問標記
int t,ans_min,ans_max; // 連通塊數量，最小和最大值void dfs(int x,int state){if(visited[x]){if(color[x]!=state){ // 染色沖突檢測cout<<"No answer";exit(0);}return;}visited[x]=true;color[x]=state;sum[state]++;for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;int expected=state^(!graph[i].w); // 鄰接節點期望顏色dfs(to, expected);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;add_edge(i,v,w);add_edge(v,i,w);}int ans=1;for(int i=1;i<=n;i++){if(!visited[i]){sum[0]=sum[1]=0;dfs(i,0); // 嘗試以顏色0開始染色// 統計當前連通塊的兩種顏色數量ans_min+=min(sum[0],sum[1]);ans_max+=max(sum[0],sum[1]) ;t++;}}for(int i=1;i<=t;i++){ans =(ans*2) % 998244353;}cout<<ans<<endl<<ans_max<<endl<<ans_min;return 0;
}

---

P7228 [COCI 2015/2016 #3] MOLEKULE

題目描述

有?N?個點和?N?1?條無向邊，定義一張有向圖的代價為一條在這張有向圖上的最長通路長度。

現在把這?N?1?條無向邊指定方向，使得形成的有向圖代價最小。

求一種指定方向的方案。

輸入格式

第一行一個整數?N?代表點數。
接下來?N?1?行每行兩個整數?ai?,bi??代表一條邊。

輸出格式

N?1?行每行一個整數?r：

• 如果?r=1?代表從?ai??連向?bi?。
• 如果?r=0?代表從?bi??連向?ai?。

輸入輸出樣例

輸入 #1復制

3
1 2
2 3

輸出 #1復制

1
0

輸入 #2復制

4
2 1
1 3
4 1

輸出 #2復制

0
1
0

說明/提示

樣例 1 解釋

如下圖所示：

這張圖的代價為?1，注意?0?1?也是一組最優解。

樣例 2 解釋

如下圖所示：

數據規模與約定

對于?30%?的數據，N≤20。
對于?100%?的數據，2≤N≤105，1≤ai?,bi?≤N。

本題采用 Special Judge。
你只需要輸出任意一種合法方案。

思路

這題挺有意思，就是把一個圖變成下面這樣，這兩種都行，我不知道還有沒有別的了哈，反正這倆就是我能想出來的

然后怎么變呢，我們以深度為序號，然后找出奇偶，1深度為0,2深度為1從第二個開始奇數的指向別的節點（我選擇的是第一個），3深度為2，偶數被指向，那最后也就是我們可以輸出他們&1的值，以他們是否為偶數來輸出答案，因為題目輸出的也就是0和1，其實都行，題目實際意思就是讓你判斷這些節點是不是偶數

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge{int to;int next;	
}graph[N*2];
int cnt,head[N];
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;
}
int n,depth[N];
void dfs(int x,int fa){depth[x]=depth[fa]+1;for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;if(to!=fa){dfs(to,x);}}
}
int main(){cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;add_edge(u,v);add_edge(v,u);}dfs(1,-1);for(int i=1;i<n;i++){int y=graph[i*2-1].to;cout<<(depth[y]&1)<<endl;//奇數的話被指，偶數的話指向別的 }
}

---

P7995 [USACO21DEC] Walking Home B

題目描述

奶牛 Bessie 正準備從她最喜愛的草地回到她的牛棚。

農場位于一個?N×N?的方陣上（2≤N≤50），其中她的草地在左上角，牛棚在右下角。Bessie 想要盡快回家，所以她只會向下或向右走。有些地方有草堆（haybale），Bessie 無法穿過；她必須繞過它們。

Bessie 今天感到有些疲倦，所以她希望改變她的行走方向至多?K?次（1≤K≤3）。

Bessie 有多少條不同的從她最愛的草地回到牛棚的路線？如果一條路線中 Bessie 經過了某個方格而另一條路線中沒有，則認為這兩條路線不同。

輸入格式

每個測試用例的輸入包含?T?個子測試用例，每個子測試用例描述了一個不同的農場，并且必須全部回答正確才能通過整個測試用例。輸入的第一行包含?T（1≤T≤50）。每一個子測試用例如下。

每個子測試用例的第一行包含?N?和?K。

以下?N?行每行包含一個長為?N?的字符串。每個字符為?.，如果這一格是空的，或?H，如果這一格中有草堆。輸入保證農場的左上角和右下角沒有草堆。

輸出格式

輸出?T?行，第?i?行包含在第?i?個子測試用例中 Bessie 可以選擇的不同的路線數量。

輸入輸出樣例

輸入 #1復制

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

輸出 #1復制

2
4
6
2
0
0
6

說明/提示

【樣例解釋】

我們將使用一個由字符 D 和 R 組成的字符串來表示 Bessie 的路線，其中 D 和 R 分別表示 Bessie 向下（down）或向右（right）移動。

第一個子測試用例中，Bessie 的兩條可能的路線為 DDRR 和 RRDD。

第二個子測試用例中，Bessie 的四條可能的路線為 DDRR，DRRD，RDDR 和 RRDD。

第三個子測試用例中，Bessie 的六條可能的路線為 DDRR，DRDR，DRRD，RDDR，RDRD 和 RRDD。

第四個子測試用例中，Bessie 的兩條可能的路線為 DDRR 和 RRDD。

第五和第六個子測試用例中，Bessie 不可能回到牛棚。

第七個子測試用例中，Bessie 的六條可能的路線為 DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD 和 RRDRDD。

【數據范圍】

測試點 2 滿足?K=1。

測試點 3-5 滿足?K=2。

測試點 6-10 滿足?K=3。

思路?

就是搜索，很正常的搜索，只是要注意清楚這個轉向就好了，看代碼吧

#include<bits/stdc++.h>
using namespace std;
const int N=60;
char grid[N][N];
int ans;
int n,k;
void dfs(int i,int j,int x,int dir){//t是轉向的次數，dir是現在的方向 if(i<0||j<0||i==n||j==n||x>k||grid[i][j]=='H') return;if(i==n-1&&j==n-1){ans++;return ;}if(i==0&&j==0){//最初不管向右向下都不算轉向 dfs(i+1,j,x,1);//1代表向下 dfs(i,j+1,x,0);//0代表向右 }else{if(dir==1){//向下時 dfs(i+1,j,x,1);dfs(i,j+1,x+1,0);}else{//向右時 dfs(i+1,j,x+1,1);dfs(i,j+1,x,0);} }}
int main(){int t;cin>>t;while(t--){cin>>n>>k;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>grid[i][j];}}ans=0;dfs(0,0,0,0);cout<<ans<<endl;}}

---

P8838 [傳智杯 #3 決賽] 面試

題目背景

disangan233 和 disangan333 去面試了，面試官給了一個問題，熱心的你能幫幫他們嗎？

題目描述

現在有?n?個服務器，服務器?i?最多能處理?ai??大小的數據。

接下來會有?k?條指令?bk?，指令?i?表示發送?bi??的數據，需要你分配一個空閑的服務器。

請你算出一個序列?pk??表示指令?i?的數據分配給服務器?pi?，且?pk??的字典序最小；如果無法分配，輸出 "-1"。

對于所有數據，n,k≤6，ai?,bi?≤10。

輸入格式

輸入共?3?行。

第?1?行輸入?2?個正整數?n,k。

第?2?行輸入?n?個正整數?ai?，表示服務器?i?最多能處理的數據大小。

第?3?行輸入?k?個正整數?bi?，表示指令?i。

輸出格式

輸出共?1?行?k?個正整數?p1?…pk?，或者輸出 "-1"。

輸入輸出樣例

輸入 #1復制

6 6
1 9 1 9 8 1
1 1 4 5 1 4

輸出 #1復制

1 3 2 4 6 5

說明/提示

樣例解釋

第 1 條指令分給服務器 1；
第 2 條指令分給服務器 3；
第 3 條指令分給服務器 2；
第 4 條指令分給服務器 4；
第 5 條指令分給服務器 6；
第 6 條指令分給服務器 5。

思路

利用全排列方式搜索，

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10],b[10],arr[10];
bool visited[10];
void dfs(int x){if(x==k+1){for(int i=1;i<=n;i++)cout<<arr[i]<<' '; exit(0);}for(int i=1;i<=n;i++){//利用for循環來遍歷第i個服務器，讓第x個數據扔進去，扔不進去就跳到下一個，//然后搜索，又重新遍歷服務器，讓之前沒用的服務器再次可能被用 if(a[i]-b[x]>=0&&!visited[i]){arr[x]=i,visited[i]=1;dfs(x+1);visited[i]=0;}	}return;
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=k;i++) cin>>b[i];dfs(1);cout<<-1;return 0;
}

---

P9304 「DTOI-5」3-1

題目描述

里克在視線可及的范圍內發現了一顆古老的「神樹」。

神樹是一顆樹，樹上有?n?個含有魔法裝置的位置。經過初步「考察」，有?n?1?條魔法連接，第?i(1≤i≤n?1)?條連接?ui?,vi??兩個魔法裝置，保證?ui?=vi??且?1≤ui?,vi?≤n。這兩個裝置可以相互雙向地在?1?單位時間內通行，保證僅由這?n?1?條連接，每個魔法裝置都可以相互到達。

此外，有?n?1?條特殊連接，對于每個魔法裝置?i∈[2,n]，可以瞬間傳送到第?1?個魔法裝置，花費?0?單位時間。特殊連接總共只能使用一次。

里克初始在魔法裝置?1?處。現在，給出這棵「神樹」的結構，里克想要在若干時間內研究盡可能多的魔法裝置。我們假定，研究一個魔法裝置只需要到達該裝置處，并且不需要花費額外時間。

里克想讓你盡快計算出，對所有?k∈[1,n]，如果要恰好研究?k?個不同的魔法裝置，并且隨之返回魔法裝置?1，最少應花費多少時間。

輸入格式

第一行，一個整數?n。

接下來?n?1?行，每行兩個整數?ui?,vi?。

輸出格式

共?n?行，第?i?行一個整數表示?k=i?的答案。

輸入輸出樣例

輸入 #1復制

5
1 2
1 3
2 4
2 5

輸出 #1復制

0
1
2
4
6

輸入 #2復制

見下發的 hope/hope2.in

輸出 #2復制

見下發的 hope/hope2.ans

說明/提示

【樣例解釋?1】

• k=1?時，里克只需要呆在裝置?1?處。
• k=2?時，里克的路徑可以是?1→2?1。
• k=3?時，里克的路徑可以是?1→2→4?1。
• k=4?時，里克的路徑可以是?1→2→4?1→3→1。
• k=5?時，里克的路徑可以是?1→3→1→2→5→2→4?1。

【樣例解釋?2】

這組數據滿足測試點編號?13～20?的性質。

【數據規模與約定】

測試點編號	特殊限制
1～2	n=3
3～4	n=5
5～6	n=100
7～8	n=1000
9～10	ui?=1,vi?=i+1
11～12	ui?=i,vi?=i+1
13～20	無特殊限制

對于所有數據，1≤n≤105，1≤ui?,vi?≤n。

附件下載

hope.zip790.22KB

思路?

就是把他當成樹，把節點1當成根然后開始搜索，遍歷所有節點，記錄他們的深度，并記錄最深的深度，但最后我們是要找到這題的那個公式，我們要知道回到節點1，就要走兩遍邊，然后現在多了個順義，想要最大程度利用的話，就減去你走的這個分支的最大長度

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge{int to;int next;
}graph[N*2];
int cnt,head[N],degree[N],depth[N];//degree記錄一下每個節點都連了幾個節點
//當遇到只連一個的除了根節點，那就是遇到從上往下的節點到底了 
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;degree[u]++;
}
int n,max_length;
void dfs(int x,int fa){depth[x]=depth[fa]+1;if(x!=1&&degree[x]==1){max_length=max(max_length,depth[x]);return ;//說明從上往下到達一個個分支的最下面了//然后就更新一下最深度 }for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;if(to!=fa){dfs(to,x);}}
} 
int main(){cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;add_edge(u,v);add_edge(v,u);}depth[0]=-1;//這樣就能保證深度就是邊的長度了dfs(1,0);//從節點1開始搜，節點0是他爹//k個節點就有（k-1）個邊，當沒有直接傳送，那么想要把所有節點走完再回到根節點//那么必須把所有節點走兩遍，那么邊就走兩遍 //現在多了個傳送，我們就要最大程度利用傳送，也就是當我走的最遠那個分支時候我們就傳送，這樣就能少走最多的路 //但是我們要求的是走所有數量的節點的情況，所以不是所有情況都要走哪個最深的分支 for(int i=1;i<=n;i++){cout<<(i-1)*2-min(i-1,max_length)<<endl; }}

---

P10095 [ROIR 2023] 斐波那契乘積 (Day 1)

題目背景

翻譯自?ROIR 2023 D1T2。

斐波那契數指斐波那契數列（f0?=1,f1?=1,fi?=fi?2?+fi?1?）中出現的數。

題目描述

給定一個自然數?n，求出將其表示為若干個大于?1?的斐波那契數的乘積的方案數。

輸入格式

第一行一個數?t，表示數據組數。

接下來?t?行，每行輸入一個數?n。

輸出格式

對于每組測試數據，輸出一個數表示答案。

輸入輸出樣例

輸入 #1復制

5
2
7
8
40
64

輸出 #1復制

1
0
2
2
3

說明/提示

樣例解釋：

• 2=2。
• 7?無法被表示為斐波那契乘積。
• 8=8=2×2×2。
• 40=5×8=2×2×2×5。
• 64=8×8=2×2×2×8=2×2×2×2×2×2。

本題使用捆綁測試。

子任務編號	分值	2≤n≤
1	15	100
2	17	105
3	9	n?是?2?的整數次冪
4	38	109
5	21	1018

對于所有數據，1≤t≤50，2≤n≤1018。

思路

看題目對樣例的解析，我們可以知道就是讓得到，n如果被分解成只有斐波那契數，那么能被分解的方案有多少個，，，我們可以想象成你在拼拼圖，現在有很多拼圖（這些拼圖都是斐波那契數），找到所有可能的搭配，拼出n，咱們分析一下遞歸

1，現在當前最大的是斐波那契數是arr[num]，如果這個數很大，比你的n還大，那咱就不考慮，直接減小num，然后找到小于等于n的斐波那契數，咱們有兩種選擇，選或不選這個拼圖，如果選，那必須是在這個拼圖能被n整除情況下選，剩下情況就是不選，去試試更小的斐波那契數，然后當n等于1也就是拼完了（也就是不用拼了），那就代表咱找到一個方案了，當num=1，說明就剩一個拼圖了，這個拼圖大小是1（第一個斐波那契數），這時候返回0，因為我們的n不是1，他選這個斐波那契數沒用，我們一直能整除他，但永遠拼不完圖

我用了打表，一班看見斐波那契我就喜歡打表，這個數也不多

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>arr={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903};int n;
int dfs(int n,int num){if(n==1) return 1;if(num==1) return 0;while(n<arr[num]){num--;}int ans=0;if(n%arr[num]==0){ans+=dfs(n/arr[num],num);}ans+=dfs(n,num-1);return ans;
}
signed main(){int t;cin>>t;while(t--){cin>>n;cout<<dfs(n,arr.size()-1)<<endl;}}

---

P10386 [藍橋杯 2024 省 A] 五子棋對弈

題目描述

“在五子棋的對弈中，友誼的小船說翻就翻？” 不！對小藍和小橋來說，五子棋不僅是棋盤上的較量，更是心與心之間的溝通。這兩位摯友秉承著 “友誼第一，比賽第二” 的宗旨，決定在一塊?5×5?的棋盤上，用黑白兩色的棋子來決出勝負。但他們又都不忍心讓對方失落，于是決定用一場和棋（平局）?作為彼此友誼的見證。 比賽遵循以下規則：

1. 棋盤規模：比賽在一個?5×5?的方格棋盤上進行，共有?25?個格子供下棋使用。
2. 棋子類型：兩種棋子，黑棋與白棋，代表雙方。小藍持白棋，小橋持黑棋。
3. 先手規則：白棋（小藍）具有先手優勢，即在棋盤空白時率先落子（下棋）。
4. 輪流落子：玩家們交替在棋盤上放置各自的棋子，每次僅放置一枚。
5. 勝利條件：率先在橫線、豎線或斜線上形成連續的五個同色棋子的一方獲勝。
6. 平局條件：當所有?25?個棋盤格都被下滿棋子，而未決出勝負時，游戲以平局告終。

在這一設定下，小藍和小橋想知道，有多少種不同的棋局情況（終局不同看成不同情況，終局相同而落子順序不同看成同一種情況），既確保棋盤下滿又保證比賽結果為平局。

輸入格式

這是一道結果填空題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

輸出格式

這是一道結果填空題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

輸入輸出樣例

無

思路?

這題嘛，明顯的回溯，和那個數獨，八皇后是一樣的，我們只要一行一行下，然后每下一次棋就回溯一次，猶豫這詞是兩個不同的棋所以要回溯兩次，對于之前的數獨和八皇后都是一類棋，他們只用回溯一次，然后我們再對每次下棋check一下，算一下總共有多少種方案就行了，這題我就不寫了，我看題解都挺好

---

P10490 Missile Defence System

題目描述

為了對抗附近惡意國家的威脅，R 國更新了他們的導彈防御系統。

一套防御系統的導彈攔截高度要么一直嚴格單調上升要么一直嚴格單調下降。

例如，一套系統先后攔截了高度為?3?和高度為?4?的兩發導彈，那么接下來該系統就只能攔截高度大于?4?的導彈。

給定即將襲來的一系列導彈的高度，請你求出至少需要多少套防御系統，就可以將它們全部擊落。

輸入格式

輸入包含多組測試用例。

對于每個測試用例，第一行包含整數?n，表示來襲導彈數量。

第二行包含?n?個不同的整數，表示每個導彈的高度。

當輸入測試用例?n=0?時，表示輸入終止，且該用例無需處理。

輸出格式

對于每個測試用例，輸出一行，一個整數，表示所需的防御系統數量。

顯示翻譯

題意翻譯

輸入輸出樣例

輸入 #1復制

5 
3 5 2 4 1 
0

輸出 #1復制

2

說明/提示

樣例解釋

對于樣例，需要兩套系統。一套擊落?3,4?號導彈，另一套擊落?5,2,1?號導彈。

數據規模與約定

1≤n≤50。

思路

這題我不會哈，我看題解寫的，就是構建兩個導彈攔截系統，一個up代表上升的系統，記錄上升的一串數那個最大的數，一個down代表下降的系統，記錄的是下降到一串數最小的那個數，，，，然后dfs搜索就是先一直構建嘛，當然是要判斷的，如果比如這個數比當前up攔截系統最大的這個數

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=60;
vector<int> up,down;
int arr[N];
int n,ans;
void dfs(int now){int x=up.size(),y=down.size();//兩個攔截系統有多少if(x+y>=ans) return;//如果攔截系統比已經記錄到的多直接返回就好 if(now>n) {ans=min(x+y,ans);return;}for(int i=0;i<x;i++){if(up[i]<arr[now]){int tmp=up[i];up[i]=arr[now];dfs(now+1);up[i]=tmp;break;}}//構造一個新的攔截系統 if(x==0||up[x-1]>=arr[now]){up.push_back(arr[now]);dfs(now+1);up.pop_back();}//不構造up新的的話,那就開始看看能不能扔進down系統for(int i=0;i<y;i++){if(down[i]>arr[now]){int tmp=down[i];down[i]=arr[now];dfs(now+1);down[i]=tmp;break;}} if(y==0||down[y-1]<=arr[now]){down.push_back(arr[now]);dfs(now+1);down.pop_back();}}
signed main(){while(cin>>n){if(n==0) break;for(int i=1;i<=n;i++){cin>>arr[i];}ans=0x7fffffff;up.clear();down.clear();//多測清空 dfs(1);cout<<ans<<endl; }
}

---

P10477 Subway tree systems

題目描述

一些主要城市的地鐵系統采用樹狀結構，即在任何兩個車站之間，只有一條且僅有一條地鐵線路。此外，大多數這些城市都有一個獨特的中央車站。想象一下，你是這些城市中的一名游客，你想要探索整個地鐵系統。你從中央車站出發，隨機選擇一條地鐵線路，跳上地鐵列車。每當你到達一個車站，你就會選擇一條你尚未乘坐過的地鐵線路。如果在當前車站沒有其他要探索的地鐵線路了，你就會乘坐第一次到達該車站的地鐵線路返回，直到最終你沿著所有的線路都行駛了兩次，即每個方向都行駛了一次。在那時，你回到了中央車站。之后，你所記得的探索順序只是在任何給定時間是否向中央車站更遠或更近，也就是說，你可以將你的旅程編碼為一個二進制字符串，其中 0 表示乘坐一條地鐵線路使你離中央車站更遠一站，而 1 表示使你離中央車站更近一站。

輸入格式

輸入的第一行是一個正整數?n，表示接下來要跟隨的測試方案的數量。每個測試方案包括兩行，每行包含一個長度最多為?3000?的由字符 '0' 和 '1' 組成的字符串，描述了地鐵樹系統的正確探索旅程。

輸出格式

對于每個測試方案，如果兩個字符串可以表示相同地鐵樹系統的探索旅程，則輸出 "same"；如果兩個字符串不能表示相同地鐵樹系統的探索旅程，則輸出 "different"。

翻譯來自于：ChatGPT。

顯示翻譯

題意翻譯

輸入輸出樣例

輸入 #1復制

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

輸出 #1復制

same
different

思路

這個題搞了好久，才算是明白怎么回事，就是現在給你兩棵樹，用字符串標示量，可能這兩棵樹的子樹們順序不一樣，但整體結構是一樣的，這就算是相同的樹，那我們現在就需要把他們的子樹順序搞的一樣，我們怎么辦呢，我們利用樹這個結構，他們是天生的遞歸圣體，我們通過在開頭末尾分別加0和1，代表給這個子樹加一個根形成新的樹，然后存進數組里，然后排序形成新的順序，當然最開始是先去掉0 1，然后相當于把這個子樹的根去掉，然后開始進行操作，最后加01構成新樹

字符串操作的意義

• 去掉首尾?0?和?1：剝離當前根節點?A，僅處理其子節點?B?和?C。

• 排序子樹：對子節點?B?和?C?的字符串進行排序，消除順序差異。

• 重組字符串：將排序后的子樹重新包裹在?0?和?1?中，形成新的根節點表示。

我這個是看題解，看了好久才懂的（我太笨蛋了哈哈），我之前把題解扔上去了，因為我也對題解做不出什么改變了。

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
void stl(string &s)
{if(s=="01") return;s=s.substr(1,s.size()-2);int st=0,cnt=0;vector<string>vs;vs.clear(); for(int i=0;i<s.size();++i){cnt+=(s[i]=='0'?1:-1);if(!cnt){string ss=s.substr(st,i-st+1);stl(ss);vs.push_back(ss);st=i+1;}}sort(vs.begin(),vs.end());s='0';for(int j=0;j<vs.size();++j) s+=vs[j];s+='1';return;
}
int main()
{int t;scanf("%d",&t);while(t--){cin>>s1;cin>>s2;s1='0'+s1+'1';s2='0'+s2+'1';//方便后面遞歸stl(s1);stl(s2);if(s1==s2) printf("same\n");else printf("different\n");}return 0;
}

---

P12317 [藍橋杯 2024 國 C] 樹的結點值

題目描述

給定一棵包含?n?個結點的樹，其樹根編號為?1。我們規定其第?i?個結點的值為其對應的子樹內所有與?i?奇偶性相同的結點數量。請按編號從小到大的順序輸出其每個結點的值。

輸入格式

輸入的第一行包含一個整數?n。

接下來?n?1?行描述每個結點的父結點，其中第?i?行包含一個整數?Fi+1?，表示第?i+1?個結點的父結點。

輸出格式

輸出?n?行，每行包含一個整數表示編號為?i?的結點的值。

輸入輸出樣例

輸入 #1復制

5
1
2
1
2

輸出 #1復制

3
1
1
1
1

說明/提示

評測用例規模與約定

對于?40%?的評測用例，1≤n≤5000；

對于所有評測用例，1≤n≤2×105，1≤Fi?<i。

思路

就是從根節點開始搜，然記錄每個節點下面的子樹所含有的和自己父節點的奇偶性相同的子樹數量，這么長一串可能看不懂哈，就是正常我們記錄的是一棵數下面包括自己有多少個節點，但是這里我們記錄的是下面與自己節點奇偶性相同的節點有多少個，包括自己也算上，我們用一個二維數組記錄，0 1 代表偶和奇

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct edge{int to;int next;
}graph[N*2];
int cnt,head[N];
void add_edge(int u,int v){cnt++;graph[cnt].to=v;graph[cnt].next=head[u];head[u]=cnt;
} 
int n,arr[N][2];//記錄第i個節點下面包括自己的奇數偶數節點有多少個
void dfs(int x,int fa){arr[x][x%2]=1;//for(int i=head[x];i;i=graph[i].next){int to=graph[i].to;if(to==fa) continue;dfs(to,x);arr[x][0]+=arr[to][0];arr[x][1]+=arr[to][1];}
}
int main(){cin>>n;
//讀好題，建圖別建錯for(int i=2;i<=n;i++){int v;cin>>v;add_edge(v,i);add_edge(i,v);}dfs(1,0);for(int i=1;i<=n;i++){cout<<arr[i][i%2]<<endl;}
}