第14屆藍橋杯C++B組省賽題解(A-J)(更新完畢)-有解無憂

A. 日期統計
- 題目內容
- 思路
- 代碼
- 答案
B.01 串的熵
- 題目內容
- 思路
- 代碼
- 答案
C.冶煉金屬
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
D.飛機降落
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
E.接龍數列
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
F.島嶼數量
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
G.子串簡寫
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
H.整數洗掉
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
I.景區導游
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼
J.砍樹
- 題目內容
- 輸入格式
- 輸出格式
- 輸入樣例
- 輸出樣例
- 思路
- 代碼

A. 日期統計

題目內容

小藍現在有一個長度為 $100$ 的陣列，陣列中的每個元素的值都在 $0$ 到 $9$ 的范圍之內，
陣列中的元素從左至右如下所示：

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

現在他想要從這個陣列中尋找一些滿足以下條件的子序列：

子序列的長度為 $8$；
這個子序列可以按照下標順序組成一個 $yyyymmdd$ 格式的日期，并且
要求這個日期是 $2023$ 年中的某一天的日期，例如 $20230902，20231223$，
$yyyy$ 表示年份，$mm$ 表示月份，$dd$ 表示天數，當月份或者天數的長度只有一位時需要一個前導零補充，
請你幫小藍計算下按上述條件一共能找到多少個不同的 $2023$ 年的日期，
對于相同的日期你只需要統計一次即可，
本題的結果為一個整數，在提交答案時只輸出這個整數，輸出多余的內容將無法得分，

思路

八重回圈列舉日期+set去重即可
$Tips:$ 前4重特判2023,否則程式會跑的很慢

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n=100;
int num[N];
set<string>s;

