国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<acronym id="l33o8"></acronym>

第十四屆藍(lán)橋杯省賽c/c++大學(xué)B組題解

2年前作者：舊林墨煙分類：Toy博客閱讀(23)違法舉報

這篇具有很好參考價值的文章主要介紹了第十四屆藍(lán)橋杯省賽c/c++大學(xué)B組題解。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

第十四屆藍(lán)橋杯省賽c/c++大學(xué)B組題解

個人答案，有錯漏感謝指正哈

試題 A: 日期統(tǒng)計

本題總分：5 分
【問題描述】
??小藍(lán)現(xiàn)在有一個長度為 100 的數(shù)組，數(shù)組中的每個元素的值都在 0 到 9 的范圍之內(nèi)。數(shù)組中的元素從左至右如下所示：
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
現(xiàn)在他想要從這個數(shù)組中尋找一些滿足以下條件的子序列：

子序列的長度為 8；
這個子序列可以按照下標(biāo)順序組成一個 yyyymmdd 格式的日期，并且要求這個日期是 2023 年中的某一天的日期，例如 20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天數(shù)，當(dāng)月份或者天數(shù)的長度只有一位時需要一個前導(dǎo)零補充。請你幫小藍(lán)計算下按上述條件一共能找到多少個不同的 2023 年的日期。對于相同的日期你只需要統(tǒng)計一次即可。

【答案提交】
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個整數(shù)，在提交答案時只填寫這個整數(shù)，填寫多余的內(nèi)容將無法得分

【解題思路】
暴力枚舉吧！2023前綴剪一下枝，不會很慢的

【代碼】

#include<bits/stdc++.h>
using namespace std;
string s;
int getday[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
set<string> se;//相同日期過濾 
void dfs(string ss,int i){
	if(ss.size()==8){
		int year=stoi(ss.substr(0,4)); 
		int month=stoi(ss.substr(4,2)); 
		int day=stoi(ss.substr(6,2)); 
		if(year==2023){
			if(month>=1&&month<=12){
				if(day>=1&&day<=getday[month]){
					se.insert(ss);
				}
			}
		}
		return;//8個字符后面就沒必要了 
	} 
	
	if(i==s.size())return;//深搜完成，退出 
	if(ss.size()==1&&ss.back()!='2')return;//年份不符合條件，直接退出
	if(ss.size()==2&&ss.back()!='0')return;//年份不符合條件，直接退出
	if(ss.size()==3&&ss.back()!='2')return;//年份不符合條件，直接退出
	if(ss.size()==4&&ss.back()!='3')return;//年份不符合條件，直接退出
	if(ss.size()==5&&stoi(ss.substr(4,1))>1)return;//月份不符合條件，直接退出 
	if(ss.size()==6&&(stoi(ss.substr(4,2))>12||stoi(ss.substr(4,2))==0))return;//月份不符合條件，直接退出 
	if(ss.size()==7&&(stoi(ss.substr(6,1))>3))return;//日不符合條件，直接退出 
	if(ss.size()==8&&(stoi(ss.substr(6,2))>31||stoi(ss.substr(6,2))==0))return;//月份不符合條件，直接退出 
	dfs(ss,i+1);//不選當(dāng)前字符 
	ss+=s[i];
	dfs(ss,i+1);//選擇當(dāng)前字符 
}

int main(){
	string s1 = "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";
	for(int c:s1){//過濾空格 
		if(c!=' '){
			s+=c;
		}
	}
	dfs("",0);
	cout<<se.size();
}

【答案】

應(yīng)該是235吧？

試題 B: 01 串的熵

本題總分：5 分
【問題描述】
??對于一個長度為 n 的 01 串 S = x1 x2 x3…xn，香農(nóng)信息熵的定義為 H(S ) = $-\sum_{1}^{n}p(x_i)log_2(p(x_i))$ ，其中 p(0), p(1) 表示在這個 01 串中 0 和 1 出現(xiàn)的占比。比如，對于 S = 100 來說，信息熵 H(S ) = $-\frac{1}{3}log_2(\frac{1}{3})-\frac{2}{3}log_2(\frac{2}{3})-\frac{2}{3}log_2(\frac{2}{3})$ =1.3083。對于一個長度為 23333333 的 01 串，如果其信息熵為 11625907.5798，且 0 出現(xiàn)次數(shù)比 1 少，那么這個 01 串中 0 出現(xiàn)了多少次？

【答案提交】
這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個整數(shù)，在提交答案時只填寫這個整數(shù)，填寫多余的內(nèi)容將無法得分。

【解題思路】
暴力枚舉，枚舉答案即可，題目看著嚇人，實則白送5分

【代碼】

#include<bits/stdc++.h>
using namespace std;
int main(){
	for(int i=0;i<=23333333;i++){
		double ans = -(double)i*i/23333333*log((double)i/23333333)/log(2)-(23333333.0-i)*(23333333-i)/23333333*log((23333333.0-i)/23333333)/log(2);
//		cout<<ans<<endl;
		if(abs(ans-11625907.5798)<1e-4){
			cout<<i<<endl;
			break;
		}
	}
}

【運行結(jié)果】

11027421

試題 C: 冶煉金屬

時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：10 分

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

【輸入格式】
第一行一個整數(shù) N，表示冶煉記錄的數(shù)目。
接下來輸入 N 行，每行兩個整數(shù) A、B，含義如題目所述。

【輸出格式】
輸出兩個整數(shù)，分別表示 V 可能的最小值和最大值，中間用空格分開。

【樣例輸入】

【樣例輸出】

20 25

【樣例說明】
??當(dāng) V = 20 時，有：? $\frac{75}{20 }$ ? = 3，? $\frac{53}{20 }$ ? = 2，? $\frac{59}{20 }$ ? = 2，可以看到符合所有冶煉
記錄。
??當(dāng) V = 25 時，有：? $\frac{75}{25}$ ? = 3，? $\frac{53}{25 }$ ? = 2，? $\frac{59}{25}$ ? = 2，可以看到符合所有冶煉
記錄。
??且再也找不到比 20 更小或者比 25 更大的符合條件的 V 值了。

【評測用例規(guī)模與約定】
對于 30% 的評測用例，1 ≤ N ≤ 10²。
對于 60% 的評測用例，1 ≤ N ≤ 10³。
對于 100% 的評測用例，1 ≤ N ≤ 10⁴，1 ≤ B ≤ A ≤ 10⁹。

【解題思路】
題目意思就是讓每種金屬都必須煉制出B個特殊金屬，多一個少一個都不行，枚舉速率的話是一個拋物線形狀。答案只有速率太低，速率合適，速率太高，只需要二分枚舉速率，特殊地取上下邊界即可，

【代碼】

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[10010];
long long b[10010];
vector<vector<long long>> ve;
int check(long long v){
	for(int i=0;i<n;i++){
		if(a[i]/v<b[i]){
			return 2;//速率太慢，需要加快，注意速率越快v的值應(yīng)該越小 
		}else if(a[i]/v>b[i]){
			return 0;//速率太快，需要減慢
		}
	}
	return 1;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
	}
	long long ans1=0,ans2=0;
	long long l=0,r=1e10;//r大一點比較穩(wěn) 
	while(l<r){
		long long m=(l+r)/2;
		if(check(m)==2){
			r=m-1;
		}else if(check(m)==1){//取左邊界 
			r=m;
		}else{
			l=m+1;
		} 
	}
	ans1=l;
	
	l=0,r=1e10;//r大一點比較穩(wěn) 
	while(l<r){
		long long m=(l+r)/2+1;
		if(check(m)==2){
			r=m-1;
		}else if(check(m)==1){//取右邊界 
			l=m;
		}else{
			l=m+1;
		} 
	}
	ans2=l;
	cout<<ans1<<' '<<ans2<<endl;
}

