2022年 第十三届蓝桥杯 省赛 c++ B组

这次题目相较于2021年有了很大变动，最大的变化就是填空题变少了，编程题数量增加。

今年的填空题只有两道，还记得去年大一时学长的话，填空题全对就省一了。今年的题型变化导致身边的一些伙伴去年省一(无需编程，会数学即可)，今年就无缘国赛。

尽管位次同大一一致(弱势C++B组第三)，但在体验上确实有所不同，经过了一年的努力，至少省赛的每一道题都具有AK的潜力，(正式省赛时并没有十分重视，环境也比较嘈杂）。

接下来，就一起过一遍题目。

题目很蓝桥，手算，计算器算都可，值得一题的是，蓝桥比赛时配备了计算器插件，大概他们也很想送分。

依旧是填空题，纸上写写画画，14个。

首先由于年份为2022，这就相当于是无用信息，只需关注月日，仔细一些就好。

一道简单的整数周期问题，暴力可以拿5分，也不错。

10分代码

#include
using namespace std;
#define ll long long
int main()
{
	ios::sync_with_stdio(false);
	ll a,b,n;
	cin>>a>>b>>n;
	ll res=0;
	res+=n/(5*a+2*b)*7ll;
	n-=n/(5*a+2*b)*(5*a+2*b);
	if(n==0){cout< 
试题D：修建灌木 
 
水题，每棵树最多只用两个最值，向左绕回来或者向右绕回来。
 
#include
using namespace std;
#define ll long long
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cout< 
试题E：X进制减法 
 
这题就是贪心题，水题。
 
#include
using namespace std;
#define ll long long
const int maxn=100005;
const ll mod=1e9+7;
ll a[maxn],b[maxn];
int main()
{
	ios::sync_with_stdio(false);
	int n,a1,a2;
	cin>>n;
	cin>>a1;
	for(int i=1;i<=a1;i++)cin>>a[a1-i+1];
	cin>>a2;
	for(int i=1;i<=a2;i++)cin>>b[a2-i+1];
	ll ans=1;
	ll res=0;
	for(int i=1;i<=max(a1,a2);i++)
	{
		res=res+ans*(a[i]-b[i]+mod)%mod;
		res%=mod;
		ans*=max(2ll,max(a[i],b[i])+1);ans%=mod;
	}
	cout< 
试题F：统计子矩阵 
 
这题可以说是经典中的经典，早期学习算法时肯定都接触过，赛场上居然没想出
    
     
      
       
        
         n
        
        
         3
        
       
      
      
       n^3
      
     
    n3的做法，写了一个码量跟多的
    
     
      
       
        
         n
        
        
         4
        
       
      
      
       n^4
      
     
    n4做法，惭愧。
 
#include
using namespace std;
#define ll long long
const int maxn=505;
int a[maxn][maxn],sum1[maxn][maxn];
int main()
{
	ios::sync_with_stdio(false);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum1[i][j]=sum1[i][j-1]+a[i][j];
	ll res=0;
	for(int i=1;i<=m;i++)
	{
		
		for(int j=i;j<=m;j++)
		{
			int sum=0,t=1;
			for(int h=1;h<=n;h++)
			{
				sum+=sum1[h][j]-sum1[h][i-1];
				while(sum>k)sum-=(sum1[t][j]-sum1[t][i-1]),t++;
				res += h-t+1;
			}
		}
	}
	cout< 
试题G：积木画 
 
这道题可以说是dp的入门题了，将积木的铺法作为dp的转移方程，就能得到解了，这题也是最好拿分的题。
 
#include
using namespace std;
#define ll long long
const int maxn=1e7+8;
const ll mod=1e9+7;
ll dp[maxn][3];
int main()
{
	dp[0][0]=1;
	int n=1;cin>>n;
	for(int i=0;i<=n;i++)
	{
		dp[i+1][0]+=dp[i][0];dp[i+1][0]%=mod;
		dp[i+2][1]+=dp[i][0];dp[i+2][1]%=mod;
		dp[i+2][2]+=dp[i][0];dp[i+2][2]%=mod;
		dp[i+2][0]+=dp[i][0];dp[i+2][0]%=mod;
		dp[i+1][0]+=dp[i][1];dp[i+1][0]%=mod;
		dp[i+1][2]+=dp[i][1];dp[i+1][2]%=mod;
		dp[i+1][1]+=dp[i][2];dp[i+1][1]%=mod;
		dp[i+1][0]+=dp[i][2];dp[i+1][0]%=mod;
	}	
	cout< 
试题H：扫雷 
 
这个代码只拿了40%的分
 
#include
using namespace std;
#define ll long long
const int maxn=2e5+4;
const ll mod=1e9+7;
ll a[maxn],b[maxn],vis[maxn];
struct node
{
	ll x,y;
	ll r;
}c[maxn];
int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n+m;i++)cin>>c[i].x>>c[i].y>>c[i].r;
	queueq;
	for(int i=n+1;i<=n+m;i++)
	{
		q.push(c[i]);
	}
	int cnt=0;
	while(q.empty()!=1)
	{
		struct node x=q.front();q.pop();
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==1)continue;
			if((x.x-c[i].x)*(x.x-c[i].x)+(x.y-c[i].y)*(x.y-c[i].y)<=x.r*x.r)cnt++,q.push(c[i]),vis[i]=1;
		}
	}
	cout< 
试题 I：李白打酒加强版 
 
利用二进制枚举骗了40%的分
 
待补。。
 
赛场上想着dp，但没能想到正确的状态机构造方式
 
试题J：砍竹子 
 
用
    
     
      
       
        
         n
        
        
         2
        
       
      
      
       n^2
      
     
    n2的算法骗了20%的分，赛场上这道题挺有感觉的，想着利用带权并查集进行维护即可，被称为启发式合并，但是一直没写出来。