bool check(string all)
{
	int m=stoi(all.substr(0,2));
	int d=stoi(all.substr(2,2));
	
	int mon[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
	if(m>=1&&m<=12)
	{
		if(d>=1&&d<=mon[m])
			return true;
	}
	
	return false;
}
int main()
{
	for(int i=0;i<n;i++)cin>>num[i];



	for(int a=0;a<n;a++)
	{
	
		if(num[a]!=2)continue;
		for(int b=a+1;b<n;b++)
		{
			if(num[b]!=0)continue;
			for(int c=b+1;c<n;c++)
			{
				if(num[c]!=2)continue;
				for(int d=c+1;d<n;d++)
				{	
					if(num[d]!=3)continue;
					for(int e=d+1;e<n;e++)
					{
						for(int f=e+1;f<n;f++)
						{
							for(int g=f+1;g<n;g++)
							{
								for(int h=g+1;h<n;h++)
								{
									string n1=to_string(num[e]);
									string n2=to_string(num[f]);
									string n3=to_string(num[g]);
									string n4=to_string(num[h]);
									string all=n1+n2+n3+n4;
									if(check(all))s.insert(all);
									
									
								}
							}
						}
					}
				}
			}
		}
	}	
	
	
	cout<<s.size()<<endl;
	
	return 0;
}

答案

B.01 串的熵

題目內容

對于一個長度 $ n $ 的 $01$ 串 $S = x_1x_2x_3...x_n$，
香農資訊熵的定義為：$H(S)=-\sum_{i=1}^{n}p(x_i)log_2(p(x_i))$ ,其中 $p(0)$, $p(1)$ 表示在這個 $01$ 串中 $0$ 和 $1$ 出現的占比，
比如，對于 $S = 100$ 來說，資訊熵 $H(S) = - \frac{1}{3}log_2(\frac{1}{3}) - \frac{2}{3} log_2(\frac{2}{3}) = 1.3083$，
對于一個長度為 $23333333$ 的 $01$ 串，如果其資訊熵為 $11625907.5798$ ，且 $0$ 出現次數比 $1$ 少，那么這個 $01$ 串中 $0$ 出現了多少次？
本題的結果為一個整數，在提交答案時只輸出這個整數，輸出多余的內容將無法得分，

思路

按題意模擬即可，由題意可得 $H(S)$的值只與 $01$ 出現的次數有關，因為 $0$ 出現次數比 $1$ 少，所以可以從 $\lfloor \frac{23333333}{2} \rfloor = 11666666$ 開始往下列舉0的個數，同時計算 $p(0)，p(1)$ 的占比，帶入公式驗證是否相等，注意設定誤差范圍去判斷浮點數是否相等

代碼

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-4;
//#define double long double
int len;

int main()
{
	int len=23333333;
	for(int i=len/2;i>=1;i--)
	{
		double px0=1.0*i/len,px1=1.0*(len-i)/len;
		double H=-(i*px0*log2(px0)+(len-i)*px1*log2(px1));
		if(fabs(H-11625907.5798)<=eps)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	
	return 0;
}

答案

11027421

C.冶煉金屬

題目內容

小藍有一個神奇的爐子用于將普通金屬 $O$ 冶煉成為一種特殊金屬 $X$ ，這個爐子有一個稱作轉換率的屬性 $V$ ，$V$ 是一個正整數，這意味著消耗 $V$ 個普通金屬 $O$ 恰好可以冶煉出一個特殊金屬 $X$，當普通金屬 $O$ 的數目不足 $V$ 時，無法繼續冶煉，現在給出了 $N$ 條冶煉記錄，每條記錄中包含兩個整數 $A$ 和 $B$，這表示本次投入了 $A$ 個普通金屬$O$，最終冶煉出了 $B$ 個特殊金屬 $X$，每條記錄都是獨立的，這意味著上一次沒消耗完的普通金屬 $O$ 不會累加到下一次的冶煉當中，根據這 $N$ 條冶煉記錄，請你推測出轉換率 $V$ 的最小值和最大值分別可能是多少，題目保證評測資料不存在無解的情況，

輸入格式

第一行一個整數 $N$，表示冶煉記錄的數目，
接下來輸入 $N$ 行，每行兩個整數 $A、B$ ，含義如題目所述，
對于 $30\%$ 的評測用例，$1 ≤ N ≤ 100$
對于 $60\%$ 的評測用例，$1 ≤ N ≤ 1000$
對于 $100\%$ 的評測用例，$1 ≤ N ≤ 10000，1 ≤ B ≤ A ≤ 1,000,000,000$

輸出格式

輸出兩個整數，分別表示 $V$ 可能的最小值和最大值，中間用空格分開，

輸入樣例

輸出樣例

20 25

思路

求最小值和最大值問題，可以利用二分答案進行判斷，

求最小值
- 假設最終答案為 $S$
  - 因為 $S$ 的最優性，若要求答案 $<S$，對于每組金屬 $A$ 至少有一個不能冶煉出 $B$ 個特殊金屬
  - 若答案可以 $>S$，則一定存在一個屬性 $V$ ，使得每組金屬 $A$ 都能冶煉出對應的 $B$ 個特殊金屬，最優解就處于可行性的分界點上
求最大值與上面同理

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;

bool check_min(int x)
{
	//如果某一組存在a[i]/x的值比實際B大，說明V可以繼續增加
	for(int i=0;i<n;i++)
		if(a[i]/x>b[i])return false;
	
	return true;
}

bool check_max(int x)
{
	//如果某一組存在a[i]/x的值比實際B小，說明V可以繼續減小
	for(int i=0;i<n;i++)
		if(a[i]/x<b[i])return false;
	
	return true;
}
int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];
	
	
	int l=0,r=1e9;
	
	//求最小值
	while(l<r)
	{
		int mid=l+r>>1;
		if(check_min(mid))r=mid;
		else l=mid+1;
	}
	
	cout<<l<<' ';
	
	
	l=0,r=1e9;
	
	//求最大值
	while(l<r)
	{
		int mid=l+r+1>>1;
		//
		if(check_max(mid))l=mid;
		else r=mid-1;
	}
	
	cout<<l<<endl;
	
	return 0;
}

D.飛機降落

題目內容

$N$ 架飛機準備降落到某個只有一條跑道的機場，其中第 $i$ 架飛機在 $T_i$ 時刻到達機場上空，到達時它的剩余油料還可以繼續盤旋 $D_i$ 個單位時間，即它最早可以于 $T_i$ 時刻開始降落，最晚可以于 $T_i + D_i$ 時刻開始降落，降落程序需要 $L_i$ 個單位時間，一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落，請你判斷 $N$ 架飛機是否可以全部安全降落，