試題 D: 飛機降落

時間限制: 2.0s 內(nèi)存限制: 256.0MB 本題總分：10 分

【問題描述】

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

【輸入格式】
輸入包含多組數(shù)據(jù)。
第一行包含一個整數(shù) T，代表測試數(shù)據(jù)的組數(shù)。
對于每組數(shù)據(jù)，第一行包含一個整數(shù) N。
以下 N 行，每行包含三個整數(shù)：T_i，D_i 和 L_i。

【輸出格式】
對于每組數(shù)據(jù)，輸出 YES 或者 NO，代表是否可以全部安全降落。

【樣例輸入】

【樣例輸出】

YES
NO

【樣例說明】
??對于第一組數(shù)據(jù)，可以安排第 3 架飛機于 0 時刻開始降落，20 時刻完成降落。安排第 2 架飛機于 20 時刻開始降落，30 時刻完成降落。安排第 1 架飛機于 30 時刻開始降落，40 時刻完成降落。
??對于第二組數(shù)據(jù)，無論如何安排，都會有飛機不能及時降落。

【評測用例規(guī)模與約定】
對于 30% 的數(shù)據(jù)，N ≤ 2。
對于 100% 的數(shù)據(jù)，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ T_i, D_i, L_i ≤ 105。

【解題思路】
看數(shù)據(jù)，N最多為10，時間2秒鐘，盲猜暴力題，全排列所有的可能即可，復(fù)雜度O(10!*10)，不會超時吧。。。

【代碼】

#include<bits/stdc++.h>
using namespace std;
long long t[15],d[15],l[15];
int n;
int check(){
	int p[10]={0,1,2,3,4,5,6,7,8,9};
	do{
		long long time=0;
		int f=1;
		for(int i=0;i<n;i++){
			if(time>t[p[i]]+d[p[i]]){//這架飛機已經(jīng)無法起飛，退出 
				f=0;
				break;
			}else{//更新這架飛機起飛完成時間 
				time=max(time,t[p[i]])+l[p[i]];
			}
		}
		if(f==1)return 1;
	}while(next_permutation(p,p+n));
	return 0;
}
int main(){
	int tt;
	cin>>tt;
	while(tt--){
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>t[i]>>d[i]>>l[i];
		}
		if(check()){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl; 
		}
	}
}

