文章目录

A组

高斯日记
排他平方书
振兴中华
颠倒的价牌
前缀判断
逆波兰表达式
错误票据
买不到的数目
剪格子
大臣的旅费

由于没有OJ，不敢保证100%正确，但是自己测试都通过了的

A组

高斯日记

直接excel算，因为题目是1777年4月30日，excel算不了那么早，所以我们把它加1000年再算最后减1000年即可

排他平方书

蓝桥杯第四届省赛C/C++A组个人题解
两种做法

用for遍历所有6位数，然后检查一下即可
用dfs填6位数，然后检查
上述两种方法都可以大同小异。
需要注意的是直接用int型会溢出，所以要用long long来乘
答案639172
for循环版

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
//判断原始数字是否重复
bool judge(LL num)
{
	int flag[10];
	memset(flag,0,sizeof(int)*10);
	while(num)
	{
		if(flag[num%10]==1)return false;
		flag[num%10]++;
		num/=10;
	}
	return true;
}
//检查新数字
void check(LL num)
{
	int flag[10]={0};
	memset(flag,0,sizeof(int)*10);
	LL tmp=num;
	while(tmp)
	{
		flag[tmp%10]=1;
		tmp/=10;
	}
	LL tnum=num*num;
	while(tnum)
	{
		//ÓÐÖØ¸´ 
		if(flag[tnum%10]==1) return;
		tnum/=10;
	}
	cout<<num<<endl;
}


int main()
{
	for(int i=100000;i<=999999;i++)
	{
		if(judge(i))check(i);
	} 
}

dfs版部分代码其余部分差不多（其实这题直接用for写最方便，bfs可以保证每次传进去判断的数都不会重复，比循环快一些)

void dfs(int cur)
{
	if(cur==6)
	{
		//这里存放数字的是数组ary,check函数里面稍微改写一下即可，即把数组取出来，然后判断
		if(check())
		{
			for(int i=0;i<6;i++)cout<<ary[i];
			ans++;
			cout<<endl;
		} 
		return;	
	}
	for(int i=0;i<10;i++)
	{
		if(flag[i]==0)
		{
			flag[i]=1;
			ary[cur]=i;
			dfs(cur+1);
			flag[i]=0;
		}
	}
	return;
}
int main()
{
	dfs(0);
}

振兴中华

蓝桥杯第四届省赛C/C++A组个人题解
一道很好的dfs题目，建议自己实现！

#include<bits/stdc++.h>
using namespace std;
//下 右 
int dx[]={0,1};
int dy[]={1,0};
int ary[][5]=
{
	{0,1,2,3,4},
	{1,2,3,4,5},
	{2,3,4,5,6},
	{3,4,5,6,7},
};
int ans=0;
void dfs(int cur,int val,int x,int y)
{
	if(cur==7)
	{
		ans++;
		return;
	}
	for(int i=0;i<2;i++)
	{
		int cy=y+dy[i];
		int cx=x+dx[i];
		if(cy>4||cx>3)continue;
		if(ary[cx][cy]==val+1)
		{
			dfs(cur+1,val+1,cx,cy);
		}
	}
	return;
}
int main()
{
	dfs(0,0,0,0);
	cout<<ans;
}

颠倒的价牌

蓝桥杯第四届省赛C/C++A组个人题解
这道注意看题目，是利润差是558而不是颠倒后的价牌相差558.如果看错题目了，你会得到很多个答案。

只有6 和 9会倒过来
我们先用bfs跑一遍，把符合条件的两个数字分别存放再不同数组中，然后做差即可

#include<bits/stdc++.h>
using namespace std;
int st[10]={0,1,2,3,4,5,9,7,8,6};
int x[4]={0};
int aryX[10000]={0};
int aryY[10000]={0};
void check()
{
	int x1[4]={0};
	for(int i=3;i>=0;i--)
	{
		//不能倒转 
		if(x[i]==3||x[i]==4||x[i]==7)return; 
		x1[3-i]=st[x[i]];
	}
	int tx=0,rx=0;
	for(int i=0;i<4;i++)
	{
		rx=rx*10+x[i]; 
		tx=tx*10+x1[i]; 
	}
	
	if(rx-tx>200&&rx-tx<300)
	{
		aryX[rx]=tx;
	}	
	if(tx-rx>800&&tx-rx<900)
	{
		aryY[rx]=tx;
	}

}
void dfs(int cur)
{
	if(cur==4)
	{
		if(x[3]==0)return;
		check();
		return;
	}
	for(int i=0;i<=9;i++)
	{
		x[cur]=i;
		dfs(cur+1);
	}

	return;
}
int main()
{
	dfs(0);
	for(int i=1000;i<10000;i++)
	{
		if(aryX[i]!=0)
		for(int j=1000;j<10000;j++)
		{
			if(aryY[j]!=0) 
			//是利润相差588 而不是颠倒的价格相差588！
			if(abs((i-aryX[i])-(aryY[j]-j))==558) 
			{
				cout<<i<<endl;
			}
		}
	}
}

