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.生成树计数
不写了