試題 E: 接龍數(shù)列

時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：15 分

【問題描述】
??對于一個長度為 K 的整數(shù)數(shù)列：A1, A2, . . . , AK，我們稱之為接龍數(shù)列當(dāng)且僅當(dāng) Ai 的首位數(shù)字恰好等于 Ai?1 的末位數(shù)字 (2 ≤ i ≤ K)。
??例如 12, 23, 35, 56, 61, 11 是接龍數(shù)列；12, 23, 34, 56 不是接龍數(shù)列，因為 56的首位數(shù)字不等于 34 的末位數(shù)字。所有長度為 1 的整數(shù)數(shù)列都是接龍數(shù)列。
??現(xiàn)在給定一個長度為 N 的數(shù)列 A1, A2, . . . , AN，請你計算最少從中刪除多少
個數(shù)，可以使剩下的序列是接龍序列？

【輸入格式】
第一行包含一個整數(shù) N。
第二行包含 N 個整數(shù) A1, A2, . . . , AN。

【輸出格式】
一個整數(shù)代表答案。

【樣例輸入】

5
11 121 22 12 2023

【樣例輸出】

【樣例說明】
刪除 22，剩余 11, 121, 12, 2023 是接龍數(shù)列。

【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，1 ≤ N ≤ 20。
對于 50% 的數(shù)據(jù)，1 ≤ N ≤ 10000。
對于 100% 的數(shù)據(jù)，1 ≤ N ≤ 10₅，1 ≤ A_i ≤ 10₉。所有 A_i 保證不包含前導(dǎo) 0。

【解題思路】
動態(tài)規(guī)劃，記錄以某個字母結(jié)尾的最優(yōu)解即可，例如樣例，
i=0時，11，字母1結(jié)尾的接龍數(shù)列最長為1
i=1時，121 ，字母1結(jié)尾的接龍數(shù)列最長為2
i=2時，22 ，字母2結(jié)尾的接龍數(shù)列最長為1
i=3時，12，字母2結(jié)尾的接龍數(shù)列最長為3
i=4時，2023，字母3結(jié)尾的接龍數(shù)列最長為4
答案為n-最長的接龍序列，即5-4=1

【代碼】

#include<bits/stdc++.h>
using namespace std;
int main(){
	int l[10]={0};
	int n;
	cin>>n;
	int ma=0;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		l[s.back()-'0']=max(l[s.back()-'0'],l[s[0]-'0']+1);
		ma=max(ma,l[s.back()-'0']);
	}
	cout<<n-ma<<endl;
}

試題 F: 島嶼個數(shù)

時間限制: 2.0s 內(nèi)存限制: 256.0MB 本題總分：15 分

【問題描述】
??小藍(lán)得到了一副大小為 M × N 的格子地圖，可以將其視作一個只包含字符‘0’（代表海水）和 ‘1’（代表陸地）的二維數(shù)組，地圖之外可以視作全部是海水，每個島嶼由在上/下/左/右四個方向上相鄰的 ‘1’ 相連接而形成。在島嶼 A 所占據(jù)的格子中，如果可以從中選出 k 個不同的格子，使得他們的坐標(biāo)能夠組成一個這樣的排列：(x₀, y₀),(x₁, y₁), . . . ,(x_k?1, y_k?1)，其中(x_(i+1)%k, y_(i+1)%k) 是由 (x_i, y_i) 通過上/下/左/右移動一次得來的 (0 ≤ i ≤ k ? 1)，此時這 k 個格子就構(gòu)成了一個 “環(huán)”。如果另一個島嶼 B 所占據(jù)的格子全部位于這個 “環(huán)” 內(nèi)部，此時我們將島嶼 B 視作是島嶼 A 的子島嶼。若 B 是 A 的子島嶼，C 又是 B 的子島嶼，那 C 也是 A 的子島嶼。
??請問這個地圖上共有多少個島嶼？在進(jìn)行統(tǒng)計時不需要統(tǒng)計子島嶼的數(shù)目。

【輸入格式】
??第一行一個整數(shù) T，表示有 T 組測試數(shù)據(jù)。
??接下來輸入 T 組數(shù)據(jù)。對于每組數(shù)據(jù)，第一行包含兩個用空格分隔的整數(shù)
??M、N 表示地圖大??；接下來輸入 M 行，每行包含 N 個字符，字符只可能是‘0’ 或 ‘1’。

【輸出格式】
對于每組數(shù)據(jù)，輸出一行，包含一個整數(shù)表示答案。

【樣例輸入】

【樣例輸出】

1
3