前缀判断

char* prefix(char* haystack_start, char* needle_start)
{
	char* haystack = haystack_start;
	char* needle = needle_start;

	
	while(*haystack && *needle){
		if((*haystack++)!=(*needle++)) return NULL;  //填空位置
	}
	
	if(*needle) return NULL;
	
	return haystack_start;
}

逆波兰表达式

https://blog.****.net/ryo_218/article/details/79719396贴一个别人的讲解答案evaluate(x+1+v1.n)

错误票据

题目有点长不写了
这道题看数据量100个不大于100000的正整数，这是不会超时的，放心的暴力吧

用getline和stringstream读入多个数据，这个技巧很好，详情请看代码
排序一下数据,用一个标记数组标记数据
再遍历标记数组，找符合条件的数

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N;
	cin>>N;
	vector<int>vt;
	for(int i=0;i<=N;i++)
	{
		string str;
		getline(cin,str);
		stringstream ss;
		ss<<str;
		int j;
		while(ss>>j)vt.push_back(j);
	}
	sort(vt.begin(),vt.end());
	const int max=vt[vt.size()-1];
	int flag[max+1];
	memset(flag,0,sizeof(int)*(max+1));
	for(int i=0;i<vt.size();i++)
	{
		flag[vt[i]]++;
	}
	int A=0,B=0;
	for(int i=vt[0];i<=max;i++)
	{
		if(flag[i]==0) A=i;
		if(flag[i]>1) B=i;
	}
	cout<<A<<" "<<B;
}

买不到的数目

蓝桥杯第四届省赛C/C++A组个人题解
这道题我用的暴力，似乎可以推导出来请看别人的分析 https://blog.****.net/bear_huangzhen/article/details/78496671
暴力法

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int flag[maxn]={0};
int main()
{
	int n,m;
	cin>>n>>m; 
	if(m>n)swap(n,m);
	int max=0;
//	求最大不能组合出的数字。
 	for(int i=0;i<maxn;i+=n)
	{

		for(int j=0;j<maxn;j+=m)
		{
			if(i+j>maxn)break;
			flag[i+j]=1;

		}
	} 

	for(int i=0;i<maxn;i++)
	{
		if(flag[i]==0)
		{
			max=i;
		}
	}
	cout<<max;
}

剪格子

蓝桥杯第四届省赛C/C++A组个人题解
P.S这道题争议很大，我只贴我的代码，具体可以看别人的分析
1.bfs从左上角搜索，找出最小的答案

#include<bits/stdc++.h>
using namespace std;
//右下左上 
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
//n行 m列 
int m,n;
int sum=0;
int ary[10][10];
int flag[10][10];
int minn=1000;
bool judge(int x,int y)
{
	if(x>=n||y>=m||x<0||y<0)return false;
	return true;
}
void dfs(int cur,int x,int y,int now)
{
	if(cur==sum/2)
	{
		if(now<minn)minn=now;
		return;
	}
	if(cur>sum/2)return;
	for(int i=0;i<4;i++)
	{
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(judge(tx,ty)&&flag[tx][ty]!=1)
		{
			flag[tx][ty]=1;
			dfs(cur+ary[tx][ty],tx,ty,now+1);
			flag[tx][ty]=0;
		}
	}
	return;
}
int main()
{
	cin>>m>>n;

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>ary[i][j];
			sum+=ary[i][j];
			flag[i][j]=0;
		}
	}
	dfs(ary[0][0],0,0,1);
	cout<<minn;
}

大臣的旅费

困扰了我很久的题目，不知道如何下手。。
http://blog.sina.com.cn/s/blog_14d68bd870102wd54.html

蓝桥杯第四届省赛C/C++A组个人题解