蓝桥杯省赛参赛总结分两期更,获奖出来前和出来后
这是大一第一次参加较为正式的比赛,虽然是线上比赛,有不可避免的作弊现象,但是对于一个算法竞赛选手来讲,这并不应该成为拿不到一个好成绩的借口,算法竞赛,菜是原罪。
下面正式进入比赛分析阶段
由于是第一次参加省级别算法类竞赛,对成绩的预估很难把握住,蓝桥杯是oi赛制,即使是自己很有信心的题也很难有把握保证测试点全部通过。目前预估分差很大,在25~75之间。
这次题目难度比起去年要小一些,但是题量很大,两个填空八个编程
下面做一下总结,不包正确,都是个人考场的发挥,外加一些心理情绪上的总结
第一题签到题,进制转换小进制转大进制,第一次转的时候用相模除的方法做的。检查的时候发现这样得到的数就大了,小进制转多进制出来的数在十进制看来应该更小(因为大进制需要更多的数才能进位)
答案:1478
这个题就很有歧义了,首先我不知道倒顺子算不算顺子,还有就是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; }
这个题好冤啊,我是用的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; }
刚遇到这个题的时候,感觉没什么思路,我就当作难题然后放后面做了。后来回过头一看才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; }
啊哈,这个题很苟啊。好多人都没看明白题,我做了好久也是白费,后来突然读懂题了。其实就是根据大的那个数来确定一个最小的进制,比如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; }
这个题唉,我真的无话可说。让我非常怀疑自己的刷题。我们集训队第一次模拟比赛时是我找的题,找了一道和这个几乎一致的题。当时没做出来,后来弄的半懂不懂。考试的时候只能自己用暴力方法做了,复杂度进(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; }
这个题自己以前做到过原题,但是现在找不到了。唉,我又又又一次败在原题上了,可怕的不是跌倒,而是在一个地方跌倒了两次。
最后只能含泪写出混子代码:
#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; }
这个题浪费了我很多时间,特别特别多,一直再检查改错。思路其实就是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; }
要是能重来,绝不做李白。这题废了我很长的时间,我刚看完题,心想,这不就是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; }
这个题感觉我会做,但是已经没有时间了,我多么应该把李白那题的时间放在这个题上。
ε=(´ο`*)))唉。这个题最后好像是提交了一个别的题的代码。
下面说说我的思路,每次找一个最大的数,如果这个数周围有和他相同的数那么一起砍掉,否则砍掉这一个。感觉这个思路应该能过不少测试点。可惜啊
最后总结:这次比赛的发挥挺让我失望的,尤其是因为两个遇到过的原题都没做出来,最后一题有思路也没时间做了。估计也就是4到编程+1/2道填空吧。作为一个acmer(acm弱校,大佬勿喷),感觉自己真的很菜。在大学之前还美其名曰接触过算法,在中专学习期间学了很多很多东西,但是现在来看真的都是些皮毛。现在的算法学习感觉很吃力,自己已经决心要将大半个大学生活放到算法竞赛上了,也不知道最后结果会是怎样。再过两周就要天梯赛,然后再两周就acm山东省赛,祝自己好运了。