第十三屆藍(lán)橋杯C++組

題目 2693:

藍(lán)橋杯2022年第十三屆決賽真題-卡牌

題目描述

這天，小明在整理他的卡牌。

他一共有 n 種卡牌，第 i 種卡牌上印有正整數(shù)數(shù) i(i ∈ [1, n])，且第 i 種卡牌 現(xiàn)有 ai 張。

而如果有 n 張卡牌，其中每種卡牌各一張，那么這 n 張卡牌可以被稱為一 套牌。小明為了湊出盡可能多套牌，拿出了 m 張空白牌，他可以在上面寫上數(shù) i，將其當(dāng)做第 i 種牌來(lái)湊出套牌。然而小明覺(jué)得手寫的牌不太美觀，決定第 i 種牌最多手寫 bi 張。

請(qǐng)問(wèn)小明最多能湊出多少套牌？

輸入格式

輸入共 3 行，第一行為兩個(gè)正整數(shù) n, m。

第二行為 n 個(gè)正整數(shù) a1, a2, …, an。

第三行為 n 個(gè)正整數(shù) b1, b2, …, bn。

輸出格式

一行，一個(gè)整數(shù)表示答案。

樣例輸入

4 5
1 2 3 4
5 5 5 5

樣例輸出

3

提示

這 5 張空白牌中，拿 2 張寫 1，拿 1 張寫 2，這樣每種牌的牌數(shù)就變?yōu)榱?3, 3, 3, 4，可以湊出 3 套牌，剩下 2 張空白牌不能再幫助小明湊出一套。

對(duì)于 30% 的數(shù)據(jù)，保證 n ≤ 2000 ；

對(duì)于 100% 的數(shù)據(jù)，保證 n ≤ 2 × 10^5 ; ai , bi ≤ 2n; m ≤ n2 。

聽(tīng)典的一個(gè)題，直接二分就行了

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
ll a[N],b[N]; 
ll n,m;
bool check(ll mid){
	ll sum=0;
	for(int i=1;i<=n;i++){
		if(a[i]<mid)
		if(mid-a[i]<=b[i])
		sum+=mid-a[i];
		else
		return false;
		if(sum>m)
		return false;
	}
	return true;
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int j=1;j<=n;j++)
	cin>>b[j];
	ll l=0,r=N*N;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid))
		l=mid+1;
		else
		r=mid;
	}
	cout<<r-1<<'\n';
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

題目 2694:

藍(lán)橋杯2022年第十三屆決賽真題-最大數(shù)字

題目描述

給定一個(gè)正整數(shù) N。你可以對(duì) N 的任意一位數(shù)字執(zhí)行任意次以下 2 種操作：

1. 將該位數(shù)字加 1。如果該位數(shù)字已經(jīng)是 9，加 1 之后變成 0。

2. 將該位數(shù)字減 1。如果該位數(shù)字已經(jīng)是 0，減 1 之后變成 9。

你現(xiàn)在總共可以執(zhí)行 1 號(hào)操作不超過(guò) A 次，2 號(hào)操作不超過(guò) B 次。

請(qǐng)問(wèn)你最大可以將 N 變成多少？

輸入格式

第一行包含 3 個(gè)整數(shù)：N, A, B。

輸出格式

一個(gè)整數(shù)代表答案。

樣例輸入

123 1 2

樣例輸出

933

提示

對(duì)百位數(shù)字執(zhí)行 2 次 2 號(hào)操作，對(duì)十位數(shù)字執(zhí)行 1 次 1 號(hào)操作。

對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 100; 0 ≤ A, B ≤ 10

對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 10^17; 0 ≤ A, B ≤ 100

