十五届蓝桥杯赛题-c/c++ 大学b组

握手问题

很简单，相互牵手即可，但是要注意，第一个人只能与其他49个人牵手，所以开头是加上49

1. #include <iostream>
2. using namespace std;
3. int main()
4. {
5.   int cnt=0;
6.   for(int i=49;i>=7;i--){
7.     cnt+=i;
8.     //cout<<i<<" ";
9.   }
10.   cout<<cnt;
11.   return 0;
12. }

复制代码

小球反弹

好数

直接从1到n循环判断即可，只要有一次不符合条件就不算

1. #include <iostream>
2. #include<string>
3. #include<algorithm>
4. using namespace std;
5. int res=0;
6. int main()
7. {
8.   //奇数位数字奇数，偶数位
9.   int n;cin>>n;
10.   for(int i=1;i<=n;i++){
11.     string a=to_string(i);
12.     reverse(a.begin(),a.end());
13.     bool flag=false;
14.     for(int j=0;j<a.length();j++){
15.       if(j%2==0&&a[j]%2==0)//偶分位不为偶数
16.         flag=true;
17.       if(j%2!=0&&a[j]%2!=0)
18.         flag=true;
19.     }
20.     if(flag==false)res++;
21.   }
22.   cout<<res;
23.   return 0;
24. }

复制代码

R格式

这道题原来是想，先对2的次方用高精度求解，再将浮点型转化为整型，用高精乘低精度求，但是，没有考虑到这个浮点型数组范围太大，只能用字符串进行表现

1. #include <bits/stdc++.h>
2. using namespace std;
3. //高精乘低精
4. vector<int>mul1(vector<int>&A,int b){
5.   vector<int> C;
6.   //t为进位
7.   int t=0;
8.   for(int i=0;i<A.size()||t;i++){
9.     if(i<A.size())t+=A[i]*b;
10.     C.push_back(t%10);
11.     //进位
12.     t/=10;
13.   }
14.   //去除前导零
15.   while(C.size()>1&&C.back()==0)C.pop_back();
16.   return C;
17. }
18. int main()
19. {
20.   int cnt=0;//处理小数点
21.   //你要想需要把浮点数转化为整型
22.   //输入n，将浮点数
23.   int n;string m;cin>>n>>m;
24.   vector<int>a;
25.   //这里将浮点数字符串存入动态数组
26.   for(int i=m.length()-1;i>=0;i--){
27.     if(m[i]!='.')a.push_back(m[i]-'0');
28.     else cnt=m.length()-i-1;//几位小数
29.   }
30.   //高精度乘低精度，高精度是浮点数，低精度就是2的次方个数
31.   while(n--)a=mul1(a,2);
32.   //结果再加上小数
33.   for(int i=a.size()-1;i>=0;i--){
34.     //cout<<"进入这";
35.     if(i==cnt){
36.       //达到小数点，开始进行四舍五入判断
37.       if(a[i-1]>=5){
38.         cout<<a[i]+1;
39.         break;
40.       }
41.       else{
42.         cout<<a[i];
43.         break;
44.       }
45.     }
46.     cout<<a[i];
47.   }
48.   return 0;
49. }

复制代码

宝石组合：

这一题应该暴力能过40%左右，但是我的暴力竟然过了0%，老脸丢尽，厥后开始思索dfs，但是过程中碰到了几个问题，
数字接龙

这题一看就是dfs，跟走迷宫很像，不外加了几个限定条件
路径不能交织，而且这个是根据1，2，3，n-1进行路径的遍历，另外这个需要输出路径的方向
那么我在思索的时间碰到了几个问题：

• 怎样表现才能让它的路径不进行交织
  
• 怎样储存这个路径而且输出
  

那么在看完题解之后得出了解决方案

• 八个方位，那么就需要8个不同的偏移量去存储
  
• 需要用一个四维数组去存储路径来制止交织
  
• 输出用字符串输出即可
  

2. #include <iostream>
3. using namespace std;
4. #include <bits/stdc++.h>
5. using namespace std;
6. string ans;
7. int n,k;
8. int a[15][15],m[15][15];
9. int mark[15][15][15][15];
10. int nx[8]={-1,-1,0,1,1,1,0,-1};
11. int ny[8]={0,1,1,1,0,-1,-1,-1};//这个方向刚好是根据循环来设置的，i等于几走那个方向是有意义的
12. void dfs(int x,int y,string s,int t){
13.   if(ans.size())return ;//剪枝
14.   if(x==n-1&&y==n-1){
15.     if(s.size()==n*n-1)ans=s;
16.     return;//将该结果储存到字符串中
17.   }
18.   for(int i=0;i<8;i++){
19.     //8个方向
20.     int tx=x+nx[i];int ty=y+ny[i];
21.     if(tx<n&&tx>=0&&ty<n&&ty>=0&&a[tx][ty]==t&&m[tx][ty]==0){
22.       //不超范围，并且没有走过，并且顺序正确
23.       if(i%2&&mark[tx][y][x][ty])continue;//奇数时就要斜着走，那么斜着走但是这个位置的交叉线走过，那么continue不走这个，判断是否交叉
24.       //不过这个方位判断不太明白,这个是交叉线，比如你这次要从[x][y]走到[tx][ty],那么就判断该交叉线的斜方向交叉线
25.       m[tx][ty]=1;
26.       mark[tx][ty][x][y]=mark[x][y][tx][ty]=1;
27.       dfs(tx,ty,s+to_string(i),(t+1)%k);
28.       mark[tx][ty][x][y]=mark[x][y][tx][ty]=0;//撤销标记
29.       m[tx][ty]=0;
30.     }
31.   }
32. }
33. int main()
34. {
35.   cin>>n>>k;
36.   for(int i=0;i<n;i++){
37.     for(int j=0;j<n;j++){
38.       cin>>a[i][j];
39.     }
40.   }
41.   m[0][0]=1;
42.   dfs(0,0,"",1%k);//第一步也要处理
43.   if(ans=="")cout<<"-1";
44.   else cout<<ans;
45.   return 0;
46. }

复制代码

拔河

这是一个非常暴力的解法，枚举所有效果进行排序即可

1. #include<iostream>
2. #include<algorithm>
3. #define int long long
4. using namespace std;
5. const int N=1e3+10;
6. int n,js=1,a[N],check[N*N];
7. signed main(){
8.     cin>>n;
9.     for(int i=1;i<=n;i++)cin>>a[i];
10.     for(int i=1;i<=n;i++){//我们先通过二层循环，暴力出每一种选法
11.         int s=0;
12.         for(int j=i;j<=n;j++){
13.             s+=a[j];//这里的每一种选法，就是从1-n的所有选法
14.             check[js++]=s;
15.         }
16.     }//可能有谁都不选的选法，check数组从0开始
17.     sort(check,check+js);
18.     //将他们从小到大排序，力量值之和差距最小的一定是相邻的两种选法
19.     //不用管区间选择重叠的情况，重叠部分相当于两种选法都没选重叠部分
20.     int ans=1e12+10;
21.     for(int i=1;i<js;i++)ans=min(ans,check[i]-check[i-1]);
22.     cout<<ans;
23.     return 0;
24. }

复制代码