輸入格式

輸入包含多組資料，
第一行包含一個整數 $T$ ，代表測驗資料的組數，
對于每組資料，第一行包含一個整數 $N$ ，
以下 $N$ 行，每行包含三個整數：$T_i，D_i$ 和 $L_i$
對于 $30\%$ 的資料，$N ≤ 2$
對于 $100\%$ 的資料，$1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ T_i,D_i,L_i ≤ 100,000$

輸出格式

對于每組資料，輸出 $YES$ 或者 $NO$，代表是否可以全部安全降落，

輸入樣例

輸出樣例

YES
NO

對于第一組資料:
安排第 $3$ 架飛機于 $0$ 時刻開始降落，$20$ 時刻完成降落，
安排第 $2$ 架飛機于 $20$ 時刻開始降落，$30$ 時刻完成降落，
安排第 $1$ 架飛機于 $30$ 時刻開始降落，$40$ 時刻完成降落，
對于第二組資料，無論如何安排，都會有飛機不能及時降落，

思路

$N$最大只有$10$,最多10組測驗組數，可以暴搜列舉所有方案

優化：若搜索到一種合法方案，剪枝一路回傳即可，不需要繼續搜索

代碼

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=12;
PII a[N];
int d[N];
bool st[N];
int n;

//代表列舉到第u層，當前飛機的降落結束時間為now
bool dfs(int u,int now)
{
	
	if(u>=n)
	{
		for(int i=0;i<n;i++)
			if(!st[i])return false;
		
		return true;
	}
	
	for(int i=0;i<n;i++)
	{
		if(!st[i])
		{
			st[i]=true;
			//如果當前飛機的最早降落時間小于等于now，并且最晚降落時間大于等于now，
			//則從當前時刻開始降落
			if(a[i].x<=now&&a[i].y>=now)
			{
				//降落結束時間now更新為now+d[i]，繼續列舉下一架飛機
				if(dfs(u+1,now+d[i]))return true;
			}
			//如果當前飛機的最早降落時間大于等于now
			else if(a[i].x>=now)
			{
				//降落結束時間now更新為a[i].x+d[i]，繼續列舉下一架飛機
				if(dfs(u+1,a[i].x+d[i]))return true;
			}
			st[i]=false;
		}
	}
	
	return false;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		
		for(int i=0;i<n;i++)
		{
			cin>>a[i].x>>a[i].y>>d[i];
			a[i].y+=a[i].x;
		}

		memset(st,0,sizeof st);
		puts(dfs(0,0)?"YES":"NO");
	}
	
	return 0;
}

E.接龍數列

題目內容

對于一個長度為 $K$ 的整數數列：$A_1, A_2, ... , A_K$，我們稱之為接龍數列：當且僅當 $A_i$ 的首位數字恰好等于 $A_{i?1}$ 的末位數字$(2 ≤ i ≤ K)$，例如：$12, 23, 35, 56, 61, 11$ 是接龍數列；$12, 23, 34, 56$ 不是接龍數列，因為 $56$ 的首位數字不等于 $34$ 的末位數字，所有長度為 1 的整數數列都是接龍數列，現在給定一個長度為 $N$ 的數列 $A_1, A_2, ... , A_N$，請你計算最少從中洗掉多少個數，可以使剩下的序列是接龍序列？

輸入格式

第一行包含一個整數 $N$ ，
第二行包含 $N$ 個整數 $A_1, A_2, ... , A_N$，
對于 $20\%$ 的資料，$1 ≤ N ≤ 20$，
對于 $50\%$ 的資料，$1 ≤ N ≤ 10000$，
對于 $100\%$ 的資料，$1 ≤ N ≤ 10^5，1 ≤ A_i ≤ 10^9$，
所有 $A_i$ 保證不包含前導 $0$，

輸出格式

一個整數代表答案，

輸入樣例

5
11 121 22 12 2023

輸出樣例

洗掉 $22$，剩余 $ 11, 121, 12, 2023 $ 是接龍數列，

思路