考慮數(shù)據(jù)范圍，復(fù)雜度只和位數(shù)有關(guān)，首先貪心，盡量讓前面的數(shù)變大，當(dāng)然變大可以減法或者加法兩種操作，因此復(fù)雜度大概在2^17左右，需要注意的地方就是如果減法剩余次數(shù)不能使得數(shù)字變大的話，就不需要進(jìn)行減法操作。

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
ll ans=0;
void dfs(string s,int pos,int a,int b){
	if(pos==s.size()||a==0&&b==0){
		ll sum=0;
		for(int i=0;i<s.size();i++)
		sum=sum*10+s[i]-'0';
		ans=max(ans,sum);
		return ;
	}
	int d1='9'-s[pos],d2=s[pos]-'0'+1;
	if(a>0){
		string s1=s;
		s1[pos]+=min(a,d1);
		dfs(s1,pos+1,a-min(a,d1),b);
	}
	if(b>=d2){
		string s1=s;
		s1[pos]='9';
		dfs(s1,pos+1,a,b-d2);
	}
	dfs(s,pos+1,a,b);
}
void solve()
{
	string s;
	int a,b;
	cin>>s>>a>>b;
	dfs(s,0,a,b);
	cout<<ans<<'\n';
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

題目 2695:

藍(lán)橋杯2022年第十三屆決賽真題-出差

題目描述

A 國(guó)有 N 個(gè)城市，編號(hào)為 1 . . . N。小明是編號(hào)為 1 的城市中一家公司的員工，今天突然接到了上級(jí)通知需要去編號(hào)為 N 的城市出差。

由于疫情原因，很多直達(dá)的交通方式暫時(shí)關(guān)閉，小明無(wú)法乘坐飛機(jī)直接從城市 1 到達(dá)城市 N，需要通過(guò)其他城市進(jìn)行陸路交通中轉(zhuǎn)。小明通過(guò)交通信息網(wǎng)，查詢到了 M 條城市之間仍然還開(kāi)通的路線信息以及每一條路線需要花費(fèi)的時(shí)間。

同樣由于疫情原因，小明到達(dá)一個(gè)城市后需要隔離觀察一段時(shí)間才能離開(kāi)該城市前往其他城市。通過(guò)網(wǎng)絡(luò)，小明也查詢到了各個(gè)城市的隔離信息。（由于小明之前在城市 1，因此可以直接離開(kāi)城市 1，不需要隔離）

由于上級(jí)要求，小明希望能夠盡快趕到城市 N，因此他求助于你，希望你能幫他規(guī)劃一條路線，能夠在最短時(shí)間內(nèi)到達(dá)城市 N。

輸入格式

第 1 行：兩個(gè)正整數(shù) N, M, N 表示 A 國(guó)的城市數(shù)量，M 表示未關(guān)閉的路線數(shù)量

第 2 行：N 個(gè)正整數(shù)，第 i 個(gè)整數(shù) Ci 表示到達(dá)編號(hào)為 i 的城市后需要隔離的時(shí)間

第 3 . . . M + 2 行：每行 3 個(gè)正整數(shù)，u, v, c，表示有一條城市 u 到城市 v 的雙向路線仍然開(kāi)通著，通過(guò)該路線的時(shí)間為 c

輸出格式

第 1 行：1 個(gè)正整數(shù)，表示小明從城市 1 出發(fā)到達(dá)城市 N 的最短時(shí)間（到達(dá)城市 N，不需要計(jì)算城市 N 的隔離時(shí)間）

樣例輸入

4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5

樣例輸出

13

提示

路線 1：1 -> 2 -> 4，時(shí)間為 4+7(隔離)+3=14

路線 2：1 -> 3 -> 4，時(shí)間為 5+3(隔離)+5=13

對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000, 1 ≤ Ci ≤ 200, 1 ≤ u, v ≤ N, 1 ≤ c ≤ 1000

在以某個(gè)點(diǎn)為起點(diǎn)的邊上加上延遲然后跑一遍最短路就可以了,注意cpp的堆是大根堆，又一次忘記開(kāi)了，要是實(shí)際比賽這直接jiji

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 1e3 + 10;
const ll mod = 1e9 + 7;
vector<int>g[N],w[N];
int c[N],d[N];
bool vis[N];
int dij(int s,int end){
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	q.push({0,s});
	while(!q.empty()){
		int t=q.top().first,u=q.top().second;
		q.pop();
		if(vis[u])continue;
		d[u]=t;
		vis[u]=true;
		if(u==end)
		return t;
		for(int i=0;i<w[u].size();i++){
			if(!vis[g[u][i]])
			q.push({w[u][i]+d[u],g[u][i]});
		}
	}
	return d[end];
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>c[i];
	int u,v,x;
	for(int i=1;i<=m;i++){
	cin>>u>>v>>x;
	g[u].push_back(v);
	g[v].push_back(u);
	w[u].push_back(x);
	w[v].push_back(x);
	}
	for(int i=2;i<=n;i++)
	for(int j=0;j<g[i].size();j++)
	w[i][j]+=c[i];
	cout<<dij(1,n)<<'\n';
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

題目 2696:

藍(lán)橋杯2022年第十三屆決賽真題-費(fèi)用報(bào)銷

題目描述

小明在出差結(jié)束后返回了公司所在的城市，在填寫差旅報(bào)銷申請(qǐng)時(shí)，粗心的小明發(fā)現(xiàn)自己弄丟了出差過(guò)程中的票據(jù)。

為了彌補(bǔ)小明的損失，公司同意小明用別的票據(jù)進(jìn)行報(bào)銷，但是公司財(cái)務(wù)要求小明提交的票據(jù)中任意兩張的日期差不小于 K 天，且總金額不得超過(guò)實(shí)際差旅費(fèi)用 M。

比如財(cái)務(wù)要求 K = 7 時(shí)，若小明提交了一張 1 月 8 日的票據(jù)，小明就不能提交 1 月 2 日至 1 月 14 日之間的其他票據(jù)，1 月 1 日及之前和 1 月 15 日及之后的票據(jù)則可以提交。

公司的同事們一起給小明湊了 N 張票據(jù)，小明現(xiàn)在想要請(qǐng)你幫他整理一下，從中選取出符合財(cái)務(wù)要求的票據(jù)，并使總金額盡可能接近 M。

需要注意，由于這些票據(jù)都是同一年的，因此 12 月底的票據(jù)不會(huì)影響到 1 月初票據(jù)的提交。這一年不是閏年。

輸入格式

第 1 行：3 個(gè)整數(shù)，N, M, K

第 2 . . . N + 1 行：每行 3 個(gè)整數(shù) mi , di , vi，第 i + 1 行表示第 i 張票據(jù)時(shí)間的月份 mi 和日期 di，vi 表示該票據(jù)的面值

輸出格式

第 1 行：1 個(gè)整數(shù)，表示小明能夠湊出的最大報(bào)銷金額

樣例輸入

4 16 3
1 1 1
1 3 2
1 4 4
1 6 8

樣例輸出

10

提示

選擇 1 月 3 日和 1 月 6 日的票據(jù)

對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 50, 1 ≤ mi ≤ 12, 1 ≤ di ≤ 31, 1 ≤ vi ≤ 400

日期保證合法。

動(dòng)態(tài)規(guī)劃，dp[i] [j]表示選前i種票據(jù)且總票據(jù)金額不超過(guò)j的可獲得的最大金額，因?yàn)檫€需要保證選取第i種票據(jù)時(shí)在它前面k天以內(nèi)的票據(jù)不能存在，所以還要保證轉(zhuǎn)移時(shí)的i1票據(jù)所在的日期要滿足要求，這個(gè)地方二分一下就可以了

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 1e3 + 10;
const ll mod = 1e9 + 7;
struct node{
	int day;
	int money;
	bool operator<(const node&a){
		return day<a.day;
	}
}p[N];
int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dp[N][5*N];//選前i種且總金額不超過(guò)j的最大金額 
void solve()
{
	for(int i=2;i<=12;i++)
	d[i]+=d[i-1];
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		b+=d[a-1];
		p[i]={b,c};
	}
	sort(p+1,p+1+n);
	int ans=0;
	for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		if(j<p[i].money){
		dp[i][j]=dp[i-1][j]; 
		continue;
	}
		int c=p[i].day-k;
		int l=1,r=i+1;
		while(l<r){
			int mid=l+r>>1;
			if(p[mid].day<=c)
			l=mid+1;
			else
			r=mid;
		}
		r--;
		dp[i][j]=max(dp[i-1][j],dp[r][j-p[i].money]+p[i].money);
	}
	ans=max(ans,dp[i][m]);
}
cout<<ans<<'\n';
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

