devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2021年中国大学生程序设计竞赛女生专场-ADGIK

作者：知新_RL | 2024-04-18 01:39:10

赞

踩

2021年中国大学生程序设计竞赛女生专场

昨天写了21年CCPC的女生赛，很庆幸自己的实力居然也能拿个牌子。一共写出来了六题，前面五题都还算是签到，妥妥手速场无疑了。废话不多说，开始讲解。

A. 公交线路

题意

小Q要坐公交，从站点x到y。公交车上有广播，但是小Q只能听见每一次广播站点的字数。你需要帮助小Q判定他是否坐反路线了。

思路

其实三个样例就已经对应了三种情况了。1.正确的 2.错误 3.不确定 ； 而出现第三种状况当且仅当存在以x为中心，左右两面念出来的字数是一样的。我们优先判定这种情况。然后在判断从x到y的各个站点的字数和小Q听到的一不一样就可以了。需要注意的是x和y的大小关系是不一定的。

代码

  1. #include<map>
  2. #include<cmath>
  3. #include<stack>
  4. #include<queue>
  5. #include <iomanip>  
  6. #include<cstdio>
  7. #include<vector>
  8. #include<string>
  9. #include<cstring>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define Endl "\n"
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int,int> pii;
  16. const int maxn = 2000007;
  17. const int INF = 0x3f3f3f;
  18. const int mod = 1e9 + 7;
  19. const double pi = acos(-1); 
  20. inline ll read(){
  21. 	ll x = 0, f = 1; char ch; ch = getchar();
  22. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  23. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  24. 	return x*f;
  25. }
  26. int n,x,y,m;
  27. bool flag;
  28. int luxian[15],ting[15];
  29. bool isok()
  30. {
  31.     int u=m;
  32.     int l,r;
  33.     for(int i=1;i<=m;i++)
  34.    {
  35.         l=x-i,r=x+i;
  36.         if(luxian[l]==luxian[r])
  37.         {
  38.             continue;
  39.         }
  40.         else
  41.         {
  42.             return true;
  43.         }
  44.    }
  45.    return false;
  46. }
  47. void solve() 
  48. {
  49.     n=read(),x=read(),y=read();
  50.     for(int i=1;i<=n;i++)
  51.     {
  52.         luxian[i]=read();
  53.     }
  54.     m=read();
  55.     for(int i=1;i<=m;i++)
  56.     {
  57.         ting[i]=read();
  58.     }
  59.     if(!isok())
  60.     {
  61.         cout<<"Unsure"<<Endl;
  62.     }
  63.     else if(isok()&&x<y)
  64.     {
  65.         flag=1;
  66.        for(int i=1;i<=m;i++)
  67.        {
  68.            int j=x+i;
  69.          if(ting[i]==luxian[j])
  70.          {
  71.            continue;
  72.          }
  73.          else
  74.          {
  75.             flag=0;
  76.             break;
  77.          }
  78.        }
  79.        if(flag) cout<<"Right"<<Endl;
  80.        else cout<<"Wrong"<<Endl;
  81.     }
  82.     else
  83.     {
  84.        flag=1;
  85.         for(int i=1;i<=m;i++)
  86.        {
  87.             int j=x-i;
  88.          if(ting[i]==luxian[j])
  89.          {
  90.            continue;
  91.          }
  92.          else
  93.          {
  94.             flag=0;
  95.             break;
  96.          }
  97.        }
  98.        if(flag) cout<<"Right"<<Endl;
  99.        else cout<<"Wrong"<<Endl;
  100.     }
  101. }
  102.  
  103. int main() {
  104. //for(int T = read(); T; T--)
  105. 		solve();
  106. 	return 0;
  107. }

D. 修建道路

题意

n个村庄，修n-1条双向道路，要求所有村庄都能互相到达。修路的花费是，如果要修从村庄i到j的路的话，那么花费是max{ak} k介于i和j之间。要求输出最少花费。

思路

区间越短，那么取到更大的数的概率也就越小。例如修村庄4到5的花费必然小于等于村庄4到6的花费。所以花费最少必然是从1到n按顺序串联起来：

那么答案就为连续相邻区间最大值的和。

