1024问

HNUCM 2020年春季ACM集训队热身赛-第2场总结

Halima ·
更新时间:2024-11-14
· 918 次阅读

HNUCM 2020年春季ACM集训队热身赛-第2场总结 文章目录HNUCM 2020年春季ACM集训队热身赛-第2场总结前言A：河畔军训B：不高兴的津津C：花生采摘D：FBI树E：火星人F：小B旅游G：括号匹配H：报数游戏I：小A的烦恼J：一步之遥 前言

不会写题解，只爱写总结（hhh）
感觉这套题整体还可以，没啥难题，但是又都有点意思，蒟蒻的我很多题都不是一发才过，还是太急了点，没怎么检查，立马就交了

A：河畔军训

比赛延长了一个小时，还是没做出来。。。
看题目就知道是三向bfs，但是奈何我的bfs太过于暴力，赛后看晖晖大佬的代码才A过

需要注意的是：
1、小h能走八个方向；小z和小y只能走四个方向
2、小h一秒最多能走3步；小z和小y一秒最多只能走1步

#include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxm=5000010; const int maxn=1e5+5; char mp[1010][1010]; bool vis[3][1010][1010]; int n,m; int dir[8][2]={0,1,0,-1,-1,0,1,0,-1,1,-1,-1,1,1,1,-1}; struct node{ int x,y; node(int xx,int yy){ x=xx,y=yy; } }; queueq[3]; int check(int x,int y,int id){ if(x>=1&&x=1&&y<=m&&vis[id][x][y]==0&&mp[x][y]!='#') return 1; return 0; } int bfs(int x){ int num=q[x].size(); while(num--){ node now=q[x].front(); q[x].pop(); for(int i=0;i=4&&(x==0||x==1)){ break; } int fx=now.x+dir[i][0]; int fy=now.y+dir[i][1]; if(check(fx,fy,x)){ vis[x][fx][fy]=1; q[x].push(node(fx,fy)); if(vis[0][fx][fy]&&vis[1][fx][fy]&&vis[2][fx][fy]){ return 1; } } } } return 0; } int solve(){ int dis=0; while(!q[0].empty()||!q[1].empty()||!q[2].empty()){ ++dis; if(bfs(0)){ return dis; } if(bfs(1)){ return dis; } for(int i=1;i<=3;i++){ if(bfs(2)){ return dis; } } } return -1; } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++){ scanf("%s",mp[i]+1); } while(!q[0].empty()){ q[0].pop(); } while(!q[1].empty()){ q[1].pop(); } while(!q[2].empty()){ q[2].pop(); } memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='z'){ vis[0][i][j]=1; q[0].push(node(i,j)); } else if(mp[i][j]=='y'){ vis[1][i][j]=1; q[1].push(node(i,j)); } else if(mp[i][j]=='h'){ vis[2][i][j]=1; q[2].push(node(i,j)); } } } //printf("%d %d\n",p1.x,p1.y); //printf("%d %d\n",p2.x,p2.y); //printf("%d %d\n",p3.x,p3.y); int ans=solve(); if(ans==-1){ printf("lack of junxun\n"); } else{ printf("%d\n",ans); } } return 0; } B：不高兴的津津

不光是津津不高兴了，我也不高兴了。这题输入居然是字符串，我也是醉了，搞的wa了三发

重点注意下这个即可，然后可能还有一个地方就是如果不高兴程度相同，则选择前面的

#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxn=1e5+5; int a[10],b[10]; string s; int main() { for(int i=1; i>s; a[i]=s[0]-'0'; b[i]=s[1]-'0'; } int maxnum=0; int ans=0; for(int i=1; i8) { if((a[i]+b[i])>maxnum) { ans=i; maxnum=(a[i]+b[i]); } } } printf("%d\n",ans); return 0; } C：花生采摘

虽然题目有点长，但是不难发现其实就是贪心的思想，我们用一结构体存花生的坐标和值；然后对值从大到小排序；然后再找。

需要注意的是：当选择对排序后的下一堆花生采摘时，需要考虑：采摘完之后能否回到道路

