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

握手问题

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

#include <iostream>
using namespace std;
int main()
{
  int cnt=0;
  for(int i=49;i>=7;i--){
    cnt+=i;
    //cout<<i<<" ";
  }
  cout<<cnt;
  return 0;
}

小球反弹

好数

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

#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
int res=0;
int main()
{
  //奇数位数字奇数，偶数位
  int n;cin>>n;
  for(int i=1;i<=n;i++){
    string a=to_string(i);
    reverse(a.begin(),a.end());
    bool flag=false;
    for(int j=0;j<a.length();j++){
      if(j%2==0&&a[j]%2==0)//偶分位不为偶数
        flag=true;
      if(j%2!=0&&a[j]%2!=0)
        flag=true;
    }
    if(flag==false)res++;
  }
  cout<<res;
  return 0;
}

R格式

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

#include <bits/stdc++.h>
using namespace std;
//高精乘低精
vector<int>mul1(vector<int>&A,int b){
  vector<int> C;
  //t为进位
  int t=0;
  for(int i=0;i<A.size()||t;i++){
    if(i<A.size())t+=A[i]*b;
    C.push_back(t%10);
    //进位
    t/=10;
  }
  //去除前导零
  while(C.size()>1&&C.back()==0)C.pop_back();
  return C;
}
int main()
{
  int cnt=0;//处理小数点
  //你要想需要把浮点数转化为整型
  //输入n，将浮点数
  int n;string m;cin>>n>>m;
  vector<int>a;
  //这里将浮点数字符串存入动态数组
  for(int i=m.length()-1;i>=0;i--){
    if(m[i]!='.')a.push_back(m[i]-'0');
    else cnt=m.length()-i-1;//几位小数
  }
  //高精度乘低精度，高精度是浮点数，低精度就是2的次方个数
  while(n--)a=mul1(a,2);
  //结果再加上小数
  for(int i=a.size()-1;i>=0;i--){
    //cout<<"进入这";
    if(i==cnt){
      //达到小数点，开始进行四舍五入判断
      if(a[i-1]>=5){
        cout<<a[i]+1;
        break;
      }
      else{
        cout<<a[i];
        break;
      }
    }
    cout<<a[i];
  }
  return 0;
}

宝石组合：

这一题应该暴力能过40%左右，但是我的暴力竟然过了0%，老脸丢尽，后来开始思考dfs，但是过程中遇到了几个问题，

数字接龙

这题一看就是dfs，跟走迷宫很像，不过加了几个限制条件

路径不能交叉，并且这个是根据1，2，3，n-1进行路径的遍历，另外这个需要输出路径的方向

那么我在思考的时候遇到了几个问题：

如何表示才能让它的路径不进行交叉
如何储存这个路径并且输出

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

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


#include <iostream>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
string ans;
int n,k;
int a[15][15],m[15][15];
int mark[15][15][15][15];
int nx[8]={-1,-1,0,1,1,1,0,-1};
int ny[8]={0,1,1,1,0,-1,-1,-1};//这个方向刚好是根据循环来设置的，i等于几走那个方向是有意义的
void dfs(int x,int y,string s,int t){
  if(ans.size())return ;//剪枝
  if(x==n-1&&y==n-1){
    if(s.size()==n*n-1)ans=s;
    return;//将该结果储存到字符串中
  }
  for(int i=0;i<8;i++){
    //8个方向
    int tx=x+nx[i];int ty=y+ny[i];
    if(tx<n&&tx>=0&&ty<n&&ty>=0&&a[tx][ty]==t&&m[tx][ty]==0){
      //不超范围，并且没有走过，并且顺序正确
      if(i%2&&mark[tx][y][x][ty])continue;//奇数时就要斜着走，那么斜着走但是这个位置的交叉线走过，那么continue不走这个，判断是否交叉
      //不过这个方位判断不太明白,这个是交叉线，比如你这次要从[x][y]走到[tx][ty],那么就判断该交叉线的斜方向交叉线
      m[tx][ty]=1;
      mark[tx][ty][x][y]=mark[x][y][tx][ty]=1;
      dfs(tx,ty,s+to_string(i),(t+1)%k);
      mark[tx][ty][x][y]=mark[x][y][tx][ty]=0;//撤销标记
      m[tx][ty]=0;
    }
  }
}
int main()
{
  cin>>n>>k;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }
  m[0][0]=1;
  dfs(0,0,"",1%k);//第一步也要处理
  if(ans=="")cout<<"-1";
  else cout<<ans;
  return 0;
}

拔河

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

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