題目 2697:

藍(lán)橋杯2022年第十三屆決賽真題-故障

題目描述

在軟件或系統(tǒng)開(kāi)發(fā)中，我們會(huì)遇到各種各樣的故障。為了從故障現(xiàn)象反推故障原因，工程師們會(huì)總結(jié)一種叫做相關(guān)性矩陣的二維表格，來(lái)表示故障原因與故障現(xiàn)象之間的關(guān)系。比如：

其中每行表示一種故障原因，每一列表示一種故障現(xiàn)象。該矩陣表示故障原因 A 可能產(chǎn)生故障現(xiàn)象 2、3、4，故障原因 B 可能產(chǎn)生故障現(xiàn)象 1、3。

在實(shí)際開(kāi)發(fā)過(guò)程中，如果出現(xiàn)了故障原因，工程師就可以根據(jù)故障現(xiàn)象，去計(jì)算每種故障原因產(chǎn)生的概率，并按照概率大小對(duì)故障原因進(jìn)行排查，以達(dá)到快速定位故障原因的目的。

現(xiàn)在，我們假設(shè)系統(tǒng)開(kāi)發(fā)中同一時(shí)間只會(huì)出現(xiàn)一種故障原因，并且故障原因引起各故障現(xiàn)象是獨(dú)立事件。舉個(gè)例子來(lái)說(shuō)：