【樣例說明】
對于第一組數(shù)據(jù)，包含兩個島嶼，下面用不同的數(shù)字進(jìn)行了區(qū)分：

島嶼 2 在島嶼 1 的 “環(huán)” 內(nèi)部，所以島嶼 2 是島嶼 1 的子島嶼，答案為 1。
對于第二組數(shù)據(jù)，包含三個島嶼，下面用不同的數(shù)字進(jìn)行了區(qū)分：

注意島嶼 3 并不是島嶼 1 或者島嶼 2 的子島嶼，因為島嶼 1 和島嶼 2 中均沒有“環(huán)”。

【評測用例規(guī)模與約定】
對于 30% 的評測用例，1 ≤ M, N ≤ 10。
對于 100% 的評測用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。

【解題思路】
我做得挺麻煩的，應(yīng)該有更好的解題思路哈哈
1、0可以往八個方向擴張，如果0能到的地方，那么就一定不是子島嶼。
2、1只能向上下左右四個方向擴張，并且只能擴張到為1的區(qū)域，這樣能保證第一點的正確性
3、解決記錄島嶼的問題–使用并查集，避免重復(fù)計算，也減去了大量的判斷
4、可以先在圖的外層添加一層0，這樣從(0,0)點開始bfs就可以了！

【代碼】

#include<bits/stdc++.h>
using namespace std;
int f[5010];
int g1[4][2]={0,1,1,0,-1,0,0,-1};//上下左右四個方向 
int g2[8][2]={0,1,1,0,-1,0,0,-1,1,1,1,-1,-1,-1,-1,1};//八個方向 

int find(int a){//并查集 
	if(f[a]!=a)return f[a]=find(f[a]);
	return a;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		for(int i=0;i<5010;i++){//初始化并查集 
			f[i]=i;
		}
		int n,m;
		cin>>n>>m;
		string s[55];
		for(int i=1;i<=n;i++){
			cin>>s[i];
		}
		for(int i=0;i<=m+1;i++){//外圍加一層0 
			s[0]+='0';
			s[n+1]+='0';
		}
		for(int i=1;i<=n;i++){
			s[i]+='0';
			s[i].insert(0,"0");
		}
		n+=2;
		m+=2;
		
		queue<vector<int>> q;
		q.push({0,0});
		int vis[55][55]={1};//標(biāo)記數(shù)組 
		while(!q.empty()){
			vector<int> v = q.front();
			q.pop();
			if(s[v[0]][v[1]]=='1'){//向四個方向擴張，且為1 
				for(int i=0;i<4;i++){
					int x=v[0]+g1[i][0];
					int y=v[1]+g1[i][1];
					if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='1'){
						f[find(v[0]*m+v[1])]=find(x*m+y);//連接起來 
						if(vis[x][y]==0){
							q.push({x,y});
							vis[x][y]=1;
						} 
					}
				} 
			}else{//向八個方向擴張 
				for(int i=0;i<8;i++){
					int x=v[0]+g2[i][0];
					int y=v[1]+g2[i][1];
					if(x>=0&&x<n&&y>=0&&y<m){
						if(vis[x][y]==0){
							q.push({x,y});
							vis[x][y]=1;
						} 
					}
				} 
			}
		}
		
		
		long long ans=0;
		//第二次計算答案 
		q.push({0,0});
		memset(vis,0,sizeof vis);
		vis[0][0]=1; 
		while(!q.empty()){
			vector<int> v = q.front();
			q.pop();
			if(s[v[0]][v[1]]=='1'){//向四個方向擴張，且為1 
				if(find(v[0]*m+v[1])==v[0]*m+v[1]){
					ans++;
				}
				for(int i=0;i<4;i++){
					int x=v[0]+g1[i][0];
					int y=v[1]+g1[i][1];
					if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='1'){
						if(vis[x][y]==0){
							q.push({x,y});
							vis[x][y]=1;
						} 
					}
				} 
			}else{//向八個方向擴張 
				for(int i=0;i<8;i++){
					int x=v[0]+g2[i][0];
					int y=v[1]+g2[i][1];
					if(x>=0&&x<n&&y>=0&&y<m){
						if(vis[x][y]==0){
							q.push({x,y});
							vis[x][y]=1;
						} 
					}
				} 
			}
		}
		cout<<ans<<endl;
	}
}

試題 G: 子串簡寫

時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：20 分

【問題描述】
??程序猿圈子里正在流行一種很新的簡寫方法：對于一個字符串，只保留首尾字符，將首尾字符之間的所有字符用這部分的長度代替。例如 internation-alization 簡寫成 i18n，Kubernetes （注意連字符不是字符串的一部分）簡寫成 K8s, Lanqiao 簡寫成 L5o 等。
??在本題中，我們規(guī)定長度大于等于 K 的字符串都可以采用這種簡寫方法（長度小于 K 的字符串不配使用這種簡寫）。
??給定一個字符串 S 和兩個字符 c₁ 和 c₂，請你計算 S 有多少個以 c₁ 開頭
c₂ 結(jié)尾的子串可以采用這種簡寫？

