第十四届蓝桥杯C++B组题解（不完全对）

A直接暴力枚举 答案235

#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second

using namespace std;

int va[200] = {0,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};

int vb[50] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

signed main()
{
	set<string> v;
	int n = 100;
	for(int y1=1;y1<=n;y1++)
	{
		if(va[y1]!=2) continue;
		for(int y2=y1+1;y2<=n;y2++)
		{
			if(va[y2]!=0) continue;
			for(int y3=y2+1;y3<=n;y3++)
			{
				if(va[y3]!=2) continue;
				for(int y4=y3+1;y4<=n;y4++)
				{
					if(va[y4]!=3) continue;
					for(int m1=y4+1;m1<=n;m1++)
					{
						for(int m2=m1+1;m2<=n;m2++)
						{
							for(int m3=m2+1;m3<=n;m3++)
							{
								for(int m4=m3+1;m4<=n;m4++)
								{
									int x1 = va[m1],x2 = va[m2],d1 = va[m3],d2 = va[m4];
									int mm = x1*10+x2,dd = d1*10+d2;
									if(mm<=12&&mm>=1&&dd>=1&&dd<=vb[mm])
									{
										char a = x1+'0',b = x2+'0',c = d1+'0',d = d2+'0';
										string s;
										s += a;s += b;s += c;s += d;
										v.insert(s);
									}
								}
							}
						}
					}
				}
			}
		}
	}
	cout<<v.size();
	for(auto t:v) cout<<t<<"\n";
}

B枚举0的个数，公式求一下。 11027421
代码比完忘记保存了

C思维

#include<bits/stdc++.h>
#define int long long
#define db double

using namespace std;

const int N = 2e5+10;

int n;
int va[N],vb[N];

signed main()
{
	scanf("%lld",&n);
	int anwl = 0,anwr = 2e9;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&va[i],&vb[i]);
		int l = va[i]/(vb[i]+1)+1;
		int r = va[i]/vb[i];
		anwl = max(anwl,l);
		anwr = min(anwr,r);
	}
	printf("%lld %lld",anwl,anwr);
	return 0;
}

D搜索+剪纸优化

#include<bits/stdc++.h>
#define int long long
#define db double

using namespace std;

const int N = 100;

struct Node{
	int a,b,c;
}va[N];

int T,n;
int vis[N];
int sta[50000];
int suc = 0;

void dfs(int now,int tim,int sum,int res)
{
	if(suc) return ;
	if(sta[res]==-1) return ;
	if(sum==n)
	{
		suc = 1;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;
		if(va[i].b<tim)
		{
			sta[res] = -1;
			return ;
		}
		vis[i] = 1;
		dfs(i,tim+va[i].c,sum+1,res+(1ll<<i));
		vis[i] = 0;
	}
}

signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		suc = 0;
		for(int i=1;i<=n;i++) vis[i] = 0;
		for(int i=0;i<=(1ll<<n);i++) sta[i] = 0;
		for(int i=1;i<=n;i++)
		{
			int a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c);
			va[i] = {a,a+b,c};
		}
		for(int i=1;i<=n;i++)
		{
			vis[i] = 1;
			dfs(i,0+va[i].c,1,(1ll<<i));
			vis[i] = 0;
		}
		if(suc) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

E动态规划，定义dp[i][j]为用到第i个，结尾为j最少要删多少个

#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second

using namespace std;

const int N = 1e5+10;

int n,m;
int va[N];
int l[N],r[N];
int dp[N][10];

int get(int x)
{
	while(x)
	{
		if(x<10) return x;
		x /= 10;
	}
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>va[i];
		l[i] = get(va[i]),r[i] = va[i]%10;
	}
	for(int i=1;i<=n;i++) for(int j=0;j<=9;j++) dp[i][j] = 1e9;
	for(int i=0;i<=9;i++)
	{
		if(i==r[1]) dp[1][i] = 0;
		else dp[1][i] = 1;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=9;j++)
		{
			if(j==r[i]) dp[i][j] = min(dp[i][j],dp[i-1][l[i]]);
			dp[i][j] = min(dp[i][j],dp[i-1][j]+1);
		}
	}
	int minn = 1e9;
	for(int i=0;i<=9;i++) minn = min(minn,dp[n][i]);
	cout<<minn;
	return 0;
}

F dfs+bfs

 #include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second

using namespace std;

int T,n,m;
char va[55][55];
int vis[55][55];
int dx[8] = {1,-1,0,0,-1,-1,1,1};
int dy[8] = {0,0,1,-1,-1,1,-1,1};

bool dfs(int A,int B)
{
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		vis[i][j] = 0;
	}
	queue<PII > q;
	q.push({A,B});
	vis[A][B] = 1;
	while(q.size())
	{
		auto now = q.front();q.pop();
		int x = now.fi,y = now.se;
		for(int i=0;i<8;i++)
		{
			int xx = x+dx[i],yy = y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m) return true;
			if(va[xx][yy]=='0'&&!vis[xx][yy])
			{
				vis[xx][yy] = 1;
				q.push({xx,yy});
			}
		}
	}
	return false;
}

void bfs(int A,int B)
{
	queue<PII > q;
	q.push({A,B});
	while(q.size())
	{
		auto now = q.front();q.pop();
		int x = now.fi,y = now.se;
		for(int i=0;i<4;i++)
		{
			int xx = x+dx[i],yy = y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&va[xx][yy]=='1')
			{
				va[xx][yy] = '0';
				q.push({xx,yy});
			}
		}
	}
}

signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			cin>>va[i][j];
		}
		int ans = 0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(va[i][j]=='1')
				{
					if(!dfs(i,j))
					va[i][j] = '0';
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(va[i][j]=='1')
				{
					ans++;
					bfs(i,j);
				}
			}
		}
		cout<<ans;
		if(T!=0) cout<<"\n";
	}
	return 0;
}

G 维护一个后缀即可

 #include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second

using namespace std;

const int N = 5e5+50;

int n,m;
char c1,c2;
char s[N];
int sumr[N];

signed main()
{
	cin>>m>>s+1>>c1>>c2;
	n = strlen(s+1);
	for(int i=n;i>=1;i--)
	{
		sumr[i] = sumr[i+1]+(s[i]==c2);
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]==c1&&i+m-1<=n)
		ans += sumr[i+m-1];
	}
	cout<<ans;
	return 0;
}

H 记录左右位置是谁

#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second

using namespace std;

const int N = 5e5+10;

int n,m;
int va[N];
int vis[N];
int l[N],r[N];

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<=n;i++)
	{
		if(i==1) l[i] = -1,r[i] = i+1;
		else if(i==n) l[i] = i-1,r[i] = -1;
		else l[i] = i-1,r[i] = i+1;
	}
	while(m--)
	{
		int minn = 1e9,idx = 0;
		int now = 1;
		while(now!=-1)
		{
			if(vis[now]==1) now = r[now];
			else
			{
				if(minn>va[now])
				{
					minn = va[now];
					idx = now;
				}
				now = r[now];
			}
		}
		if(l[idx]!=-1) va[l[idx]] += va[idx];
		if(r[idx]!=-1) va[r[idx]] += va[idx];
		vis[idx] = 1;
		r[l[idx]] = r[idx];
		l[r[idx]] = l[idx];
	}
	int now = 1;
	while(now!=-1)
	{
		if(vis[now]==1) now = r[now];
		else
		{
			cout<<va[now]<<" ";
			now = r[now];
		}
	}
	return 0;
}

I LCA

 #include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back

using namespace std;

const int N = 1e5+10;

int n,m;
int va[N];
int acc[N][25],cnt=22;
int dep[N],sum[N];

vector<PII > e[N];

void dfs(int now,int p)
{
	acc[now][0] = p;
	dep[now] = dep[p]+1;
	for(auto t:e[now])
	{
		int spot = t.fi,w = t.se;
		if(spot==p) continue;
		sum[spot] = sum[now]+w;
		dfs(spot,now);
	}
}

int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=cnt;i>=0;i--)
	{
		if(dep[acc[a][i]]>=dep[b])
		a = acc[a][i];
	}
	if(a==b) return a;
	for(int i=cnt;i>=0;i--)
	{
		if(acc[a][i]!=acc[b][i])
		{
			a = acc[a][i];
			b = acc[b][i];
		}
	}
	return acc[a][0];
}

int get(int a,int b)
{
	int res = sum[a]+sum[b]-2*sum[lca(a,b)];
	return res;
}

signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		e[a].pb({b,c});
		e[b].pb({a,c});
	}
	dfs(1,0);
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=n;j++)
		acc[j][i] = acc[acc[j][i-1]][i-1];
	}
	for(int i=1;i<=m;i++) scanf("%lld",&va[i]);
	int ans = 0;
	for(int i=1;i<m;i++) ans += get(va[i],va[i+1]);
	for(int i=1;i<=m;i++)
	{
		int res = 0;
		if(i==1) res = ans-get(va[i],va[i+1]);
		else if(i==m) res = ans-get(va[i],va[i-1]);
		else
		{
			res = ans-get(va[i],va[i-1])-get(va[i],va[i+1]);
			res += get(va[i-1],va[i+1]);
		}
		printf("%lld",res);
		if(i!=m) printf(" ");
	}
	return 0;
}

J 数据小的时候暴力枚举选择哪一天边可以，数据大直接-1

#include<bits/stdc++.h>
#define int long long
#define db double
#define PII pair<int,int >
#define fi first
#define se second

using namespace std;

const int N = 2e5+10;

int n,m;
PII va[N];
PII vb[N];
int acc[N];

int find(int x)
{
	if(x!=acc[x]) acc[x] = find(acc[x]);
	return acc[x];
}

bool check(int x)
{
	for(int i=1;i<=n;i++) acc[i] = i;
	for(int i=1;i<n;i++)
	{
		if(i==x) continue;
		int a = va[i].fi,b = va[i].se;
		int t1 = find(a),t2 = find(b);
		acc[t1] = t2;
	}
	for(int i=1;i<=m;i++)
	{
		int a = vb[i].fi,b = vb[i].se;
		int t1 = find(a),t2 = find(b);
		if(t1==t2) return false;
	}
	return true;
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<n;i++) cin>>va[i].fi>>va[i].se;
	for(int i=1;i<=m;i++) cin>>vb[i].fi>>vb[i].se;
	if(n*m>3e7||n*n>3e7)
	{
		cout<<-1;
		return 0;
	}
	for(int i=n-1;i>=1;i--)
	{
		if(check(i))
		{
			cout<<i;
			return 0;
		}
	}
	cout<<-1;
	return 0;
}