假設(shè)系統(tǒng)現(xiàn)在發(fā)生了故障原因 A，有 1/3 的概率出現(xiàn)故障現(xiàn)象 2，有 1/4 的概率出現(xiàn)故障現(xiàn)象 3，有 1/2 的概率出現(xiàn)故障現(xiàn)象 4。由于 3 種現(xiàn)象是獨(dú)立發(fā)生的，因此有1/(234)的概率同時(shí)出現(xiàn)故障 2、3、4。

約定若相關(guān)性矩陣中沒(méi)有 ‘x’ 記號(hào)，則表示該故障原因一定不會(huì)產(chǎn)生某故障現(xiàn)象，比如故障原因 A，一定不會(huì)產(chǎn)生故障現(xiàn)象 1。

根據(jù)歷史經(jīng)驗(yàn)數(shù)據(jù)，我們統(tǒng)計(jì)得到了每一種故障原因出現(xiàn)的概率以及每一 種故障原因?qū)?yīng)的故障現(xiàn)象產(chǎn)生概率。

現(xiàn)在已知系統(tǒng)出現(xiàn)的故障現(xiàn)象，求問(wèn)各個(gè)故障原因發(fā)生的概率。

輸入格式

第 1 行：2 個(gè)正整數(shù) N, M，N 表示故障原因的個(gè)數(shù)（編號(hào) 1 . . . N），M 表示故障現(xiàn)象的個(gè)數(shù)（編號(hào) 1 . . . M）.

第 2 行：N 個(gè)整數(shù)，第 i 個(gè)數(shù)表示故障原因 i 產(chǎn)生的概率 Pi .

第 3 . . . N + 2 行：每行 M 個(gè)整數(shù)，第 i + 2 行第 j 個(gè)整數(shù) Pij 表示故障原因 i 出現(xiàn)故障現(xiàn)象 j 的概率（百分比）.

第 N + 3 行：1 個(gè)正整數(shù) K，表示目前出現(xiàn)的故障現(xiàn)象數(shù)量。

第 N + 4 行：K 個(gè)正整數(shù)，依次為當(dāng)前出現(xiàn)的故障現(xiàn)象編號(hào)，不會(huì)重復(fù)。

輸出格式

第 1 . . . N 行：按概率從高到低輸出每種故障原因及其可能的概率，若出現(xiàn)概率相同則優(yōu)先輸出編號(hào)小的故障原因。第 1 個(gè)數(shù)為故障原因編號(hào)，第 2 個(gè)數(shù)為故障概率（百分比），保留 2 位小數(shù)。

樣例輸入

3 5
30 20 50
0 50 33 25 0
30 0 35 0 0
0 0 0 25 60
1
3

樣例輸出

2 56.89
1 43.11
3 0.00

提示

對(duì)于所有測(cè)試用例，1 ≤ N ≤ 40, 1 ≤ M ≤ 20, 0 ≤ Pi ≤ 100, ∑ (Pi) = 100, 0 ≤ Pij ≤ 100.

