蓝桥杯省赛参赛总结分两期更,获奖出来前和出来后

这是大一第一次参加较为正式的比赛,虽然是线上比赛,有不可避免的作弊现象,但是对于一个算法竞赛选手来讲,这并不应该成为拿不到一个好成绩的借口,算法竞赛,菜是原罪。

下面正式进入比赛分析阶段
由于是第一次参加省级别算法类竞赛,对成绩的预估很难把握住,蓝桥杯是oi赛制,即使是自己很有信心的题也很难有把握保证测试点全部通过。目前预估分差很大,在25~75之间。

这次题目难度比起去年要小一些,但是题量很大,两个填空八个编程

下面做一下总结,不包正确,都是个人考场的发挥,外加一些心理情绪上的总结

1.png

第一题签到题,进制转换小进制转大进制,第一次转的时候用相模除的方法做的。检查的时候发现这样得到的数就大了,小进制转多进制出来的数在十进制看来应该更小(因为大进制需要更多的数才能进位)
答案:1478     


2.png

这个题就很有歧义了,首先我不知道倒顺子算不算顺子,还有就是012算不算顺子(因为给的样例说出现了一个顺子是123,所以我觉得应该把0给否定掉了)。我这里的计算是没有算上0且没有算倒顺子。
答案:4

代码:


#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a=20210101;
	int f[8];
	long long i,t,j,cnt=0;
	for(a=20220101;a<=20221231;a++)
	{
		int n,y,d;
		n=a/10000;y=a/100%100;d=a%100;
		switch(y)
		{
			case 1: case 3: case 5: case 7: case 8: case 10: 
			case 12: if(d>31)	d=1,y++; break;
			case 4:case 6:case 9:case 11: if(d>30)	d=1,y++;break;
			case 2: if(d>28)	d=1,y++;break; 
		}
		a = n*10000+y*100+d;//新的
		t=a;
		i=7;
		while(t)
		{
			f[i]=t%10;
			t/=10;
			i--;
		}
		int flag=0;
		for(i=0;i<=5;i++)
		{
			if(f[i]!=0&&f[i+1]-f[i]==1&&f[i+2]-f[i+1]==1)
				flag =1;
		}
		if(flag)	
		{	cout<<a<<endl;
			cnt++;
		}
	}
	cout<<cnt;
}


3.png

这个题好冤啊,我是用的n的复杂度,也就是暴力。本来想着做完再回过头来改改优化优化,结果忘了,我丢。。。
10^18不知道能不能跑完┭┮﹏┭┮

给出暴力代码:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll a,b,n,k;
	cin>>a>>b>>n;
	ll	i=0;
	while(n>=0)
	{
		if(i%7==6||i%7==0)
			n-=b;
		else n-=a;
		i++;
	}
	cout<<i;
	return 0;
}


4.png

刚遇到这个题的时候,感觉没什么思路,我就当作难题然后放后面做了。后来回过头一看才10分,就尝试找了一下顾虑。这个题好像有些同学没有看出来,我是感觉对于每一个数,它的最好情况应该是左边数的数量和右边数的数量较大的那个乘以2

上代码:


#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<max(n-i,i-1)*2<<endl;
	}
	return 0;
}


5.png5-1.png

啊哈,这个题很苟啊。好多人都没看明白题,我做了好久也是白费,后来突然读懂题了。其实就是根据大的那个数来确定一个最小的进制,比如456,这个数最小,肯定末尾7进制,第二位6进制,第一位5进制。也就是当前这个数+1。枚举确定位数后,再根据题意和输入将首位和尾位确定(N,2)最后计算的时候一遍计算一遍取模(乘法原理好像是)

上代码:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll a[20];
	ll b[20];
	ll s[20];
	ll na,nb,i,j,n;
	cin>>n;
	cin>>na;
	for(i=1;i<=na;i++)
	{
		cin>>a[i];
		s[i]=a[i]+1;
	}
	s[i]=n;
	s[na]=2;
	cin>>nb;
	for(i=1;i<=nb;i++)
	{
		cin>>b[i];
	}
	ll ans=0,k=1;
	for(i=na;i>=1;i--)
	{
		ans+=k*a[i];
		k=k*s[i];
	}
	ll ans2=0,t=na;
	k=1; 
	for(i=nb;i>=1;i--)
	{
		ans2+=k*b[i];
		k=k*s[t];
		t--;
	}
	cout<<ans-ans2;
	return 0;
}



6.png

这个题唉,我真的无话可说。让我非常怀疑自己的刷题。我们集训队第一次模拟比赛时是我找的题,找了一道和这个几乎一致的题。当时没做出来,后来弄的半懂不懂。考试的时候只能自己用暴力方法做了,复杂度进(N^5)就是确定矩阵起点左上角和终点右下角,然后计算矩阵内的和(用前缀和相减)。唉,我是弱鸡啊,我是弱鸡。以后要好生对待自己做过的题。

给出比赛时的代码:


#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mapt[5000][5000];
ll s[5000][5000];