線性 $dp$，定義狀態 $f[i]$ , 代表以 $i$ 結尾的最長序列的長度
因此，所求的最少洗掉數的個數 = $n - $最長接龍序列的長度

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=12;
int f[N];
int main()
{
	int n;
	cin>>n;
	
	int maxv=0;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		int a=s[0]-'0',b=s.back()-'0';
		f[b]=max(f[b],f[a]+1);//接到前面以a結尾的數后面；或者替換掉前面一個以b結尾的數，保持不變
		maxv=max(maxv,f[b]);//更新最大值
	}
	
	cout<<n-maxv<<endl;
	
	return 0;
}

F.島嶼數量

題目內容

小藍得到了一副大小為 $M × N$ 的格子地圖，可以將其視作一個只包含字符$0$（代表海水）和 $1$（代表陸地）的二維陣列，地圖之外可以視作全部是海水，每個島嶼由在上/下/左/右四個方向上相鄰的 $1$ 相連接而形成，在島嶼 A 所占據的格子中，如果可以從中選出 $k$ 個不同的格子，使得他們的坐標能夠組成一個這樣的排列：$(x_0, y_0),(x_1, y_1), . . . ,(x_{k?1}, y_{k?1})$，其中 $($ $x_{(i+1)\%k}, y_{(i+1)\%k}$ $)$ 是由 $(x_i, y_i)$ 通過上/下/左/右移動一次得來的 $(0 ≤ i ≤ k ? 1)$，此時這 $k$ 個格子就構成了一個 “環”，如果另一個島嶼 $B$ 所占據的格子全部位于這個 “環” 內部，此時我們將島嶼 B 視作是島嶼 $A$ 的子島嶼，若 $B$ 是 $A$ 的子島嶼，$C$ 又是 $B$ 的子島嶼，那 $C$ 也是 $A$ 的子島嶼，請問這個地圖上共有多少個島嶼？在進行統計時不需要統計子島嶼的數目，

輸入格式

第一行一個整數 $T$，表示有 $T$ 組測驗資料，
接下來輸入 $T$ 組資料，對于每組資料，第一行包含兩個用空格分隔的整數 $M、N$ 表示地圖大小；接下來輸入 $M$ 行，每行包含 $N$ 個字符，字符只可能是 $0$ 或 $1$

輸出格式

對于每組資料，輸出一行，包含一個整數表示答案，

輸入樣例

輸出樣例

1
3

對于第一組資料，包含兩個島嶼，下面用不同的數字進行了區分：

島嶼 $2$ 在島嶼 $1$ 的 “環” 內部，所以島嶼 $2$ 是島嶼 $1$ 的子島嶼，答案為 $1$，
對于第二組資料，包含三個島嶼，下面用不同的數字進行了區分：

注意島嶼 $3$ 并不是島嶼 $1$ 或者島嶼 $2$ 的子島嶼，因為島嶼 $1$ 和島嶼 $2$ 中均沒有“環”，
對于 $30\%$ 的評測用例，$1 ≤ M, N ≤ 10$ ，
對于 $100\%$ 的評測用例，$1 ≤ T ≤ 10，1 ≤ M, N ≤ 50$ ，

思路

兩次寬搜，從 $(1,1)$ 處存圖

第一次寬搜，先從 $(0,0)$ ，即海水處開始向八個方向搜索，將能搜索到的 $0$ 標記成 $\#$，將每塊島嶼分隔開
第二次寬搜，遍歷 $g[][]$ 陣列，當遇到 $1$ 的時候，將 $1$ 包圍的整塊區域標記成 $\#$，同時要統計的島嶼個數加一

代碼

#include<bits/stdc++.h>
#define x first 
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=55;
char g[N][N];
int n,m;
int dx[]={-1,0,1,0,-1,-1,1,1};
int dy[]={0,1,0,-1,-1,1,1,-1};

//分隔島嶼
void bfs1(int x,int y)
{
	queue<PII>q;
	
	q.push({0,0});
	g[0][0]='#';
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		for(int i=0;i<8;i++)
		{
			int a=t.x+dx[i],b=t.y+dy[i];
			if(a<0||a>n+1||b<0||b>m+1||g[a][b]=='1'||g[a][b]=='#')continue;
			g[a][b]='#';
			q.push({a,b});
		}
	}
}