#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxn=1e5+5; int mp[30][30]; struct node{ int x,y; int num; }; node a[410]; int n,m,k; bool cmp(node xx,node yy){ return xx.num>yy.num; } int main(){ int t=0; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&mp[i][j]); if(mp[i][j]!=0){ a[t].x=i,a[t].y=j; a[t].num=mp[i][j]; t++; } } } sort(a,a+t,cmp); int prex=0,prey=a[0].y; int ans=0,cnt=0; for(int i=0;i<t;i++){ int dis=abs(a[i].x-prex)+abs(a[i].y-prey); if((dis+cnt+a[i].x+1)<=k){ cnt+=dis+1; ans+=a[i].num; prex=a[i].x,prey=a[i].y; } else{ break; } } printf("%d\n",ans); D：FBI树

很明显的建树，遍历树，但是如果按照传统的建树之后再遍历似乎显得有点麻烦，而且没有必要；本来建树和遍历的过程就是递归的过程，那我们为何不用递归的思想直接求呢

#include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxn=1e5+5; char s[maxn]; void solve(int l,int r){ int mid=(l+r)/2; if(l!=r){ solve(l,mid); solve(mid+1,r); } int flag1=0,flag2=0; for(int i=l;i<=r;i++){ if(s[i]=='0') flag1=1; else flag2=1; } if(flag1&&flag2){ printf("F"); } else if(flag1){ printf("B"); } else{ printf("I"); } } int main(){ int n; scanf("%d",&n); scanf("%s",s+1); solve(1,strlen(s+1)); printf("\n"); return 0; } E：火星人

全排列问题，但是需要注意的是：当得到结果后，需要结束全排列，不然肯定会超时。
有两种方法：
1、C++全排列函数，有时候比赛中，为了节省时间，这何尝不是一种好方法
2、递归，也很简单

C++全排列函数版本

#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxn=1e5+5; int a[10010]; int n,m; int main(){ scanf("%d",&n); scanf("%d",&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } int cnt=0; do{ cnt++; if(cnt==m+1){ printf("%d",a[1]); for(int i=2;i<=n;i++){ printf(" %d",a[i]); } printf("\n"); break; } }while(next_permutation(a+1,a+n+1)); return 0; } F：小B旅游

这题可能题意会有点小难理解，它是求将多种方案能经过的城市去重求和

可能还是比较容易想到用BFS，但是发现城市数很大，不能用链接矩阵存，那我们就用邻接链表吧，链表可能比较麻烦，于是我们就用数组模拟链表：链式向前星存图

链式向前星（数组模拟邻接表）

#include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxm=5000010; const int maxn=1e5+5; struct Edge{ int val,nxt; }edge[maxn*2]; struct node{ int num,dis; node(int x,int d){ num=x,dis=d; } }; int head[maxn],tot; int ans=0,vis[maxn]; int n,m,p; void add(int u,int v){ edge[tot].val=v; edge[tot].nxt=head[u]; head[u]=tot++; } void init(){ memset(head,-1,sizeof(head)); tot=0; } void bfs(){ queueq; q.push(node(1,0)); vis[1]=1; ans++; while(!q.empty()){ node now=q.front(); q.pop(); if(now.dis==p){ break; } for(int i=head[now.num];i!=-1;i=edge[i].nxt){ int v=edge[i].val; if(vis[v]==0){ vis[v]=1; q.push(node(v,now.dis+1)); ans++; } } } return ; } int main(){ init(); scanf("%d%d%d",&n,&m,&p); int u,v; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } ans=0; bfs(); printf("%d\n",ans); return 0; } G：括号匹配

