第十四届蓝桥杯省赛游记

第十四届蓝桥杯省赛

我们是线上比赛，听说今年国赛还是省内分赛点，输麻了

期望得分 \(5+5+0+4+9+9+6+12+10+0= 60\) 能不能拿省一还不一定呢.。。

A 幸运数

没啥技术含量，暴力

#include <bits/stdc++.h>
using namespace std;
int getsum(int x)
{
	int sum = 0;
	while(x)
	{
		sum += x%10;
		x/=10;
	}
	return sum;
}
int lg[100000010];
int main()
{
	int cnt = 0;
	for(int i = 1;i <= 100000000;i++)
	{
		lg[i] = lg[i/10]+1;
	}
	//cout<<lg[999]<<" "<<lg[1000]<<" "<<lg[1001]<<endl;
	for(int i = 1;i <= 100000000;i++)
	{
		int x = lg[i];
		//cout<<x<<endl;
		if(x&1) continue;
		int a1 = i/pow(10,x/2);
		int a2 = i-a1*pow(10,x/2);
		//cout<<a1<<" "<<a2<<endl;
		if(getsum(a1)==getsum(a2)) cnt++;
	}
	cout<<cnt;
 } 
 //4430091

B 有奖问答

暴搜，还是没有技术含量233

#include <bits/stdc++.h>
using namespace std;
int cnt;
void dfs(int x,int nscore)
{
	if(nscore == 70) cnt++;
	if(x == 31||nscore == 100) return;
	dfs(x+1,nscore+10);
	dfs(x+1,0);
}
int main()
{
	dfs(1,0);
	cout<<cnt;
}
//8335366

C 平方差

给定 \(L ,R\)，问 $L \le x \le R $ 中有多少个数 \(x\) 满足存在整数 \(y\) , \(z\) 使得 \(x = y^2 - z^2\)。

\(1\le L \le R \le 10^9\)

考场上脑抽了，正解应该是除了 \(4n+2\) 不可以外都可以（奇数和可以被4整除的数，实现应该有点细节，等写一下

D 更小的数

长度为 \(n\) 且仅由数字组成的字符串，问多少连续子串可以通过反转使新数字更小

裸的区间DP，考场上看不出来，我是废了233

暴力，期望得分40％

//补题
#include <bits/stdc++.h>
using namespace std;
#define db double
#define ll long long
#define pii pair<int,int>
#define mm(a,b) memset(a,b,sizeof(a))
#define rush() int T; cin >> T; while (T--)
#define ACCELERATE (ios::sync_with_stdio(false),cin.tie(0))
int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9') {if(f == '-') f = -1; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){x = x*10 + ch - '0'; ch = getchar();}
	return x*f;
}
int f[5005][5005];
char s[5005];
int main()
{
	scanf("%s",s+1);
	int len = strlen(s+1);
	int ans = 0;
	for(int k = 2;k <= len;k++)
	{
		for(int i = 1;i + k - 1<= len;i++)
		{
			int j = i + k - 1;
			int a = s[i]-'0',b = s[j]-'0';
			if(a == b) f[i][j] = f[i+1][j-1];
			else if(a > b) f[i][j] = 1;
			else f[i][j] = 0;
			ans += f[i][j];
		}
	}
	cout<<ans; 
	return 0;
} 

E 颜色平衡树

说是启发式合并/线段树合并，不会，拿个60％部分分吧

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int head[maxn],to[maxn],nxt[maxn],cnt;
int dp[5010][5010];
int n,c[5050];
int ans = 0;
int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9') {if(f == '-') f = -1; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){x = x*10 + ch - '0'; ch = getchar();}
	return x*f;
}
void add(int x,int y)
{
	nxt[++cnt] = head[x];
	to[cnt] = y;
	head[x] = cnt;
}
void dfs(int x,int fa)
{
	dp[x][c[x]]+=1;
	for(int i = head[x];i;i = nxt[i])
	{
		int y = to[i];
		if(y == fa) continue;
		dfs(y,x);
		for(int i = 1;i <= 5000;i++) dp[x][i]+=dp[y][i];
	}
	int flag = 0,pd = 0,pdd = 0;
	for(int i = 1;i <= 5000;i++) 
	{
		if(dp[x][i]&&flag==0) pd = dp[x][i],flag = 1;
		else if(dp[x][i]&&flag)
		{
			if(dp[x][i] == pd) continue;
			else{
				pdd = 1;
				break;
			}
		}
	}
	if(!pdd) 
}
int main()
{
	n = read();
	for(int i = 1;i <= n;i++)
	{
		c[i] = read();
		int y = read();
		if(i!=1) add(i,y),add(y,i);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

F 买瓜

说是什么 DP 或双搜，又是我不会的了（做个蓝桥杯发现不会这么多）爆搜期望得分60％？

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll a[100],b[100];
ll visa[100],visb[100];
ll ans = 10000,use;
ll read()
{
	ll x = 0,f = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9') {if(f == '-') f = -1; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){x = x*10 + ch - '0'; ch = getchar();}
	return x*f;
}
void dfs(ll x)
{
	if(x == m) 
	{
		ans = min(ans,use);
		return;
	}
	if(x >= m) return;
	for(ll i = 1;i <= n;i++)
	{
		if(!visb[i]&&!visa[i])
		{
			visb[i] = 1;
			dfs(x+b[i]);
			visb[i] = 0;
		}
	}
	for(ll i = 1;i <= n;i++)
	{
		if(!visa[i]&&!visb[i])
		{
			use++;
			visa[i] = 1;
			dfs(x+a[i]);
			use--;
			visa[i] = 0;
		}
	}
		
}
int main()
{
	n = read(),m = read();
	for(ll i = 1;i <= n;i++) a[i] = read(),b[i] = 2*a[i];
	m*=2;
	dfs(0);
	if(ans == 10000) cout<<"-1";
	else cout<<ans;
	return 0;
}

G 网络稳定性

网上说是 \(kruskal\) 重构树板子题，后来看这不就是货车运输原题233，树上倍增LCA就行

不会，\(Floyd\) 期望得分 30％，\(Dijkstra\) 应该可以60%?

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int f[505][505];
int n,m,q;
int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9') {if(f == '-') f = -1; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){x = x*10 + ch - '0'; ch = getchar();}
	return x*f;
}
int main()
{
	n = read(),m = read(),q = read();
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) f[i][j] = -1;
	for(int i = 1;i <= m;i++) 
	{
		int x,y,z;
		x = read(),y = read(),z = read();
		f[x][y] = f[y][x] = z;
	}
	for(int k = 1;k <= n;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				f[i][j] = max(f[i][j],min(f[i][k],f[k][j]));
			}
		}
	}
	for(int i = 1;i <= q;i++)
	{
		int l = read(),r = read();
		cout<<f[l][r]<<endl;
	}
	return 0;
}