int main()
{
	ll n,m,kk;
	cin>>n>>m>>kk;
	ll i,j,k,l,w,cnt=0,t;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>mapt[i][j]; 
			s[i][j]=s[i][j-1]+mapt[i][j];
		} 
	}
	for(k=1;k<=n;k++)
	{
		for(t=1;t<=m;t++)
		{
			for(i=k;i<=n;i++)
			{
				for(j=t;j<=m;j++)
				{
					ll ans=0;
					for(w=k;w<=i;w++)
					{
						ans+=s[w][j]-s[w][t-1];
					} 
					if(ans<=kk)
						cnt++;
				}
			}
		}
		
	} 
	cout<<cnt;
	return 0;
}


7.png

这个题自己以前做到过原题,但是现在找不到了。唉,我又又又一次败在原题上了,可怕的不是跌倒,而是在一个地方跌倒了两次。
最后只能含泪写出混子代码:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n,ans=1,i;
	cin>>n;
	ll k=1;
	for(i=2;i<=n;i++)
	{
		if(i%2==1)
		ans=ans*2+1;
		else ans=ans*2;
		ans%=1000000007;
	}
	cout<<ans;
	return 0;
}


8.png8-1.png

这个题浪费了我很多时间,特别特别多,一直再检查改错。思路其实就是bfs但是不能用邻接矩阵来存储,要用邻接表来存储。用结构体存放地雷和火箭的信息,将火箭入列然后bfs搜,因为搜索面积是圆,我不知道会不会卡一下精度问题,我就令距离和r<=1e-6。如果这个题大部分的分都拿了,感觉就差不多有60分左右了,感觉拿奖有望。但是如果有什么闪失,估计这次比赛就凉了。我这做题有个毛病就是不怎么爱做测试点,感觉acm赛制或许能对我友好一些,虽然会罚时。之前在校赛,我有个题罚了10多次(在自己领先第二两个题情况下疯狂提交改错)

上代码:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct lei{
	ll x,y,r;
};
queue<lei> q;
vector<lei> za;
ll newr;
bool panduan(double x1,double y1,double x2,double y2,double r)
{
	double d = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	//cout<<d<<endl;
	if(fabs(d-r)<1e-5)
		return true;
	return false;
}
bool cunzai(ll i,ll j)
{
	ll k;
	for(k=0;k<za.size();k++)
	{
		/*cout<<"@"<<za[k].x<<i<<"@";
		cout<<"@"<<za[k].y<<j<<"@"<<endl;*/
		if(za[k].x==i&&za[k].y==j)
		{
			newr = za[k].r;
			za[k].r=0;
			return true;
		}
	}
	return false;
}
int main()
{
	ll n,m;
	cin>>n>>m;
	ll i,j,k,a,b,c;
	for(i=1;i<=n;i++)
	{
		cin>>a>>b>>c;
		za.push_back({a,b,c});
	}
	for(i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		q.push({a,b,c});
	}
	while(!q.empty())
	{
		lei f= q.front();
		q.pop();
		ll curx = f.x;
		ll cury = f.y;
		ll curr = f.r;
		for(i=curx-curr;i<=curx+curr;i++)
		{
			for(j=curx-curr;j<=curx+curr;j++)
			{
			//	cout<<i<<' '<<j<<endl; 
				if(cunzai(i,j)&&panduan(i,j,curx,cury,curr))//
				{
					q.push({curx+i,cury+j,newr});
				}
			}
		}
	}
	ll cnt=0;
	for(i=0;i<za.size();i++)
	{
		if(za[i].r==0)	cnt++;
			//cout<<za[i].x<<' '<<za[i].y<<' '<<za[i].r<<endl;
		
	}
	cout<<cnt;
	return 0;
}


9.png

要是能重来,绝不做李白。这题废了我很长的时间,我刚看完题,心想,这不就是dfs嘛,直接搜。然后做着做着发现没那么简单,很多条件可能自己想不到,条件之间摆放的位置也想不明白,感觉这题挺考验思维的。啃了好久这个题,最后还是没能啃下来,最后含泪混了

混子代码:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans=0,n,m;
void dfs(ll d,ll h,ll j)
{
	if(j>h)	return;
	if(d==0&&h==0&&j==0)
	{
		ans++;
		ans%=1000000007;
		return ;	
	} 
	if(d==0&&j<h) 
		return;
	
	if(j!=0)
		dfs(d,h-1,j-1);//遇花 
	dfs(d-1,h,j*2);//遇店 
}
int main()
{
	cin>>n>>m;
	dfs(n,m,2);
	if(ans%2==0)
		cout<<ans/2;
	else
		cout<<ans/2+1;
	return 0;
}


10.png

这个题感觉我会做,但是已经没有时间了,我多么应该把李白那题的时间放在这个题上。
ε=(´ο`*)))唉。这个题最后好像是提交了一个别的题的代码。
下面说说我的思路,每次找一个最大的数,如果这个数周围有和他相同的数那么一起砍掉,否则砍掉这一个。感觉这个思路应该能过不少测试点。可惜啊


最后总结:这次比赛的发挥挺让我失望的,尤其是因为两个遇到过的原题都没做出来,最后一题有思路也没时间做了。估计也就是4到编程+1/2道填空吧。作为一个acmer(acm弱校,大佬勿喷),感觉自己真的很菜。在大学之前还美其名曰接触过算法,在中专学习期间学了很多很多东西,但是现在来看真的都是些皮毛。现在的算法学习感觉很吃力,自己已经决心要将大半个大学生活放到算法竞赛上了,也不知道最后结果会是怎样。再过两周就要天梯赛,然后再两周就acm山东省赛,祝自己好运了。