概率學(xué)的太爛了，就會(huì)一點(diǎn)點(diǎn)簡(jiǎn)單數(shù)論和組合數(shù)學(xué)，貝葉斯公式不會(huì)，貼一份別人的題解
用100減去未出現(xiàn)的現(xiàn)象的對(duì)應(yīng)故障的概率。
令各個(gè)現(xiàn)象為Ri, 故障為A,B,C…
則P(R1R2R3..Rm|A) = P(R1|A) * P(R2|A) … * P(Rm|A)
再帶入貝葉斯公示就好了。
注意開(kāi)long doublｅ，而且注意浮點(diǎn)數(shù)比較時(shí)的精度問(wèn)題。

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include<iostream>
using namespace std;
const double esp = 1e-12;
int n, m, k, P[50][31];
struct node {
    long double p;
    int i;
    inline bool operator<(const node &nd) const 
    {
        return (abs(p - nd.p) < esp) ? i < nd.i : p > nd.p;
    }
} ans[50];
int main() 
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d", &P[i][0]);
    for (int i = 0; i < n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &P[i][j]), P[i][j] = 100 - P[i][j];
    scanf("%d", &k);
    for (int g = 0, j; g < k; ++g) 
    {
        scanf("%d", &j);
        for (int i = 0; i < n; ++i)
            P[i][j] = 100 - P[i][j];
    }
    long double sum = 0;
    for (int i = 0; i < n; ++i) 
    {
        ans[i].p = P[i][0] / 100.0;
        for (int j = 1; j <= m; ++j)
            ans[i].p *= P[i][j] / 100.0;
        ans[i].i = i + 1;
        sum += ans[i].p;
    }
    sort(ans, ans + n);
    for (int i = 0; i < n; ++i)
    {
        long double t = (abs(sum) < esp) ? 0.0 : 100 * ans[i].p / sum;
        printf("%d %.2LF\n", ans[i].i, t);
    }
       return 0;
}

題目 2698:

藍(lán)橋杯2022年第十三屆決賽真題-機(jī)房

題目描述

這天，小明在機(jī)房學(xué)習(xí)。

他發(fā)現(xiàn)機(jī)房里一共有 n 臺(tái)電腦，編號(hào)為 1 到 n，電腦和電腦之間有網(wǎng)線連接，一共有 n ? 1 根網(wǎng)線將 n 臺(tái)電腦連接起來(lái)使得任意兩臺(tái)電腦都直接或者間接地相連。

小明發(fā)現(xiàn)每臺(tái)電腦轉(zhuǎn)發(fā)、發(fā)送或者接受信息需要的時(shí)間取決于這臺(tái)電腦和多少臺(tái)電腦直接相連，而信息在網(wǎng)線中的傳播時(shí)間可以忽略。比如如果某臺(tái)電腦用網(wǎng)線直接連接了另外 d 臺(tái)電腦，那么任何經(jīng)過(guò)這臺(tái)電腦的信息都會(huì)延遲 d 單位時(shí)間 (發(fā)送方和接收方也會(huì)產(chǎn)生這樣的延遲，當(dāng)然如果發(fā)送方和接收方都是同一臺(tái)電腦就只會(huì)產(chǎn)生一次延遲)。

小明一共產(chǎn)生了 m 個(gè)疑問(wèn)：如果電腦 ui 向電腦 vi 發(fā)送信息，那么信息從 ui 傳到 vi 的最短時(shí)間是多少？

輸入格式

輸入共 n + m 行，第一行為兩個(gè)正整數(shù) n, m。

后面 n ? 1 行，每行兩個(gè)正整數(shù) x, y 表示編號(hào)為 x 和 y 的兩臺(tái)電腦用網(wǎng)線直接相連。

后面 m 行，每行兩個(gè)正整數(shù) ui , vi 表示小明的第 i 個(gè)疑問(wèn)。

輸出格式

輸出共 m 行，第 i 行一個(gè)正整數(shù)表示小明第 i 個(gè)疑問(wèn)的答案。

樣例輸入

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

樣例輸出

5
6
1

提示

這四臺(tái)電腦各自的延遲分別為 2, 2, 1, 1。