//补题，kruskal树上倍增LCA
#include <bits/stdc++.h>
using namespace std;
#define db double
#define ll long long
#define pii pair<int,int>
#define mm(a,b) memset(a,b,sizeof(a))
#define rush() int T; cin >> T; while (T--)
#define ACCELERATE (ios::sync_with_stdio(false),cin.tie(0))
int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9') {if(f == '-') f = -1; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){x = x*10 + ch - '0'; ch = getchar();}
	return x*f;
} 
const int maxm = 3e5+7;
int n,m,q;
int fa[100010];
int nxt[maxm<<1],to[maxm<<1],val[maxm<<1],cnt,head[100010];
int f[100010][30],w[100010][30],d[100010],vis[100010];
int find(int x)
{
	return fa[x] == x?x:fa[x] = find(fa[x]);
}
void add(int x,int y,int z)
{
	nxt[++cnt] = head[x];
	to[cnt] = y;
	val[cnt] = z;
	head[x] = cnt;
}
struct node{
	int x,y,z;
	bool operator < (const node &other)const
	{
		return z>other.z;
	}
}e[300010];
void kruskal()
{
	sort(e+1,e+m+1);
	for(int i = 1;i <= n;i++) fa[i] = i;
	for(int i = 1;i <= m;i++)
	{
		int x = find(e[i].x);
		int y = find(e[i].y);
		if(x!=y)
		{
			fa[x] = y;
			add(x,y,e[i].z);
			add(y,x,e[i].z);
		}
	}
}
void dfs(int x,int fa,int dis)
{
	vis[x] = 1; 
	f[x][0] = fa;
	d[x] = d[fa]+1;
	w[x][0] = dis;
	for(int k = 1;k <= 22;k++)
	{
		f[x][k] = f[f[x][k-1]][k-1];
		w[x][k] = min(w[x][k-1],w[f[x][k-1]][k-1]);
	}
	for(int i = head[x];i;i = nxt[i])
	{
		int v = to[i],w = val[i];
		if(v==fa) continue;
		dfs(v,x,w);
	}
}
int lca(int x,int y)
{
	if(d[x]<d[y]) swap(x,y);
	int ans = 0x3f3f3f3f;
	for(int k = 22;k >= 0;k--)
	{
		if(d[f[x][k]] >= d[y]) 
		{
			ans = min(ans,w[x][k]);
			x = f[x][k];
		}
	}
	if(x == y) return ans;
	for(int k = 22;k >= 0;k--)
	{
		if(f[x][k]!=f[y][k])
		{
			ans = min(ans,min(w[x][k],w[y][k]));
			x = f[x][k];
			y = f[y][k];
		}
	}
	ans = min(ans,min(w[x][0],w[y][0]));
	return ans;
}
int main()
{
	n = read(),m = read(),q = read();
	for(int i = 1;i <= m;i++)
	{
		e[i].x = read(),e[i].y = read(),e[i].z = read();
	}
	kruskal();
	for(int i = 1;i <= n;i++)
	{
		if(!vis[i]) dfs(i,0,0);
	}
	for(int i = 1;i <= q;i++)
	{
		int a,b;
		a = read(),b = read(); 
		if(find(a)!=find(b)) cout<<"-1"<<endl;
		else
		{
			cout<<lca(a,b)<<endl;
		}
	}
	return 0;
}

H 异或和之和

好像做过原题，但是忘了。。。

异或前缀和搞了个60％分，也止步于此了.

正解应该是由 \(0 \le A_i \le 2^{20}\) ，按位搞就可以了，复杂度 \(O(20n)\)?

考场代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
	ll x = 0,f = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9') {if(f == '-') f = -1; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){x = x*10 + ch - '0'; ch = getchar();}
	return x*f;
}
ll a[100010],sum[100010];
int main()
{
	ll n = read();
	for(ll i = 1;i <= n;i++) a[i] = read(),sum[i] =sum[i-1]^a[i];
	ll ans = 0;
	for(ll i = 1;i <= n;i++)
	{
		for(ll j = i;j <= n;j++)
		{
			ans += sum[j]^sum[i-1];
			ll k = sum[j]^sum[i-1];
			cout<<i<<" "<<j<<" ";
			cout<<k<<endl;
		}
	}
	cout<<ans;
	return 0;
}

I 像素放置

\(O(2^{nm})\)爆搜，估计拿不了50％，应该加点剪枝的

J 翻转硬币

数学题，盲区了