【輸入格式】
第一行包含一個整數(shù) K。
第二行包含一個字符串 S 和兩個字符 c₁ 和 c₂。

【輸出格式】
一個整數(shù)代表答案。

【樣例輸入】

4
abababdb a b

【樣例輸出】

【樣例說明】
符合條件的子串如下所示，中括號內(nèi)是該子串：

[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]

【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，2 ≤ K ≤ |S | ≤ 10000。
對于 100% 的數(shù)據(jù)，2 ≤ K ≤ |S | ≤ 5 × 10⁵。S 只包含小寫字母。c₁ 和 c₂都是小寫字母。|S | 代表字符串 S 的長度。

【解題思路】
計算貢獻(xiàn)的題目，記錄a的前綴和，當(dāng)遇到字符b時記錄答案即可

【代碼】

#include<bits/stdc++.h>
using namespace std;
int main(){
	int k;
	string s;
	string a,b;
	cin>>k>>s>>a>>b;
	long long sum=0;
	long long ans=0;
	for(int i=k-1;i<s.size();i++){
		if(s[i-(k-1)]==a[0]){
			sum++;
		}
		if(s[i]==b[0]){
			ans+=sum;
		}
	}
	cout<<ans<<endl;
}

試題 H: 整數(shù)刪除

時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：20 分

【問題描述】
??給定一個長度為 N 的整數(shù)數(shù)列：A₁, A₂, . . . , A_N。你要重復(fù)以下操作 K 次：
每次選擇數(shù)列中最小的整數(shù)（如果最小值不止一個，選擇最靠前的），將其刪除。并把與它相鄰的整數(shù)加上被刪除的數(shù)值。輸出 K 次操作后的序列。

【輸入格式】
第一行包含兩個整數(shù) N 和 K。
第二行包含 N 個整數(shù)，A₁, A₂, A₃, . . . , A_N。

【輸出格式】
輸出 N ? K 個整數(shù)，中間用一個空格隔開，代表 K 次操作后的序列。

【樣例輸入】

5 3
1 4 2 8 7

【樣例輸出】

17 7

【樣例說明】
數(shù)列變化如下，中括號里的數(shù)是當(dāng)次操作中被選擇的數(shù)：

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

【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，1 ≤ K < N ≤ 10000。
對于 100% 的數(shù)據(jù)，1 ≤ K < N ≤ 5 × 10⁵，0 ≤ A_i≤ 10⁸。

【解題思路】
用優(yōu)先級隊列動態(tài)地獲取最小的數(shù)，時間復(fù)雜度為O(N*logN)
1、用懶標(biāo)記標(biāo)記刪除的點，在隊列中獲取數(shù)據(jù)時判斷是否被標(biāo)記刪除，是則丟棄，否則就是要取的點
2、刪除當(dāng)前節(jié)點后，左右節(jié)點加上當(dāng)前節(jié)點的值，并且左節(jié)點的右節(jié)點更新為當(dāng)前節(jié)點的右節(jié)點、右節(jié)點的左節(jié)點更新為當(dāng)前節(jié)點的左節(jié)點
模擬這個過程即可

【代碼】

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<long long> v[500010];//存節(jié)點信息 
int f[500010];//標(biāo)記是否被刪除 
int main(){
	priority_queue<vector<long long>,vector<vector<long long>>,greater<vector<long long>>> q;
	cin>>n>>m;
	v[0]=v[n+1]={0,0,0};
	for(long long i=1;i<=n;i++){
		long long a;
		cin>>a;
		v[i]={a,i-1,i+1};//記錄值和前后點的位置 
		q.push({a,i});//把值和下標(biāo)放入優(yōu)先級隊列 
	}
	while(m--){
		while(!q.empty()&&(q.top()[0]!=v[q.top()[1]][0]||f[q.top()[1]]==1)){//被刪除的點或者不是最新的點直接丟掉 
			q.pop();
		}
		vector<long long> vv=q.top();
		q.pop();
		f[vv[1]]=1;
		long long l = v[vv[1]][1];//左節(jié)點 
		long long r = v[vv[1]][2];//右節(jié)點 
		v[l][0]+=vv[0]; //左節(jié)點加上當(dāng)前節(jié)點的值 
		v[l][2]=v[vv[1]][2];//左節(jié)點的右節(jié)點改為當(dāng)前節(jié)點的右節(jié)點 
		v[r][0]+=vv[0]; //右節(jié)點加上當(dāng)前節(jié)點的值 
		v[r][1]=v[vv[1]][1];//右節(jié)點的左節(jié)點改為當(dāng)前節(jié)點的左節(jié)點 
		if(l>0&&l<=n){//越界判斷 
			q.push({v[l][0],l});
		}
		if(r>0&&r<=n){
			q.push({v[r][0],r});
		}
	} 
	int ff=0;//控制輸出的空格 
	for(int i=1;i<=n;i++){//打印未刪除的節(jié)點 
		if(f[i]==0){
			if(ff==1){
				cout<<' ';
			}
			ff=1;
			cout<<v[i][0];
		}
	}
}