//將整塊島嶼標記
void bfs2(int x,int y)
{
	queue<PII>q;
	
	q.push({x,y});
	g[x][y]='#';
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		for(int i=0;i<4;i++)
		{
			int a=t.x+dx[i],b=t.y+dy[i];
			if(a<1||a>n||b<1||b>m||g[a][b]=='#')continue;
			g[a][b]='#';
			q.push({a,b});
		}
	}
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		memset(g,'0',sizeof g);
		for(int i=1;i<=n;i++)cin>>g[i]+1;
		
		
		int x,y;
		bfs1(x,y);
			
		int cnt=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(g[i][j]=='1')
					bfs2(i,j),cnt++;//統計個數
			
		cout<<cnt<<endl;
	}
	
	return 0;
}

G.子串簡寫

題目內容

程式猿圈子里正在流行一種很新的簡寫方法：
對于一個字串，只保留首尾字符，將首尾字符之間的所有字符用這部分的長度代替，
例如 $internationalization$ 簡寫成 $i18n，Kubernetes$ 簡寫成 $K8s, Lanqiao$ 簡寫成 $L5o$ 等，
在本題中，我們規定長度大于等于 $K$ 的字串都可以采用這種簡寫方法，
長度小于 $K$ 的字串不允許使用這種簡寫，
給定一個字串 $S$ 和兩個字符 $c_1$ 和 $c_2$，
請你計算 $S$ 有多少個以 $c_1$ 開頭 $c_2$ 結尾的子串可以采用這種簡寫？

輸入格式

第一行包含一個整數 $K$，
第二行包含一個字串 $S$ 和兩個字符 $c_1$ 和 $c_2$，
對于 $20\%$ 的資料，$2 ≤ K ≤ |S| ≤ 10000$，
對于 $100\%$ 的資料，$2 ≤ K ≤ |S| ≤ 5 × 10^5$，
$S$ 只包含小寫字母，$c_1$ 和 $c_2$ 都是小寫字母，
$|S|$ 代表字串 $S$ 的長度，

輸出格式

一個整數代表答案

輸入樣例

4
abababdb a b

輸出樣例

符合條件的子串如下所示，中括號內是該子串：
$[abab]abdb$
$[ababab]db$
$[abababdb]$
$ab[abab]db$
$ab[ababdb]$
$abab[abdb]$

思路

先求出 $c_1$ 的前綴和陣列 $s[i]$ ，統計$c_1$在前綴中出現的次數，接著遍歷字串，每遇到一次 $c_2$ ，就加上 $s[i-k+1]$ ，即加上以 $c_1$ 開頭 $c_2$ 結尾且長度大于等于 $K$ 的字串，最后得到答案，
$Tips:$注意最后答案可能很大，要開 $longlong$

代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
char str[N];
ll cnt[N];
char st,ed;
int k;

int main()
{
	cin>>k;
	
	cin>>str+1>>st>>ed;
	
	int n=strlen(str+1);
	//統計c1的前綴和
	for(int i=1;i<=n;i++)
		if(str[i]==st)cnt[i]=cnt[i-1]+1;
		else cnt[i]=cnt[i-1];
	
	
	//累加求個數
	ll res=0;
	for(int i=k;i<=n;i++)
		if(str[i]==ed)res+=cnt[i-k+1];
	
	
	cout<<res<<endl;
	
	return 0;
}

H.整數洗掉

題目內容

給定一個長度為 $N$ 的整數數列：$A_1, A_2, . . . , A_N$ ，你要重復以下操作 $K$ 次：
每次選擇數列中最小的整數（如果最小值不止一個，選擇最靠前的），將其洗掉，并把與它相鄰的整數加上被洗掉的數值，輸出 $K$ 次操作后的序列，

輸入格式

第一行包含兩個整數 $N$ 和 $K$，
第二行包含 $N$ 個整數，$A_1, A_2, A_3, . . . , A_N$，

輸出格式

輸出 $N ? K$ 個整數，中間用一個空格隔開，代表 $K$ 次操作后的序列，

輸入樣例

5 3
1 4 2 8 7

輸出樣例

17 7

數列變化如下，中括號里的數是當次操作中被選擇的數：