还是很容易想到栈应用的，我们可以开三个栈，分别存{、[、(、

#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxn=1e5+5; string s; int main(){ cin>>s; stackst1,st2,st3; int len=s.length(); for(int i=0;i<len;i++){ if(s[i]=='{'){ st1.push(i); } else if(s[i]=='['){ st2.push(i); } else if(s[i]=='(') st3.push(i); else if(s[i]=='}'){ printf("%d %d\n",st1.top(),i); st1.pop(); } else if(s[i]==']'){ printf("%d %d\n",st2.top(),i); st2.pop(); } else if(s[i]==')'){ printf("%d %d\n",st3.top(),i); st3.pop(); } } return 0; } H：报数游戏

约瑟夫环，数据比较弱，我们用模拟完全可以过，但是也可以找下小规律

模拟法：

#include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxn=1e5+5; int t,n,m; vectorve; int flag[maxn]; int main(){ vector::iterator it; scanf("%d",&t); while(t--){ ve.clear(); memset(flag,0,sizeof(flag)); scanf("%d%d",&n,&m); int cnt=0; int ans=0; while(flag[1]==0){ for(int i=1;i<=n;i++){ if(flag[i]==0){ cnt++; } if(flag[i]==0&&cnt==m){ cnt=0; flag[i]=1; //cout<<i<<" "; ans++; } if(flag[1]){ break; } } if(flag[1]) break; } //cout<<endl; printf("%d\n",ans-1); } return 0; }

找规律，直接得答案（一个学弟想出来的）：

#include using namespace std; int main() { int t,n,m; cin>>t; while(t--) { cin>>n>>m; int num=1,ans=0,len=n; while(num!=m) { int w=num; ans+=(len+num-1)/m; num=(len+num-1)%m+1; len-=(len+w-1)/m; } cout<<ans<<endl; } } I：小A的烦恼

和F题很像，也是数比较大，我们只能用链式向前星存图，然后这里是求每个城市与其相邻的城市，按照输入顺序输出；我们只要在创建图的时候，同时开个数组存下每个城市相邻的城市即可，具体见代码：

#include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const ll mod=1e9+7; const double eps=1e-8; const int maxm=5000010; const int maxn=1e5+5; struct Edge{ int val,nxt; }edge[maxn*2]; int head[maxn],tot; int n,m; int vis[maxn]; struct node{ int num,dis; node(int x,int d){ num=x,dis=d; } }; vectorve[maxn]; void add(int u,int v){ edge[tot].val=v; edge[tot].nxt=head[u]; head[u]=tot++; ve[u].push_back(v); } void init(){ memset(head,-1,sizeof(head)); tot=0; } void solve(){ for(int i=1;i<=n;i++){ printf("%d",ve[i][0]); for(int j=1;j<ve[i].size();j++){ printf(" %d",ve[i][j]); } printf("\n"); } return ; } int main(){ init(); scanf("%d%d",&n,&m); int u,v; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } solve(); return 0; } J：一步之遥

这题就有点离谱，我用了个set，然后这题就特别水了

#include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll long long using namespace std; const double eps=1e-8; const int maxn=1e3+10; const ll mod=1e9+7; int n,m,p; setst; int main() { while(~scanf("%d%d%d",&n,&m,&p)) { st.clear(); int u,v; for(int i=1; i<=m; i++) { scanf("%d%d",&u,&v); if(u==p){ st.insert(v); } else if(v==p){ st.insert(u); } } printf("%d\n",st.size()); } return 0; }
作者：algorithmLB



acm

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
Shell脚本实现乱序排列文件内容的多种方法（洗牌问题）
Delphine 2021-05-01
928
ACM算法总结 动态规划（一）
Nita 2020-02-25
947
ACM基础（四）：排序之冒泡排序
Glenna 2021-01-18
732
开挂的人生！那些当选院士，又是ACM/IEEE 双料Fellow的华人学者们
Ingrid 2020-01-24
729
Java在ACM中的使用
Bonita 2020-02-11
816
ACM之java速成
Phyllis 2020-05-12
621
习题4-5 IP网络（IP Networks，ACM/ICPC NEERC 2005，UVa1590）
Elita 2021-04-28
726
关于计算机内的无穷(infinite)[INF](C/C++)(ACM)
Pearl 2021-02-13
562
ACM竞赛技巧总结
Madeleine 2020-09-13
719
ACM练习1 排列问题
Vida 2021-06-05
616
HNUCM2020年春季ACM集训队选拔赛(3)题解
Odessa 2020-10-01
888
ACM比赛经验、刷题记录及模板库总结（更新中）
Roxana 2021-06-22
644
【随笔】我的两年 ACM 回(心)忆(酸)录(路) 【多图预警】
Onida 2020-11-26
733
HNUCM2020年春季ACM集训队热身赛-第1场题解
Kathy 2021-05-20
714
HNUCM 2020年春季ACM集训队热身赛-第2场总结
Halima 2020-01-10
918
例题6-14 Abbott的复仇（Abbott's Revenge, ACM/ICPC World Finals 2000, UVa816)
Paloma 2021-06-08
961
习题6-10 10-20-30游戏（10-20-30, ACM/ICPC World Finals 1996, UVa246)
Levana 2020-06-16
614
编程比赛三大赛制介绍（ACM赛制、OI赛制、IOI赛制）
Vesta 2020-03-19
992
[ACM]【树形DP】牛客练习赛62 牛牛染颜色
Iona 2020-07-28
600
HNUCM2020年春季ACM集训队热身赛-第7场题解
Belle 2021-03-22
936