代码

  1. #include<map>
  2. #include<cmath>
  3. #include<stack>
  4. #include<queue>
  5. #include <iomanip>  
  6. #include<cstdio>
  7. #include<vector>
  8. #include<string>
  9. #include<cstring>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define Endl "\n"
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int,int> pii;
  16. const int maxn = 2000007;
  17. const int INF = 0x3f3f3f;
  18. const int mod = 1e9 + 7;
  19. const double pi = acos(-1); 
  20. inline ll read(){
  21. 	ll x = 0, f = 1; char ch; ch = getchar();
  22. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  23. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  24. 	return x*f;
  25. }
  26. ll n,ans,x;
  27. ll a[200005];
  28. void solve() 
  29. {
  30.     ans=0;
  31.     n=read();
  32.     for(ll i=1;i<=n;i++)
  33.     {
  34.         a[i]=read();
  35.         if(i>=2)
  36.         {
  37.             x=max(a[i],a[i-1]);
  38.             ans+=x;
  39.         }
  40.     }
  41.     cout<<ans;
  42. }
  43.  
  44. int main() {
  45. //for(int T = read(); T; T--)
  46. 		solve();
  47. 	return 0;
  48. }

G. 3G网络

题意

建立n个3G基站，每个基站覆盖面积是半径为R的圆。给定n，求所有基站覆盖面积/每个基站覆盖面积之和。

思路

题目给了一个很关键的提示：

当r趋向于正无穷时，每个基站的覆盖面积都是无限大的，那么必然所有的圆都会相互覆盖，所以最后所有基站的覆盖面积可以看成是一个基站的覆盖面积S，每个基站的覆盖面积之和则为nS，所以直接输出1/n即可。

代码

  1. #include<map>
  2. #include<cmath>
  3. #include<stack>
  4. #include<queue>
  5. #include <iomanip>  
  6. #include<cstdio>
  7. #include<vector>
  8. #include<string>
  9. #include<cstring>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define Endl "\n"
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int,int> pii;
  16. const int maxn = 2000007;
  17. const int INF = 0x3f3f3f;
  18. const int mod = 1e9 + 7;
  19. const double pi = acos(-1); 
  20. inline ll read(){
  21. 	ll x = 0, f = 1; char ch; ch = getchar();
  22. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  23. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  24. 	return x*f;
  25. }
  26. double n;
  27. struct node{
  28.     int x;
  29.     int y;
  30. }q[2005];
  31. void solve() 
  32. {
  33.     cin>>n;
  34.     for(int i=1;i<=n;i++)
  35.     {
  36.         q[i].x=read(),q[i].y=read();
  37.     }
  38.     double ans=1.0/n;
  39.     printf("%.15lf",ans);
  40. }
  41.  
  42. int main() {
  43. //for(int T = read(); T; T--)
  44. 		solve();
  45. 	return 0;
  46. }

I. 驾驶卡丁车

题意

一道驾驶卡丁车的模拟+搜索题。有四个指令控制车头方向和车速，卡丁车可以向8个方向进行前进v步，直至出界、撞车、穿模。

思路

这道题在寒假集训的时候写过，我记得当时这题我写了特别特别久，怎么改都改不对。现在能轻松拿下来也算是进步了吧。

直接按照题意模拟即可。

首先卡丁车有两个状态参数一个是速度v，一个是车头朝向c。其次，拥有4种指令：

  1. /* 车头朝向与c的值
  2.  2  1  8
  3.  3     7
  4.  4  5   6
  5. */
  6. void l()
  7. {
  8.     if(c==8)
  9.         c=1;
  10.     else c+=1;
  11. }
  12. void r()
  13. {
  14.     if(c==1)
  15.         c=8;
  16.     else c-=1;
  17. }
  18. void u()
  19. {
  20.     v+=1;
  21. }
  22. void d()
  23. {
  24.     v=max(v-1,0);
  25. }