[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7

對于 $20\%$ 的資料，$1 ≤ K < N ≤ 10000$，
對于 $100\%$ 的資料，$1 ≤ K < N ≤ 5 × 10^5，0 ≤ A_i ≤ 10^8$，

思路

題目關鍵是洗掉數列最小值，并且動態維護最小值，若取出最小元素的值比原來有變化，要重新放入優先佇列中判斷；否則就將其洗掉

洗掉操作考慮使用雙鏈表，進行 $O(1)$ 洗掉
最小值利用優先佇列去維護

代碼

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e5+10;
typedef long long ll;
typedef pair<ll,int>PII;
ll e[N],l[N],r[N];

priority_queue<PII,vector<PII>,greater<PII>>q;

int n,k;

//雙鏈表洗掉
void dele(int k)
{
	l[r[k]]=l[k];
	r[l[k]]=r[k];
	e[l[k]]+=e[k];
	e[r[k]]+=e[k];
	
}

int main()
{
	cin>>n>>k;
	
	//雙鏈表的頭尾
	r[0]=1,l[n+1]=n;
	
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		e[i]=x,l[i]=i-1,r[i]=i+1;
		q.push({e[i],i});//優先佇列，小根堆，儲存值和編號
	}
	
	while(k--)
	{
		auto t=q.top();
		q.pop();
		
		//取出最小元素，如果值有變化，重新放入優先佇列中；否則將其洗掉
		if(t.x!=e[t.y])q.push({e[t.y],t.y}),k++;
		else dele(t.y);	
	}
	
	for(int i=r[0];i!=n+1;i=r[i])
		cout<<e[i]<<' ';
	
	
	return 0;
}

I.景區導游

題目內容

某景區一共有 $N$ 個景點，編號 $1$ 到 $N$，景點之間共有 $N ? 1$ 條雙向的擺渡車線路相連，形成一棵樹狀結構，在景點之間往返只能通過這些擺渡車進行，需要花費一定的時間，
小明是這個景區的資深導游，他每天都要按固定順序帶客人游覽其中 $K$ 個景點：$A_1, A_2, . . . , A_K$ ，今天由于時間原因，小明決定跳過其中一個景點，只帶游客按順序游覽其中 $K ? 1$ 個景點，具體來說，如果小明選擇跳過 $A_i$，那么他會按順序帶游客游覽 $ A_1, A_2, . . . , A_{i?1}, A_{i+1}, . . . , A_K, (1 ≤ i ≤ K) $，
請你對任意一個 $A_i$，計算如果跳過這個景點，小明需要花費多少時間在景點之間的擺渡車上？

輸入格式

第一行包含 $2$ 個整數 $N$ 和 $K$，
以下 $N ? 1$ 行，每行包含 $3$ 個整數 $u, v$ 和 $t$，代表景點 $u$ 和 $v$ 之間有擺渡車線路，花費 $t$ 個單位時間，
最后一行包含 $K$ 個整數 $A_1, A_2, . . . , A_K$ 代表原定游覽線路，

輸出格式

輸出 $K$ 個整數，其中第 $i$ 個代表跳過 $A_i$ 之后，花費在擺渡車上的時間，

輸入樣例

輸出樣例

10 7 13 14

原路線是 $2 → 6 → 5 → 1$，
當跳過 $2$ 時，路線是 $6 → 5 → 1$，其中 $6 → 5$ 花費時間 $3 + 2 + 2 = 7，5 → 1$ 花費時間 $2 + 1 = 3$，總時間花費 $10$，
當跳過 $6$ 時，路線是 $2 → 5 → 1$，其中 $2 → 5$ 花費時間 $1 + 1 + 2 = 4，5 → 1$ 花費時間 $2 + 1 = 3$，總時間花費 $7$，
當跳過 $5$ 時，路線是 $2 → 6 → 1$，其中 $2 → 6$ 花費時間 $1 + 1 + 2 + 3 = 7，6 → 1$ 花費時間 $3 + 2 + 1 = 6$，總時間花費 $13$，
當跳過 $1 $時，路線時 $2 → 6 → 5$，其中 $2 → 6$ 花費時間 $1 + 1 + 2 + 3 = 7，6 → 5$ 花費時間 $3 + 2 + 2 = 7$，總時間花費 $14$，