試題 I: 景區(qū)導(dǎo)游

時間限制: 5.0s 內(nèi)存限制: 256.0MB 本題總分：25 分

【問題描述】
??某景區(qū)一共有 N 個景點，編號 1 到 N。景點之間共有 N ? 1 條雙向的擺渡車線路相連，形成一棵樹狀結(jié)構(gòu)。在景點之間往返只能通過這些擺渡車進(jìn)行，需要花費一定的時間。
??小明是這個景區(qū)的資深導(dǎo)游，他每天都要按固定順序帶客人游覽其中 K 個景點：A₁, A₂, . . . , A_K。今天由于時間原因，小明決定跳過其中一個景點，只帶游客按順序游覽其中 K ? 1 個景點。具體來說，如果小明選擇跳過 Ai，那么他會按順序帶游客游覽 A₁, A₂, . . . , A_i?1, A_i+1, . . . , A_K, (1 ≤ i ≤ K)。
??請你對任意一個 Ai，計算如果跳過這個景點，小明需要花費多少時間在景
點之間的擺渡車上？

【輸入格式】
第一行包含 2 個整數(shù) N 和 K。
以下 N ? 1 行，每行包含 3 個整數(shù) u, v 和 t，代表景點 u 和 v 之間有擺渡車線路，花費 t 個單位時間。
最后一行包含 K 個整數(shù) A1, A2, . . . , AK 代表原定游覽線路。

【輸出格式】
輸出 K 個整數(shù)，其中第 i 個代表跳過 Ai 之后，花費在擺渡車上的時間。

【樣例輸入】

【樣例輸出】

10 7 13 14

【樣例說明】
原路線是 2 → 6 → 5 → 1。
當(dāng)跳過 2 時，路線是 6 → 5 → 1，其中 6 → 5 花費時間 3 + 2 + 2 = 7，5 → 1 花費時間 2 + 1 = 3，總時間花費 10。
當(dāng)跳過 6 時，路線是 2 → 5 → 1，其中 2 → 5 花費時間 1 + 1 + 2 = 4，5 → 1 花費時間 2 + 1 = 3，總時間花費 7。
當(dāng)跳過 5 時，路線是 2 → 6 → 1，其中 2 → 6 花費時間 1 + 1 + 2 + 3 = 7，6 → 1 花費時間 3 + 2 + 1 = 6，總時間花費 13。
當(dāng)跳過 1 時，路線時 2 → 6 → 5，其中 2 → 6 花費時間 1 + 1 + 2 + 3 = 7，6 → 5 花費時間 3 + 2 + 2 = 7，總時間花費 14。

【評測用例規(guī)模與約定】
對于 20% 的數(shù)據(jù)，2 ≤ K ≤ N ≤ 10²。
對于 40% 的數(shù)據(jù)，2 ≤ K ≤ N ≤ 10⁴。
對于 100% 的數(shù)據(jù)，2 ≤ K ≤ N ≤ 10⁵，1 ≤ u, v, A_i ≤ N，1 ≤ t ≤ 10⁵。保證A_i 兩兩不同。

【解題思路】
使用最近公共祖先算法即可解答該題
1、因為題目給出的是無向樹，我們?nèi)我饽靡粋€作為樹的根節(jié)點都可以
2、假如要求a、b兩點的距離，假設(shè)根節(jié)點為root，a、b最近公共祖先是c，那么a點和b點之間的距離等于a點到root的距離加上b點到root的距離減去c點到root的距離的兩倍
第十四屆藍(lán)橋杯省賽c/c++大學(xué)B組題解
3、如上面樣例畫出來的圖，求點6到點5的距離 = 點6到點1的距離 + 點5到點1的距離 - 2*點3到點1的距離

4、那么我們就要先預(yù)處理出所有點到根節(jié)點的距離！

5、接下來求出最小公共祖先即可AC了，求最小公共祖先算法有多種，倍增、樹鏈剖分、tanjar離線都可以做到，這到題5秒鐘，都不會超時的吧，下面代碼是用tanjar離線做的

【代碼】

#include<bits/stdc++.h>
using namespace std;
vector<vector<long long>> v[100010];
long long d[100010];
void dfs(long long i,long long p,long long dd){//i：當(dāng)前節(jié)點，p：父節(jié)點，dd目前的距離 
	d[i]=dd;
	for(vector<long long> c:v[i]){
		if(c[0]!=p){
			dfs(c[0],i,dd+c[1]);
		}
	}
}

long long f[100010];
long long find(long long a){//tanjar離線算法需要使用并查集 
	if(f[a]!=a)return f[a]=find(f[a]);
	return a;
}

