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

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

    A. 公交线路

    题意

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

    思路

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

    代码

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


    至此，问题基本解决。

    代码

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include   
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    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----"<
    59.   //      cout<
    60.         if(x<=0||x>n||y<=0||y>m)
    61.         {
    62.    //         cout<<"here1"<
    63.             return false;
    64.         }
    65.         else if(mp[x][y]=='#')
    66.         {
    67.    //         cout<<"here2"<
    68.             return false;
    69.         }
    70.         else if(c==8&&mp[x][y-1]=='#'&&mp[x+1][y]=='#')
    71.         {
    72.    //         cout<<"here3"<
    73.             return false;
    74.         }
    75.         else if(c==2&&mp[x][y+1]=='#'&&mp[x+1][y]=='#')
    76.         {
    77.    //         cout<<"here4"<
    78.             return false;
    79.         }
    80.         else if(c==4&&mp[x-1][y]=='#'&&mp[x][y+1]=='#')
    81.         {
    82.   //          cout<<"here5"<
    83.             return false;
    84.         }
    85.         else if(c==6&&mp[x][y-1]=='#'&&mp[x-1][y]=='#')
    86.         {
    87.   //          cout<<"here6"<
    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"<
    101.         xt+=dist[c-1][0];
    102.         yt+=dist[c-1][1];
    103.   //      cout<<"now dist[c-1][0]"<
    104.     //    cout<
    105.     //    cout<<"over"<
    106.         if(!iscrash(xt,yt))
    107.         {
    108.             v=0;
    109.             cout<<"Crash! "<" "<
    110.             return ;
    111.         }
    112.         else
    113.         {
    114.             x=xt,y=yt;
    115.         }
    116.     }
    117.     cout<" "<
    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
    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
    2. #include
    3. #include
    4. #include
    5. #include   
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    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<
    46. }
    47.  
    48. int main() {
    49. //for(int T = read(); T; T--)
    50. 		solve();
    51. 	return 0;
    52. }
  • 相关阅读:
    IntelliJ IDEA快速查询maven依赖关系
    程序员福音，关于如何使用Markdown写出一份漂亮的简历 —— 程序员简历 | md文档简历制作教程
    回调函数——qsort的模拟实现
    CSS（二）css选择器+css背景
    springboot 集成webSocket
    JAVAWEB复习
    HTTP状态码的含义；并且实现：如何实现多组输入
    Centos部署Docker
    Eunomia: 让 ebpf 程序的分发和使用像网页和 web 服务一样自然
    LLM研究之-NVIDIA的CUDA
  • 原文地址：https://blog.csdn.net/m0_66624446/article/details/126744729