2016年蓝桥杯B组C/C++决赛题解

2016年第七届蓝桥杯B组C/C++决赛题解

2016年蓝桥杯B组C/C++决赛题目(不含答案)

1.一步之遥

枚举解方程，或者套模板解线性方程

#include<bits/stdc++.h>

using namespace std;

int main(){

	int ans = 0x3f3f3f3f;

	for(int a=0;a<=100;a++){

		for(int b=0;b<=100;b++){

			if(97*a - 127*b == 1){

				ans = min(ans,a+b);

			}

		}

	}

	cout<<ans<<endl;

	return 0;

}

//97

2.凑平方数

思路：

分成几组? k组 1 ~ 10;

每组:dfs搜索0~9这几个没用过的数;

if 完全平方数

1.x+1

2.继续加值 (0不能作为第一个数单独考虑)

到了k组先对结果排序存到vector数组中再set去重(因为递归回溯结果有大量重复)

注意：必须用long long...用int会出错因为int的取值范围为：-2147483648 ~ 2147483647

网上有全排列后再dfs的方法，这样不用再回溯打乱顺序，博客地址：https://blog.csdn.net/riba2534/article/details/72480145

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int vis[15];

ll a[15];

vector<ll> v;

int vis2[10];

int k;

int ans = 0;

set<vector<ll> > se;

inline bool check(ll x){

	if(x == 9814072356){

		int eeeeee = 1;

	}

	double d = sqrt(x);

	return d == (ll)d;

}

//因为递归回溯有大量重复  改成set去重

void dfs(int x,ll cur){

	if(x == k){

		for(int i=0;i<10;i++){

			vis2[i] = 0;

		}

		for(int i=0;i<k;i++){

			ll d = a[i];

			if(d == 0) vis2[d] = 1;

			else{

				while(d){

					vis2[d%10] = 1;

					d = d/10;

				}

			}

		}

		for(int i=0;i<=9;i++){

			if(!vis2[i]) return;

		}

		for(int i=0;i<k;i++) v.push_back(a[i]);

		sort(v.begin(),v.end());

		if(se.find(v) == se.end()){

			for(int i=0;i<k;i++) cout<<v[i]<<" ";

			cout<<endl;

			se.insert(v);

		}

		v.clear();

		ans++;

		return;

	}

	for(int i=0;i<=9;i++){

		if(!vis[i]){

			vis[i] = 1;

			if(cur == 0 && i == 0){//如果是以0开头 并且当前搜索的是一个新的分组(cur值为0) 就直接搜索下一组

				a[x] = 0;

				dfs(x+1,0);

				vis[i] = 0;

				continue;

			}

			ll num = cur*10+i;

			if(check(num)){

				a[x] = num;

				dfs(x+1,0);

			} //搜索下一分组

			dfs(x,cur*10+i);//继续搜索当前分组

			vis[i] = 0;

		}

	}

}

int main(){

	//freopen("out1.txt","w",stdout);

	//枚举分组的次数

	for(k = 1;k <= 10;k++){

		memset(vis,0,sizeof(vis));

		dfs(0,0);

	}

	cout<<ans<<endl;

	cout<<se.size()<<endl;

	return 0;

}

//3085

//300

3.棋子换位

输出结果

手算

判断两者不同点

尝试给出答案。。就这样做

思路：交换的两边不一样，才能跳

答案：valid(data, i+dd+dd) &&valid(data, i-dd) && data[i-dd] == data[i+dd+dd]

4.机器人塔

直接dfs搜索了，初步估计能过30%数据

思路:dfs搜索

首先理解题意:搭人梯总人数肯定是按1 + 2 + 3 + 4 +.....+n 这种数据类型来给的题目写了保证数据合理。

我们可以提前预处理给定的人数应该搭人梯共几层比如样例：1 2 就是2层样例：3 3就是3层满足等差数列 1 + 2 + 3,我们根据等差数列性质求出下面代码的belong数组有sum个人时对应的层数

belong[a+b] 算出等于共k层，当然用等差数列公式开方也直接能算的，不用再预处理了。。。。。。