int vis[100010];//標(biāo)記數(shù)組 
vector<long long> vvv[100010];//離線的點 
map<pair<long long,long long>,long long> ma;
void dfs2(long long i,long long p){//i：當(dāng)前節(jié)點，p：父節(jié)點

	for(long long c:vvv[i]){//記錄最近公共祖先 
		if(vis[c]==1){
			ma[{i,c}]=find(c);
			ma[{c,i}]=find(c);
		}
	}

	for(vector<long long> c:v[i]){
		if(c[0]!=p){
			dfs2(c[0],i);
		}
	}
	f[find(i)]=find(p);
	vis[i]=1;
} 

int main(){
	for(int i=0;i<100010;i++){//初始化并查集 
		f[i]=i;
	}
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++){
		long long x,y,val;
		cin>>x>>y>>val;
		v[x].push_back({y,val});
		v[y].push_back({x,val});
	}
	vector<long long> vv;//存原本的路徑 
	for(int i=0;i<m;i++){
		long long a;
		cin>>a;
		vv.push_back(a);
	} 
	for(int i=1;i<m;i++){
		vvv[vv[i]].push_back(vv[i-1]);
		vvv[vv[i-1]].push_back(vv[i]);
		if(i>=2){
			vvv[vv[i]].push_back(vv[i-2]);
			vvv[vv[i-2]].push_back(vv[i]);
		}
	} 
	
	dfs(1,0,0);//求出所有點到根節(jié)點的距離
	
	dfs2(1,0);//tanjar離線求最小公共祖先 
	
	long long ans=0;//總路線花費 
	for(int i=1;i<vv.size();i++){
		ans+=d[vv[i]]+d[vv[i-1]]-2*d[ma[{vv[i-1],vv[i]}]];
	}
	
	cout<<ans-(d[vv[0]]+d[vv[1]]-2*d[ma[{vv[0],vv[1]}]])<<' ';//特別處理第一個點 
	for(int i=1;i<vv.size()-1;i++){//去掉中間點 
		cout<<(ans-(d[vv[i]]+d[vv[i-1]]-2*d[ma[{vv[i-1],vv[i]}]])-(d[vv[i]]+d[vv[i+1]]-2*d[ma[{vv[i+1],vv[i]}]]))+(d[vv[i-1]]+d[vv[i+1]]-2*d[ma[{vv[i+1],vv[i-1]}]])<<' ';
	}
	cout<<ans-(d[vv.back()]+d[vv[vv.size()-2]]-2*d[ma[{vv.back(),vv[vv.size()-2]}]])<<endl;//特別處理最后一個點 
	
}

試題 J: 砍樹

時間限制: 1.0s 內(nèi)存限制: 256.0MB 本題總分：25 分

【問題描述】
給定一棵由 n 個結(jié)點組成的樹以及 m 個不重復(fù)的無序數(shù)對 (a₁, b₁), (a₂, b₂),. . . , (a_m, b_m)，其中 ai 互不相同，b_i 互不相同，a_i , b_j(1 ≤ i, j ≤ m)。小明想知道是否能夠選擇一條樹上的邊砍斷，使得對于每個 (ai, b_i) 滿足 a_i和 b_i 不連通，如果可以則輸出應(yīng)該斷掉的邊的編號（編號按輸入順序從 1 開始），否則輸出 -1。

【輸入格式】
輸入共 n + m 行，第一行為兩個正整數(shù) n，m。
后面 n ? 1 行，每行兩個正整數(shù) xi，yi 表示第 i 條邊的兩個端點。
后面 m 行，每行兩個正整數(shù) a_i，b_i。

【輸出格式】
一行一個整數(shù)，表示答案，如有多個答案，輸出編號最大的一個。

【樣例輸入】

【樣例輸出】

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

【評測用例規(guī)模與約定】
對于 30% 的數(shù)據(jù)，保證 1 < n ≤ 1000。
對于 100% 的數(shù)據(jù)，保證 1 < n ≤ 10⁵，1 ≤ m ≤ 2。

最后一題不會嘿嘿嘿文章來源地址http://www.zghlxwxcb.cn/news/detail-411052.html

到了這里，關(guān)于第十四屆藍(lán)橋杯省賽c/c++大學(xué)B組題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

