握手问题
很简单,相互牵手即可,但是要注意,第一个人只能与其他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 longusing 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;}