對(duì)于第一個(gè)詢問(wèn)，從 2 到 3 需要經(jīng)過(guò) 2, 1, 3，所以時(shí)間和為 2 + 2 + 1 = 5。

對(duì)于第二個(gè)詢問(wèn)，從 3 到 4 需要經(jīng)過(guò) 3, 1, 2, 4，所以時(shí)間和為 1+2+2+1 = 6。

對(duì)于第三個(gè)詢問(wèn)，從 3 到 3 只會(huì)產(chǎn)生一次延遲，所以時(shí)間為 1。

對(duì)于 30% 的數(shù)據(jù)，保證 n, m ≤ 1000；

對(duì)于 100% 的數(shù)據(jù)，保證 n, m ≤ 100000 。

思路很簡(jiǎn)單，先建圖后建樹(shù)，然后跑lca，求lca的過(guò)程中順便把延遲之和求出來(lái)，注意要加上終點(diǎn)的延遲

這題wa了幾次，st預(yù)處理的時(shí)候i，j不分wa了，還是熟練度不太高

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
const ll mod = 1e9 + 7;
int fa[N] = { 0,1 }, depth[N];
pair<int, int>st[N][15];

vector<int>g[N];
void init(int f, int root) {
	depth[root] = depth[f] + 1;
	fa[root] = f;
	st[root][0] = { g[root].size(),f };
	for (int i = 0; i < g[root].size(); i++) {
		if (g[root][i] != f)
			init(root, g[root][i]);
	}
}
int lca(int u, int v) {
	if (u == v)
		return g[u].size();
	int ans = 0;
	for (int i = 14; i >= 0; i--) {
		if (st[u][i].second != st[v][i].second) {
			ans += st[u][i].first + st[v][i].first, u = st[u][i].second, v = st[v][i].second;
		}
	}
	ans += st[u][0].first + st[v][0].first + g[st[u][0].second].size();
	return ans;
}
void solve()
{
	int n, m;
	cin >> n >> m;
	int u, v;
	for (int i = 1; i < n; i++)
		cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
	init(0, 1);
	for (int i = 1; i <= 14; i++)
		for (int j = 1; j <= n; j++)
			st[j][i] = { st[j][i - 1].first + st[st[j ][i-1].second][i - 1].first,st[st[j][i - 1].second][i - 1].second };
	while (m--) {
		cin >> u >> v;
		int a = u, b = v;
		if (depth[u] < depth[v])
			swap(u, v);
		int x = depth[u] - depth[v], ans = 0;
		for (int i = 0; i <= 14 && x; i++) {
			if (x & 1) {
				ans += st[u][i].first;
				u = st[u][i].second;
			}
			x >>= 1;
		}
		ans += lca(u, v);
		cout << ans << '\n';
	}
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

題目 2699:

藍(lán)橋杯2022年第十三屆決賽真題-齒輪

題目描述

這天，小明在組裝齒輪。

他一共有 n 個(gè)齒輪，第 i 個(gè)齒輪的半徑為 ri，他需要把這 n 個(gè)齒輪按一定順序從左到右組裝起來(lái)，這樣最左邊的齒輪轉(zhuǎn)起來(lái)之后，可以傳遞到最右邊的齒輪，并且這些齒輪能夠起到提升或者降低轉(zhuǎn)速 (角速度) 的作用。

小明看著這些齒輪，突然有 Q 個(gè)疑問(wèn)：能否按一定順序組裝這些齒輪使得最右邊的齒輪的轉(zhuǎn)速是最左邊的齒輪的 qi 倍？

輸入格式

輸入共 Q + 2 行，第一行為兩個(gè)正整數(shù) n, Q，表示齒輪數(shù)量和詢問(wèn)數(shù)量。

第二行為 n 個(gè)正整數(shù) r1,r2, …,rn，表示每個(gè)齒輪的半徑。

后面 Q 行，每行一個(gè)正整數(shù) qi 表示詢問(wèn)。

輸出格式

Q 行，對(duì)于每個(gè)詢問(wèn)，如果存在至少一種組裝方案滿足條件，輸出 ‘YES‘，否則輸出 ‘NO‘。

樣例輸入

5 3
4 2 3 3 1
2
4
6

樣例輸出

YES
YES
NO

提示

詢問(wèn) 1 方案之一：2 3 3 4 1 。

詢問(wèn) 2 方案之一：4 2 3 3 1 。

詢問(wèn) 3 沒(méi)有方案。

對(duì)于 15% 的數(shù)據(jù)，保證 n, Q ≤ 100 ；

對(duì)于 30% 的數(shù)據(jù)，保證 n, Q ≤ 2000 ；

對(duì)于 100% 的數(shù)據(jù)，保證 n, Q ≤ 2 × 105 ; ri , qi ≤ 2 × 105 。

很容易知道的就是倍數(shù)只和頭尾轉(zhuǎn)輪有關(guān)，所以問(wèn)題轉(zhuǎn)換成了序列中是否存在兩個(gè)數(shù)a，b使得a/b=x。思路是先預(yù)處理一下有哪些x存在，然后查詢直接看存不存在這個(gè)x就行了。預(yù)處理的話，先排序然后對(duì)于每個(gè)ai，分解因數(shù)，看一下這個(gè)因數(shù)是否在a數(shù)組中出現(xiàn)過(guò)，假設(shè)因子為j，需要判斷（ai）/j是否在數(shù)組中存在，如果存在就x=j，同時(shí)如果j在數(shù)組中存在，那么存在x=（ai)/j，復(fù)雜度n^1.5。

