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

百度松果线上菁英班竞赛真题_小码哥最近在玩一个游戏叫做冰雪大冒险,这个游戏在一个n行m列的网格上进行。某些

作者：笔触狂放9 | 2024-04-09 11:41:25

赞

踩

小码哥最近在玩一个游戏叫做冰雪大冒险,这个游戏在一个n行m列的网格上进行。某些

目录

1.MC0101冰雪大冒险(难度：白银）

2.MC0102房间打扫(难度：白银）

3.MC0103数字统计(难度：白银）

4.MC0104项链(难度：黄金）

 5.函数的幂

6.剧场

7.污渍

8.白给

9.新河妇荡杯

10.曼哈顿矩阵

1.MC0101冰雪大冒险(难度：白银）

题目描述

小码哥最近在玩一个游戏叫冰雪大冒险，这个游戏在一个n行m列的网格上进行。某些格子上 存在一些无法通过的障碍物，其余均是光滑的冰面。

玩家初始在其中一个非障碍物的格子上，且保持静止，然后他会通过操控角色进行上下左右移动，当他控制角色朝一个方向移动时，角色会在冰面上一直滑行。直到角色移动方向的下一个是障碍物或者超出图的边界时，角色才会停止移动，然后等待小码哥的下一个操作。

现在给出地图中所有障碍物的位置，小码哥的初始位置和小码哥的操作序列，请你求出小码哥最终停留的位置。

输入格式

 第一行输入两个数n,m(2<=n,m<=100),表示地图的行数和列数。

第二行输入两个整数x，y(1<=x<=n,1<=y<=m),表示小码哥初始时在第x行第y列。

第三行输入一个整数k(1<=k<=n*m-1),表示地图上障碍物的个数。

接下来k行，每行两个数字ai,bi,表示第i个障碍物在第ai行第bi列，保证障碍物不会重叠，而且不会出现在小码哥初始位置上。

最后一行输入一个长度不超过1000，包含LRUD四种字母的字符串，字母第i个字母表示小码哥第i步的运动方向。U表示向上，D表示向下，L表示向左，R表示向右。

输出格式：输出两个整数，用空格隔开，表示小码哥的最终位置。 

样例输入

5 5

2 2

6

1 3

1 5

3 4

4 2

5 3

5 5

DRDRULUR 

样例输出

1 2 

解析：只需要模拟一下即可。

  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N=110;
  6.  
  7. int a[N][N];
  8. int n,m;
  9. int x,y;
  10. int t;
  11.  
  12. string s;
  13.  
  14. int main()
  15. {
  16.     cin>>n>>m;
  17.     cin>>x>>y;
  18.     cin>>t;
  19.     
  20.     while(t--)
  21.     {
  22.         int l,r;
  23.         cin>>l>>r;
  24.         a[l][r]=1;
  25.     }
  26.     
  27.     cin>>s;
  28.     
  29.     for(int i=0;i<s.size();i++)
  30.     {
  31.         switch(s[i])
  32.         {
  33.             case 'U':
  34.                 while(1)
  35.                 {
  36.                     if(a[x-1][y]==1||x==1) break;//只要不超过边界或者碰到障碍物，就一直走
  37.                     x--;
  38.                 }
  39.                 break;
  40.             case 'D':
  41.                 while(1)
  42.                 {
  43.                     if(a[x+1][y]==1||x==m) break;
  44.                     x++;
  45.                 }
  46.                 break;
  47.             case 'L':
  48.                 while(1)
  49.                 {
  50.                     if(a[x][y-1]==1||y==1) break;
  51.                     y--;
  52.                 }
  53.                 break;
  54.             case 'R':
  55.                 while(1)
  56.                 {
  57.                     if(a[x][y+1]==1||y==m) break;
  58.                     y++;
  59.                 }
  60.                 break;
  61.         }
  62.     }
  63.     
  64.     cout<<x<<" "<<y<<endl;
  65.     
  66.     return 0;
  67. }

2.MC0102房间打扫(难度：白银）

题目描述 

小码哥准备去打扫一件房间。这个房间可以简单地看成由n行n列，一共n*n个格子组成，每个格子的初始状态要么是干净的，要么是脏的。小码哥打扫房间的方式非常奇怪：如果他打扫了一个脏格子，这个格子就会变得很干净；反之亦然，如果打扫了一个干净的格子，就会变得很脏。

他想从n列的格子中选择几列进行打扫，希望打扫后完全干净的格子的行数尽可能多。注意：如果他选择了一列进行打扫，则它需要打扫这一列所有的格子；一行是干净，是指这一行所有的格子都是干净的。

小码哥并不是很擅长数学，于是希望你计算一下，如果他使用合理的打扫策略，完全打扫干净的行数最多可以有多少。

输入格式

第一行一个整数n(1<=n<=200)，表示房间的大小。

接下来n行n列的01串，1表示干净的，0表示脏的。

输出格式

输出一个整数，表示最大可能的完全干净的行数。 

样例输入

5

10001

10001

10010

00101

10001 

样例输出

3 

题解：看似是动态规划问题，实际是让统计哪种行数的状态最多，就拿上述例子来说，最多的初始行数为10001，数目为3,这样，开一个map哈希即可解决。

  1. #include<bits/stdc++.h>
  2. #include<map>
  3. using namespace std;
  4. const int N=1000;
  5. char a[N][N];
  6. map<string,int> mp;
  7. int main()
  8. {
  9.     int n;
  10.     cin>>n;
  11.     for(int i=1;i<=n;i++)
  12.     {
  13.         string b="";
  14.         for(int j=1;j<=n;j++)
  15.         {
  16.             cin>>a[i][j];
  17.             b+=a[i][j];
  18.         }
  19.         mp[b]++;
  20.     }
  21.     int ans=0;
  22.     for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++)
  23.     {
  24.         if(ans<it->second)
  25.             ans=it->second;
  26.     }
  27.     cout<<ans;
  28.     return 0;
  29. }

3.MC0103数字统计(难度：白银）

 题目描述

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int f(int n)
  4. {
  5.     int l=n;
  6.     int sum=0;
  7.     while(l)
  8.     {
  9.         sum=sum*10+l%10;
  10.         l/=10;
  11.     }
  12.     if(n%sum==0) return 1;
  13.     return 0;
  14. }
  15. int main()
  16. {
  17.     int n,ans=0;
  18.     cin>>n;
  19.     for(int i=1;i<=n;i++)
  20.         if(f(i)) ans++;
  21.     cout<<ans;
  22.     return 0;
  23. }

4.MC0104项链(难度：黄金）

题解：一开始想的是dfs把所有排列都枚举处理，但会TLE，我们不能发现，问题的规模是存在一个序列使得式子成立，我们就拿1 2 3 4，他只存在4 1 3 2 使得式子值最大，规律就是把所有序列排好然后第一个是最大的，第二个是最小的，第三个是第二大的，第四个是第二小的......

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e6+10;
  4. int a[N],b[N],vis[N];
  5. int ans,n;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(int i=1;i<=n;i++)
  10.         cin>>a[i];
  11.     sort(a+1,a+n+1);
  12.     int l=1,r=n;
  13.     int x=0;
  14.     while(l<=r)
  15.     {
  16.         b[++x]=a[r];
  17.         b[++x]=a[l];
  18.         l++;
  19.         r--;
  20.     }
  21.     for(int i=1;i<n;i++)
  22.     {
  23.         int p=b[i]-b[i+1];
  24.         if(p<0) p=-p;
  25.         ans+=p;
  26.     }
  27.     ans+=abs(b[n]-b[1]);
  28.     cout<<ans;
  29.     return 0;
  30. }

目录

 5.函数的幂

6.剧场

7.污渍

8.白给

9.新河妇荡杯

10.曼哈顿矩阵

 5.函数的幂

递归函数的调用：

  1. #include<iostream>
  2. using namespace std;
  3. int a;
  4. int b;
  5. int C;
  6. int D;
  7. int f(int a,int b)
  8. {
  9.     if(a==1) return (C*b+D)%10;
  10.     return f(a-1,f(a-1,b));
  11. }
  12. int main()
  13. {
  14.     cin>>a>>b>>C>>D;
  15.     cout<<f(a,b);
  16.     return 0;
  17. }

6.剧场

思路： 还是进行模拟，这一题有一个坑，每一秒是先把后面的人都往后移一位，然后才能进入新的人。

  1. #include<iostream>
  2. using namespace std;
  3. const int N=1000;
  4. char a[N][N];
  5. int main()
  6. {
  7.     int n;
  8.     cin>>n;
  9.     int t=n*n;
  10.     //先进行初始化
  11.     for(int i=1;i<=n;i++)
  12.         for(int j=1;j<=n;j++)
  13.             a[i][j]='0';
  14.     while(t--)
  15.     {
  16.         for(int i=n;i>=1;i--)
  17.         {
  18.             for(int j=n;j>=1;j--)
  19.             {
  20.                 if(j==1)
  21.                 {
  22.                     if(a[i][j]=='0'&&a[i-1][n]=='1')
  23.                     {
  24.                         a[i][j]='1';
  25.                         a[i-1][n]='0';
  26.                     }
  27.                 }
  28.                 else
  29.                 {
  30.                     if(a[i][j]=='0'&&a[i][j-1]=='1')
  31.                     {
  32.                         a[i][j]='1';
  33.                         a[i][j-1]='0';
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.         char x;
  39.         cin>>x;
  40.         if(x=='1') a[1][1]='1';
  41.         int ans=0;
  42.         for(int i=1;i<=n;i++)
  43.         {
  44.             int sum=0;
  45.             for(int j=1;j<=n;j++)
  46.             {
  47.                 if(a[i][j]=='1') sum++;
  48.             }
  49.             if(sum!=0) ans++;
  50.         }
  51.         cout<<ans<<" ";
  52.     }
  53.     return 0;
  54. }

7.污渍

分析：只需要讨论几种情况即可：包含，相离，相交。

  1. #include<iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     int a,b,v1,c,d,v2;
  6.     cin>>a>>b>>v1>>c>>d>>v2;
  7.     int x1=a,y1=b-v1,x2=a+v1,y2=b;
  8.     int x3=c,y3=d-v2,x4=c+v2,y4=d;
  9.     int m1,n1;
  10.     int m2,n2;
  11.     m1=max(min(x1,x2),min(x3,x4));
  12.     n1=max(min(y1,y2),min(y3,y4));
  13.     m2=min(max(x1,x2),max(x3,x4));
  14.     n2=min(max(y1,y2),max(y3,y4));
  15.     if(m2>m1&&n2>n1) 
  16.         cout<<v1*v1+v2*v2-(m2-m1)*(n2-n1);//相交
  17.     else 
  18.         cout<<v1*v1+v2*v2;//相离
  19.     return 0;
  20. }

8.白给

  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int x,y,n;
  8.     cin>>x>>y>>n;
  9.     while(n--)
  10.     {
  11.         if(x>=y)
  12.         {
  13.             int q=x/2;
  14.             x=x-q;
  15.             y=y+q;
  16.         }
  17.         else
  18.         {
  19.             int q=y/2;
  20.             x=x+q;
  21.             y=y-q;
  22.         }
  23.     }
  24.     cout<<x<<" "<<y<<endl;
  25.     return 0;
  26. }

9.新河妇荡杯

  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int a,b,c,s;
  8.     cin>>a>>b>>c>>s;
  9.     for(int i=1;;i++)
  10.     {
  11.         if(i/a+i/b+i/c==s)
  12.         {
  13.             cout<<i;
  14.             break;
  15.         }
  16.     }
  17.     return 0;
  18. }

10.曼哈顿矩阵

思路：找到规律即可，随便枚举一个数，找到四个象限之间和自己的坐标轴关系，如果是n，则它前面一定有 （n-1)!*4个数即可找到规律。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int x,y;
  7.     cin>>x>>y;
  8.     int n=abs(x)+abs(y);
  9.     int sum=0;
  10.     for(int i=0;i<n;i++)
  11.         sum+=i;
  12.     sum*=4;
  13.     int ans=0;
  14.     if(x>=1&&y>=0) ans=x;
  15.     else if(x>=0&&y<0) ans=x-2*y;
  16.     else if(x<=-1&&y<=0) ans=2*n-x;
  17.     else if(x<=0&&y>0) ans=2*n+2*y-x;
  18.     cout<<ans+sum;
  19.     return 0;
  20. }

  

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/392516
推荐阅读
相关标签

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

  

闽ICP备14008679号