利用bfs的知识来模拟卡丁车走的情况：

  1. void rush()
  2. {
  3.     int xt,yt;
  4.     xt=x,yt=y;
  5.     for(int i=1;i<=v;i++)
  6.     {
  7.    //     cout<<"now"<<xt<<" "<<y<<Endl;
  8.         xt+=dist[c-1][0];
  9.         yt+=dist[c-1][1];
  10.   //      cout<<"now dist[c-1][0]"<<dist[c-1][0]<<" "<<dist[c-1][1]<<Endl;
  11.     //    cout<<xt<<" "<<yt<<Endl;
  12.     //    cout<<"over"<<Endl;
  13.         if(!iscrash(xt,yt))
  14.         {
  15.             v=0;
  16.             cout<<"Crash! "<<x<<" "<<y<<Endl;
  17.             return ;
  18.         }
  19.         else
  20.         {
  21.             x=xt,y=yt;
  22.         }
  23.     }
  24.     cout<<x<<" "<<y<<Endl;
  25. }

判定是否crash，有三种情况：1.撞到障碍物 2.出界 3.穿模

  1. bool iscrash(int x,int y)
  2. {
  3.     if(v==0) 
  4.         return true;
  5.     else
  6.     {
  7.    //     cout<<"---iscrash----"<<Endl;
  8.   //      cout<<x<<" "<<y<<" "<<c<<Endl;
  9.         if(x<=0||x>n||y<=0||y>m)
  10.         {
  11.    //         cout<<"here1"<<Endl;
  12.             return false;
  13.         }
  14.         else if(mp[x][y]=='#')
  15.         {
  16.    //         cout<<"here2"<<Endl;
  17.             return false;
  18.         }
  19.         else if(c==8&&mp[x][y-1]=='#'&&mp[x+1][y]=='#')
  20.         {
  21.    //         cout<<"here3"<<Endl;
  22.             return false;
  23.         }
  24.         else if(c==2&&mp[x][y+1]=='#'&&mp[x+1][y]=='#')
  25.         {
  26.    //         cout<<"here4"<<Endl;
  27.             return false;
  28.         }
  29.         else if(c==4&&mp[x-1][y]=='#'&&mp[x][y+1]=='#')
  30.         {
  31.   //          cout<<"here5"<<Endl;
  32.             return false;
  33.         }
  34.         else if(c==6&&mp[x][y-1]=='#'&&mp[x-1][y]=='#')
  35.         {
  36.   //          cout<<"here6"<<Endl;
  37.             return false;
  38.         }
  39.         else return true;
  40.     }
  41.     
  42. }


至此，问题基本解决。