第十四屆藍(lán)橋杯大賽軟件組省賽 Python大學(xué)A組個人暴力題解
4.23 update: 省一咯 Powered by: NEFU AB-IN 博主個人的暴力題解，基本很少是正解，求輕噴題意思路模擬即可，本身想用Python自帶的datetime庫，結(jié)果發(fā)現(xiàn)年不能開那么大，就直接手寫了代碼題意思路 DFS爆搜即可代碼題意思路直接沒思路，一看到數(shù)據(jù)范圍瞬間慫了，腦子里想的
2023年04月09日
瀏覽(25)
2023第十四屆藍(lán)橋杯 C/C++大學(xué)生A組省賽滿分題解
以下代碼，目前均可通過民間OJ數(shù)據(jù)（dotcpp New Online Judge），兩個OJ題目互補，能構(gòu)成全集，可以到對應(yīng)鏈接下搜題提交（感謝OJ對題目的支持）如果發(fā)現(xiàn)任何問題，包含但不限于算法思路出錯、OJ數(shù)據(jù)弱算法實際超時、存在沒考慮到的邊界情況等，請及時聯(lián)系作者 ? ? 洛谷
2023年04月27日
瀏覽(28)
第十四屆藍(lán)橋杯省賽PythonA/C組------翻轉(zhuǎn)
小藍(lán)用黑白棋的n個棋子排成了一行，他在腦海里想象出了一個長度為n的01串T，他發(fā)現(xiàn)如果把黑棋當(dāng)做1，白棋當(dāng)做0，這一行棋子也是一個長度為n 的01串S。小藍(lán)決定，如果在S中發(fā)現(xiàn)一個棋子和它兩邊的棋子都不一樣，就可以將其翻轉(zhuǎn)變成另一個顏色。也就是說，如果S中存在
2024年01月22日
瀏覽(29)
第十四屆藍(lán)橋杯省賽C++ A組淺析
（僅個人看法，對錯未知，可以當(dāng)做口胡QAQ）如有錯誤請大佬們指出，有更好做法歡迎留言！暴力判不多說了看到很多搜的，提供一個dp做法 d p [ i ] [ j ] 表示前 i 道題，答對 j 道的方案數(shù) dp[i][j]表示前i道題，答對j道的方案數(shù) d p [ i ] [ j ] 表示前 i 道題，答對 j 道的方案數(shù)
2023年04月13日
瀏覽(24)
2023年第十四屆藍(lán)橋杯省賽Java C組題解
只做出來(ACDFGH)，挑幾個出來，答案不一定正確，但自己測試通過了求1~20230408的和這里就直接套等差數(shù)列的求和公式，答案:204634714038436 ? 【問題描述】 ????????有一個長度為n的數(shù)組(n是10的倍數(shù))，每個數(shù) Ai 都是區(qū)間[0,9]中的整數(shù)，小明發(fā)現(xiàn)數(shù)組里每種數(shù)出現(xiàn)的次數(shù)不太
2023年04月26日
瀏覽(32)
第十四屆藍(lán)橋杯省賽 Python B 組 D 題——管道（AC）
有一根長度為 len text{len} len 的橫向的管道，該管道按照單位長度分為 len text{len} len 段，每一段的中央有一個可開關(guān)的閥門和一個檢測水流的傳感器。一開始管道是空的，位于 L i L_i L i ? 的閥門會在 S i S_i S i ? 時刻打開，并不斷讓水流入管道。對于位于 L i L_i L i ? 的閥
2024年02月07日
瀏覽(24)
第十四屆藍(lán)橋杯省賽 C/C++ A 組 H 題——異或和之和（AC）
給定一個數(shù)組 A i A_i A i ? ，分別求其每個子段的異或和，并求出它們的和?；蛘哒f，對于每組滿足 1 ≤ L ≤ R ≤ n 1 leq L leq R leq n 1 ≤ L ≤ R ≤ n 的 L , R L, R L , R ，求出數(shù)組中第 L L L 至第 R R R 個元素的異或和。然后輸出每組 L , R L, R L , R 得到的結(jié)果加起來的值。輸入的第
2024年02月13日
瀏覽(88)
第十四屆藍(lán)橋杯省賽JavaB組試題E【蝸牛】Dijkstra堆優(yōu)化 or 線性DP？
??????????????????????????????????????????????????????????????????????????????????????????????????????? ????????????????????????????????????????????? 第十四屆藍(lán)橋杯省賽JavaB組試題E【蝸牛】Dijkstra堆
2024年02月01日
瀏覽(22)
2023第十四屆藍(lán)橋杯C/C++B組省賽題解
題目描述【問題描述】小藍(lán)現(xiàn)在有一個長度為100 的數(shù)組，數(shù)組中的每個元素的值都在0 到9 的范圍之內(nèi)。數(shù)組中的元素從左至右如下所示：現(xiàn)在他想要從這個數(shù)組中尋找一些滿足以下條件的子序列：子序列的長度為8；這個子序列可以按照下標(biāo)順序組成一個yyyymmdd 格式的日
2024年02月04日
瀏覽(18)
藍(lán)橋杯第十四屆省賽完整題解 C/C++ B組
沒有測評，不知道對不對，僅僅過樣例而已本題總分：5 分【問題描述】小藍(lán)現(xiàn)在有一個長度為 100 的數(shù)組，數(shù)組中的每個元素的值都在 0 到 9 的范圍之內(nèi)。數(shù)組中的元素從左至右如下所示： 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
2023年04月13日
瀏覽(95)

<code id="bo3u8"><abbr id="bo3u8"></abbr></code>

<b id="bo3u8"><abbr id="bo3u8"></abbr></b>