用等差数列公式开方，上面过程可以不看

主要是dfs：

随后 dfs搜索每一层:dfs(int x,int cur,int numa,int numb) 参数含义:第x层当前层的第cur个位置使用a的数量numa 使用b的数量numb

按题目条件dfs填充a[x][cur]就可以了

剪枝后也只能过小数据

#include<bits/stdc++.h>

using namespace std;

const int maxn = 510;

int belong[maxn*maxn];

int a[maxn][maxn];

int n,m;

int ans = 0;

int k;

void dfs(int x,int cur,int numa,int numb){

	if(x == k){ //出口:最后一层只能放置一个 容易判断

		if(numa == n-1 && numb == m){

			if((a[x-1][1] == 1 && a[x-1][2] == 1) || (a[x-1][1] == 2 && a[x-1][2] == 2)){

				ans++;

			}

		}

		if(numb == m-1 && numa == n){

			if((a[x-1][1] == 1 && a[x-1][2] == 2) || (a[x-1][1] == 2 && a[x-1][2] == 1)){

				ans++;

			}

		}

		return;

	}

	int idx = k-x+1;

	if(x == 1){//第一层可以随意放

		for(int i=cur;i<idx;i++){ //每一层可以放idx个

			if(numa + 1 <= n){

				a[x][i] = 1;

				dfs(x,cur+1,numa+1,numb);

				a[x][i] = 0;

			}

			if(numb + 1 <= m){

				a[x][i] = 2;

				dfs(x,cur+1,numa,numb+1);

				a[x][i] = 0;

			}

		}

		if(cur == idx){

			if(numa + 1 <= n){

				a[x][cur] = 1;

				dfs(x+1,1,numa+1,numb);

				a[x][cur] = 0;

			}

			if(numb + 1 <= m){

				a[x][cur] = 2;

				dfs(x+1,1,numa,numb+1);

				a[x][cur] = 0;

			}

		}

	}else{ //非第一层 受题目条件限制放置

		for(int i=cur;i<idx;i++){ //每一层可以放idx个

			if((a[x-1][i] == 1 && a[x-1][i+1] == 1) || (a[x-1][i] == 2 && a[x-1][i+1] == 2)){

				if(numa + 1 <= n){

					a[x][i] = 1;

					dfs(x,cur+1,numa+1,numb);

					a[x][i] = 0;

				}

			}

			if((a[x-1][i] == 1 && a[x-1][i+1] == 2) || (a[x-1][i] == 2 && a[x-1][i+1] == 1) ){

				if(numb + 1 <= m){

					a[x][i] = 2;

					dfs(x,cur+1,numa,numb+1);

					a[x][i] = 0;

				}

			}

		}

		if(cur == idx){

			if((a[x-1][cur] == 1 && a[x-1][cur+1] == 1) || (a[x-1][cur] == 2 && a[x-1][cur+1] == 2)){

				if(numa + 1 <= n){

					a[x][cur] = 1;

					dfs(x+1,1,numa+1,numb);

					a[x][cur] = 0;

				}

			}

			if((a[x-1][cur] == 1 && a[x-1][cur+1] == 2) || (a[x-1][cur] == 2 && a[x-1][cur+1] == 1) ){

				if(numb + 1 <= m){

					a[x][cur] = 2;

					dfs(x+1,1,numa,numb+1);

					a[x][cur] = 0;

				}

			}

		}

	}

}

void init(){

	for(int i=1;i<=200;i++){

		int sum = 0;

		for(int j=1;j<=i;j++){

			sum += j;

		}

		belong[sum] = i;

	}

}

int main(){

	init();

	cin>>n>>m;

	k = belong[n+m];

	dfs(1,1,0,0);

	cout<<ans<<endl;

	return 0;

}

5.广场舞

想到思路了，但是做起来还是挺麻烦的，不写了

提供几条资料

百度：计算几何判断点与多边形的关系

这题题解博客(不保证准确性但是博主写的很详细能看懂得) https://blog.csdn.net/codeswarrior/article/details/80397275

6.生成树计数

不写了

巴特西