十五届蓝桥杯赛题-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;
}