對于 $20\%$ 的資料，$2 ≤ K ≤ N ≤ 10^2$，
對于 $40\%$ 的資料，$2 ≤ K ≤ N ≤ 10^4$，
對于 $100\%$ 的資料，$2 ≤ K ≤ N ≤ 10^5，1 ≤ u, v, A_i ≤ N，1 ≤ t ≤ 10^5$，保證 $A_i$ 兩兩不同，

思路

$LCA$板子題，題目中是一棵樹形圖，求用時即為求樹上任意兩點間的距離，可利用$LCA$快速求出兩點之間的距離，求樹上兩個點距離的時候，可以預處理出每個點到根節點的距離，
兩點間最短距離公式: $x$ 到 $y$ 的距離 $= d[x]+d[y] - 2*d[lca(x,y)]$ ，本題可以先計算不跳過景點時的總用時，之后分類討論

洗掉第 $1$ 個結點時，減去 $1 \sim 2$ 之間的用時即可
洗掉第 $k$ 個結點時，減去 $k-1 \sim k$ 之間的用時
其他情況減去 $i-1 \sim i,i\sim i+1$ 之間的用時,并且加上 $i-1 \sim i+1$ 之間的用時
時間復雜度：預處理 $O(nlogn)$ 查詢：$O(logn)$

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N*2;
typedef long long ll;
int h[N],e[M],ne[M],w[M],idx;
int f[N][20];
int depth[N];
ll d[N];
int A[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

//計算所有結點到根節點1的距離
void bfs()
{
    queue<int>q;
    depth[1]=1;
    q.push(1);
    
    while(q.size()){
        int t=q.front();
        q.pop();
        
        
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(depth[j])continue;
            q.push(j);
            
            if(depth[j])continue;
            depth[j]=depth[t]+1;
            d[j]=d[t]+w[i];
            f[j][0]=t;
            for(int k=1;k<=19;k++)
                f[j][k]=f[f[j][k-1]][k-1];
            
        }
    }
    
}


//倍增法求lca
int lca(int a,int b)
{
    if(depth[a]<depth[b])swap(a,b);
    
    for(int i=19;i>=0;i--)
        if(depth[f[a][i]]>=depth[b])
            a=f[a][i];
    
    
    if(a==b)return a;
    for(int i=19;i>=0;i--)
        if(f[a][i]!=f[b][i])
            a=f[a][i],b=f[b][i];
    
    
    return f[a][0];
}

int main()
{ 	
	
	memset(h,-1,sizeof h);
	int n,k;
   
    cin>>n>>k;
    
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    
    bfs();
    
    
    for(int i=1;i<=k;i++)
    	cin>>A[i];
    

    //求不洗掉結點前的總用時
    ll res=0;
    for(int i=2;i<=k;i++)
    {
    	int p=lca(A[i],A[i-1]);
		res+=d[A[i]]+d[A[i-1]]-2*d[p];
	}
	
	
    for(int i=1;i<=k;i++)
    {
    	ll dist;

		if(i==1)//洗掉第一個結點時，減去1~2之間的用時即可
		{
    		int p=lca(A[1],A[2]);
			dist=d[A[1]]+d[A[2]]-2*d[p];
			cout<<res-dist<<' ';
				
		}
		else if(i==k)//洗掉第k個結點時，減去k-1~k之間的用時
		{
			int p=lca(A[k],A[k-1]);
			dist=d[A[k]]+d[A[k-1]]-2*d[p];
			cout<<res-dist<<' ';
			
		}
		else{//其他情況減去i-1~i,i~i+1之間的用時,并且加上i-1~i+1之間的用時
			
			int p1=lca(A[i-1],A[i]);
			int p2=lca(A[i],A[i+1]);
			int p3=lca(A[i-1],A[i+1]);
			dist=d[A[i-1]]+d[A[i]]-2*d[p1]+d[A[i]]+d[A[i+1]]-2*d[p2];
			
			cout<<res-dist+d[A[i-1]]+d[A[i+1]]-2*d[p3]<<' ';
			
		}
		
	}
    
    
    return 0;
    
}

J.砍樹

題目內容