代码

  1. #include<map>
  2. #include<cmath>
  3. #include<stack>
  4. #include<queue>
  5. #include <iomanip>  
  6. #include<cstdio>
  7. #include<vector>
  8. #include<string>
  9. #include<cstring>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define Endl "\n"
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int,int> pii;
  16. const int maxn = 2000007;
  17. const int INF = 0x3f3f3f;
  18. const int mod = 1e9 + 7;
  19. const double pi = acos(-1); 
  20. inline ll read(){
  21. 	ll x = 0, f = 1; char ch; ch = getchar();
  22. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  23. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  24. 	return x*f;
  25. }
  26. int n,m,q,x,y;
  27. int v,c;
  28. char mp[55][55];
  29. string zl;
  30. int dist[8][2]={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
  31. void l()
  32. {
  33.     if(c==8)
  34.         c=1;
  35.     else c+=1;
  36. }
  37. void r()
  38. {
  39.     if(c==1)
  40.         c=8;
  41.     else c-=1;
  42. }
  43. void u()
  44. {
  45.     v+=1;
  46. }
  47. void d()
  48. {
  49.     v=max(v-1,0);
  50. }
  51.  
  52. bool iscrash(int x,int y)
  53. {
  54.     if(v==0) 
  55.         return true;
  56.     else
  57.     {
  58.    //     cout<<"---iscrash----"<<Endl;
  59.   //      cout<<x<<" "<<y<<" "<<c<<Endl;
  60.         if(x<=0||x>n||y<=0||y>m)
  61.         {
  62.    //         cout<<"here1"<<Endl;
  63.             return false;
  64.         }
  65.         else if(mp[x][y]=='#')
  66.         {
  67.    //         cout<<"here2"<<Endl;
  68.             return false;
  69.         }
  70.         else if(c==8&&mp[x][y-1]=='#'&&mp[x+1][y]=='#')
  71.         {
  72.    //         cout<<"here3"<<Endl;
  73.             return false;
  74.         }
  75.         else if(c==2&&mp[x][y+1]=='#'&&mp[x+1][y]=='#')
  76.         {
  77.    //         cout<<"here4"<<Endl;
  78.             return false;
  79.         }
  80.         else if(c==4&&mp[x-1][y]=='#'&&mp[x][y+1]=='#')
  81.         {
  82.   //          cout<<"here5"<<Endl;
  83.             return false;
  84.         }
  85.         else if(c==6&&mp[x][y-1]=='#'&&mp[x-1][y]=='#')
  86.         {
  87.   //          cout<<"here6"<<Endl;
  88.             return false;
  89.         }
  90.         else return true;
  91.     }
  92.     
  93. }
  94. void rush()
  95. {
  96.     int xt,yt;
  97.     xt=x,yt=y;
  98.     for(int i=1;i<=v;i++)
  99.     {
  100.    //     cout<<"now"<<xt<<" "<<y<<Endl;
  101.         xt+=dist[c-1][0];
  102.         yt+=dist[c-1][1];
  103.   //      cout<<"now dist[c-1][0]"<<dist[c-1][0]<<" "<<dist[c-1][1]<<Endl;
  104.     //    cout<<xt<<" "<<yt<<Endl;
  105.     //    cout<<"over"<<Endl;
  106.         if(!iscrash(xt,yt))
  107.         {
  108.             v=0;
  109.             cout<<"Crash! "<<x<<" "<<y<<Endl;
  110.             return ;
  111.         }
  112.         else
  113.         {
  114.             x=xt,y=yt;
  115.         }
  116.     }
  117.     cout<<x<<" "<<y<<Endl;
  118. }
  119. void solve() 
  120. {
  121.     n=read(),m=read();
  122.     v=0,c=1;
  123.     for(int i=1;i<=n;i++)
  124.         for(int j=1;j<=m;j++)
  125.         {
  126.             cin>>mp[i][j];
  127.             if(mp[i][j]=='*')
  128.             {
  129.                 x=i;
  130.                 y=j;
  131.             }
  132.         }
  133.     q=read();
  134.     cin>>zl;
  135.     for(int i=0;i<q;i++)
  136.     {
  137.         if(zl[i]=='L')
  138.         {
  139.             l();
  140.         }
  141.         else if(zl[i]=='R')
  142.         {
  143.             r();
  144.         }
  145.         else if(zl[i]=='U')
  146.         {
  147.             u();
  148.         }
  149.         else
  150.         {
  151.             d();
  152.         }
  153.         rush();
  154.     }
  155. }
  156.  
  157. int main() {
  158. //for(int T = read(); T; T--)
  159. 		solve();
  160. 	return 0;
  161. }

K. 音乐游戏

题意

过于水的签到题了。

思路

直接统计-的个数即可。

代码

  1. #include<map>
  2. #include<cmath>
  3. #include<stack>
  4. #include<queue>
  5. #include <iomanip>  
  6. #include<cstdio>
  7. #include<vector>
  8. #include<string>
  9. #include<cstring>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define Endl "\n"
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int,int> pii;
  16. const int maxn = 2000007;
  17. const int INF = 0x3f3f3f;
  18. const int mod = 1e9 + 7;
  19. const double pi = acos(-1); 
  20. inline ll read(){
  21. 	ll x = 0, f = 1; char ch; ch = getchar();
  22. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  23. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  24. 	return x*f;
  25. }
  26. int n;
  27. char s;
  28. int ans;
  29. void solve() 
  30. {
  31.     ans=0;
  32.     n=read();
  33.     for(int i=1;i<=n;i++)
  34.     {
  35.         getchar();
  36.         for(int j=1;j<=6;j++)
  37.         {
  38.             scanf("%c",&s);
  39.             if(s=='-')
  40.             {
  41.                 ans++;
  42.             }
  43.         }
  44.     }
  45.     cout<<ans<<Endl;
  46. }
  47.  
  48. int main() {
  49. //for(int T = read(); T; T--)
  50. 		solve();
  51. 	return 0;
  52. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/443328
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号