剛開(kāi)始寫的時(shí)候沒(méi)有想著直接分解因數(shù)，而是采取了類似篩法的思路，在dotcpp上面過(guò)了，后面覺(jué)得有點(diǎn)懵，因?yàn)槲艺J(rèn)為時(shí)間復(fù)雜度說(shuō)不去的，后面跑到藍(lán)橋杯官網(wǎng)交了一發(fā)，也在規(guī)定時(shí)間內(nèi)跑完，但20發(fā)數(shù)據(jù)wa了一發(fā)小數(shù)據(jù)，對(duì)了95%，也不知道哪里錯(cuò)了，不過(guò)時(shí)間復(fù)雜度可以過(guò)就覺(jué)得蠻離譜的

95%的錯(cuò)誤代碼

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
void solve()
{
	int n,q;
	cin>>n>>q;
	int x;
	unordered_map<int,int>mp;
	unordered_map<int,int>ans;
	for(int i=1;i<=n;i++){
	cin>>x,mp[x]++;
	if(mp[x]>=2)
	ans[1]++;
}
	for(auto it:mp){
		for(int i=2;i*it.first<N;i++)
		if(mp[i*it.first]>0)
		ans[i]++;
		else
		mp.erase(i*it.first);
	}
	while(q--){
		cin>>x;
		if(ans[x]>0)
		cout<<"YES"<<'\n';
		else
		cout<<"NO"<<'\n';
	}
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

正確代碼

#include<bits/stdc++.h>
using namespace std;

int a[200005];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a[x]++;
    }
    while(m--){
        int x;
        cin>>x;
        int f=0;
        for(int i=1;i<=n/x;i++){
            if(a[i]&&a[i*x]){
                if(i!=i*x||i==i*x&&a[i]>1){
                    f=1;
                    break;
                } 
            }
        }
        if(f||(n==1&&x==1)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

題目 2700:

藍(lán)橋杯2022年第十三屆決賽真題-搬磚

題目描述

這天，小明在搬磚。

他一共有 n 塊磚，他發(fā)現(xiàn)第 i 磚的重量為 wi，價(jià)值為 vi。他突然想從這些磚中選一些出來(lái)從下到上堆成一座塔，并且對(duì)于塔中的每一塊磚來(lái)說(shuō)，它上面所有磚的重量和不能超過(guò)它自身的價(jià)值。

他想知道這樣堆成的塔的總價(jià)值（即塔中所有磚塊的價(jià)值和）最大是多少。

輸入格式

輸入共 n + 1 行，第一行為一個(gè)正整數(shù) n，表示磚塊的數(shù)量。

后面 n 行，每行兩個(gè)正整數(shù) wi , vi 分別表示每塊磚的重量和價(jià)值。

輸出格式

一行，一個(gè)整數(shù)表示答案。

樣例輸入

5
4 4
1 1
5 2
5 5
4 3

樣例輸出

10

提示

選擇第 1、2、4 塊磚，從上到下按照 2、1、4 的順序堆成一座塔，總價(jià)值為 4 + 1 + 5 = 10 。

對(duì)于 20% 的數(shù)據(jù)，保證 n ≤ 10；

對(duì)于 100% 的數(shù)據(jù)，保證 n ≤ 1000; wi ≤ 20; vi ≤ 20000 。

印象中第一次做這一類的題，這個(gè)應(yīng)該也是個(gè)蠻典的題，本人dp比較爛，做題過(guò)程中也算對(duì)01背包等一類背包問(wèn)題有了一些新的感悟，先說(shuō)感悟再說(shuō)解法

拿01背包來(lái)說(shuō)，01背包實(shí)際有一個(gè)隱含條件，對(duì)于dpij和dpkj，i小于k，選擇i后面可能可以選擇k，選擇k后面必然不能選擇i，在實(shí)際場(chǎng)景中如果兩者沒(méi)有實(shí)際的制約與時(shí)序關(guān)系，那么我們就需要構(gòu)造一個(gè)時(shí)序，在最基本01背包中，看起來(lái)i和k沒(méi)有什么制約關(guān)系，但實(shí)際我們?cè)O(shè)置狀態(tài)轉(zhuǎn)移方程時(shí)也假設(shè)了i只會(huì)出現(xiàn)在k之前而不會(huì)出現(xiàn)在k后面的條件。說(shuō)的不太清楚，湊合看看吧。

拿這個(gè)題來(lái)說(shuō)

對(duì)于每個(gè)磚塊怎么保證，他上面的重量總和小于等于他的價(jià)值呢，這個(gè)該怎么維護(hù)呢。實(shí)際上在紙上畫一畫，思考一下可以先處理上面的磚塊，再處理下面的磚塊，一點(diǎn)一點(diǎn)的處理，因?yàn)槟闳绻忍幚硐旅娴拇u塊，你怎么選對(duì)吧，才能保證下面的都滿足。所以先考慮上面的，從上往下每個(gè)磚塊都能線性處理。