題目描述
給定一棵由 $n$ 個結點組成的樹以及 $m$ 個不重復的無序數對 $(a_1, b_1), (a_2, b_2), ... , (a_m, b_m) $，其中 $a_i$ 互不相同，$b_i$ 互不相同，$a_i ≠ b_j(1 ≤ i, j ≤ m)$，
小明想知道是否能夠選擇一條樹上的邊砍斷，使得對于每個 $(a_i, b_i)$ 滿足 $a_i$ 和 $b_i$ 不連通，
如果可以則輸出應該斷掉的邊的編號（編號按輸入順序從 $1$ 開始），否則輸出 $-1$ ，

輸入格式

輸入共 $n + m$ 行，第一行為兩個正整數 $n，m$，
后面 $n ? 1$ 行，每行兩個正整數 $x_i，y_i$ 表示第 $i$ 條邊的兩個端點，
后面 $m$ 行，每行兩個正整數 $a_i，b_i$ ，
對于 $30\%$ 的資料，保證 $1 < n ≤ 1000$，
對于 $100\%$ 的資料，保證 $1 < n ≤ 100000，1 ≤ m ≤ n / 2$ ，

輸出格式

一行一個整數，表示答案，如有多個答案，輸出編號最大的一個，

輸入樣例

輸出樣例

斷開第 2 條邊后形成兩個連通塊：{3, 4}，{1, 2, 5, 6}，滿足 3 和 6 不連通，4 和 5 不連通，
斷開第 4 條邊后形成兩個連通塊：{1, 2, 3, 4}，{5, 6}，同樣滿足 3 和 6 不連通，4 和 5 不連通，
4 編號更大，因此答案為 4，

思路

$LCA + $樹上差分模板題，若砍掉某條邊讓這兩點不連通，那么這條邊一定是從 $x$ 到 $y$ 路徑上的一點，我們可以利用樹上差分，讓 $diff[x]+1,diff[y]+1,diff[lca(x,y)]-2$ ，最后做一遍 $dfs$ 求和,讓從 $x$ 到 $y$ 路徑的邊權值都加1，只需要從編號最大的倒序遍歷，若存在一條邊的值為 $m$，則該邊即為所求答案，若不存在，則輸出 $-1$

代碼

#include<bits/stdc++.h>
#define x first
#define y second;
using namespace std;
const int N=1e5+10,M=N*2;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],idx;
int depth[N];//記錄深度
int f[N][20];
int diff[N];//差分陣列
PII edge[N];//記錄每條邊的編號
int n,m;	

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

void dfs(int u,int fa)
{
	depth[u]=depth[fa]+1;
	
	f[u][0]=fa;
	
	for(int i=1;i<=19;i++)
		f[u][i]=f[f[u][i-1]][i-1];
		
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j!=fa)
		{
			dfs(j,u);
		}
	}
	
}

//倍增法求lca
int lca(int a,int b)
{
	if(depth[a]<depth[b])swap(a,b);
	
	for(int i=19;i>=0;i--)
		if(depth[f[a][i]]>=depth[b])
			a=f[a][i];
			
			
	
	if(a==b)return a;
	
	for(int i=19;i>=0;i--)
		if(f[a][i]!=f[b][i])
			a=f[a][i],b=f[b][i];
			
	return f[a][0];
}

//利用dfs對樹上的差分陣列求和
void dfs1(int u,int fa)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];	
		if(j!=fa)
		{
			dfs1(j,u);
			diff[u]+=diff[j];
		}
	}
}

int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		edge[i]={a,b};
		add(a,b),add(b,a);
		
	}
	
	dfs(1,0);
	
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		int p=lca(a,b);
		
		diff[a]++,diff[b]++;
		diff[p]-=2;
	}
	  
	dfs1(1,0);
	
	
	int res=-1;
	for(int i=n-1;i>=1;i--)
	{
		int a=edge[i].x,b=edge[i].y;
		if(depth[a]<depth[b])swap(a,b);//邊的權值保存在深度大的節點上
		if(diff[a]==m)
		{
			res=i;
			break;
		}
		
	}
	cout<<res<<endl;
	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551108.html

標籤：其他

上一篇：李航統計學習概述

下一篇：返回列表