定義dp[i] [j]是用了前i個(gè)磚塊，此時(shí)重量恰好為j的時(shí)候的最大價(jià)值。

但是這樣該怎么枚舉磚塊的順序呢？實(shí)際上這就是要排序，以前就做過(guò)這種，比如國(guó)王的游戲。這題可以讓i在上面，j在下面，我們讓wi+sum<vj，wj+sum>vi，也就是讓i在上面的時(shí)候j可以選，讓i在下面的時(shí)候，j不可以選了。所以轉(zhuǎn)化一下這個(gè)公式，可以把sum丟掉，sum是上面所有的重量。然后公式就是wi<vj,vi<wj。兩個(gè)想加可以得到wi+vi<wj+vj。所以按這個(gè)排序就行。然后對(duì)于維護(hù)每個(gè)磚塊上面的重量小于他的價(jià)值，其實(shí)在dp的時(shí)候加個(gè)判斷條件就夠了。然后其實(shí)就是01背包，加了一個(gè)貪心排序，和多了一個(gè)判斷條件。可以優(yōu)化為1維的。

沒(méi)有寫滾動(dòng)數(shù)組版本的，大家自己寫寫吧文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-477023.html

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
const ll mod = 1e9 + 7;
struct node {
	int w, v;
	bool operator<(const node& a) {
		return w + v < a.w + a.v;
	}
}p[1010];
int dp[1010][20010];
void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> p[i].w >> p[i].v;
	int ans = 0;
	sort(p + 1, p + 1 + n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n * 20 && j - p[i].w <= p[i].v; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j - p[i].w >= 0) {
				if (dp[i - 1][j - p[i].w] != 0)
					dp[i][j] = max(dp[i][j], dp[i - 1][j - p[i].w] + p[i].v);
				if (j - p[i].w == 0)
					dp[i][j] = max(p[i].v, dp[i][j]);
			}
			ans = max(dp[i][j], ans);
		}
	cout << ans << '\n';
}

int  main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

到了這里，關(guān)于第十三屆藍(lán)橋杯C++B組j國(guó)賽的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！