蓝桥杯搜索练习2
脑洞题：
假设有两种微生物 X 和 YX出生后每隔3分钟分裂一次（数目加倍），Y出生后每隔2分钟分裂一次（数目加倍）。
一个新出生的X，半分钟之后吃掉1个Y，并且，从此开始，每隔1分钟吃1个Y。
现在已知有新出生的 X=10, Y=89，求60分钟后Y的数目。
如果X=10，Y=90 呢？
本题的要求就是写出这两种初始条件下，60分钟后Y的数目。
也许因为你消灭的那只 Y 就是最终导致 Y 种群灭绝的最后一根稻草！
请忍住悲伤，把答案写在“解答.txt”中，不要写在这里！
/*【解题思路】
解法：
根据题目来for循环逻辑运算,且可以把分钟转化为秒来运算，
避免浮点数运算（如半分钟）
其中列表找规律可得出：
可以不用管X是半分钟吃一个Y，还是一分钟吃一个Y，
都可以算成一分钟吃一个Y，
比如一个新出生的X，它在0.5分钟的时候吃了一个Y，
在第1.5分钟吃一个，2.5分钟又吃了一个，
也就是说，三分钟内，X吃了3个Y，且题目要求的是60分钟，能被3整除，
并且因为分裂增倍和这半分钟是没有关系的，所以相当于每个x的都是在
3的整数倍的时候出生，都在3的整数倍+0.5的时候开始吃人，所以也实际
上等价于每个X都在一分钟内吃一个Y，也就是说，所有的X都是xx.5秒的时候吃Y
可以直接转变为X每分钟吃了1个Y
答案：94371840
*/
#include<iostream>
using namespace std;
int main()
{
int x,y;
x = 10;
y = 90;
for(int i=1;i<=3600;i++)
{
if(y < 0)
{
y=0;
break;
}
if(i % 60 == 0)
{
y -= x;
}
if(i % 120 == 0)
{
y *= 2;
}
if(i % 180 == 0)
{
x *= 2;
}
}
cout<<"当X=10，Y=90时,60分钟后Y的数目为："<<y<<endl;
return 0;
} 福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式：
ABCDE * ? = EDCBA
他对华生说：“ABCDE应该代表不同的数字，问号也代表某个数字！”
华生：“我猜也是！”
于是，两人沉默了好久，还是没有算出合适的结果来。
请你利用计算机的优势，找到破解的答案。
把 ABCDE 所代表的数字写出来。
答案写在“解答.txt”中，不要写在这里！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[6];
int vis[11]={0};
int cnt=0;
void dfs(int step){
if(step==5){
if(a[0]!=0&&a[0]!=a[1]&&a[0]!=a[2]&&a[0]!=a[3]&&a[0]!=a[4]
&&a[1]!=a[2]&&a[1]!=a[3]&&a[1]!=a[4]
&&a[2]!=a[3]&&a[2]!=a[4]
&&a[3]!=a[4]){
for(int i=1;i<10;i++){
int num1=a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4];
int num2=a[4]*10000+a[3]*1000+a[2]*100+a[1]*10+a[0];
if(num1*i==num2)cout<<"A:"<<a[0]<<" B:"<<a[1]<<" C:"<<a[2]<<" D:"<<a[3]<<" E:"<<a[4]<<endl;
}
}
}
for(int i=0;i<10;i++){
if(vis[i]==0){
a[step]=i;
vis[i]=1;
dfs(step+1);
vis[i]=0;
}
}
return;
}
int main(){
dfs(0);
return 0;
}某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：
每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；
答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。
每位选手都有一个起步的分数为10分。
某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？
如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。
例如：0010110011 就是可能的情况。
你的任务是算出所有可能情况。每个答案占一行。
答案写在“解答.txt”中，不要写在这里！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[11];
int cnt;
void dfs(int step){
if(step==10){
int sum=10;
for(int i=0;i<10;i++){
if(a[i]==0)sum=sum-(i+1);
else if(a[i]==1)sum*=2;
}
if(sum==100){
for(int i=0;i<10;i++)cout<<a[i];
cout<<endl;
}
return;
}
for(int i=0;i<=1;i++){
a[step]=i;
dfs(step+1);
}
return ;
}
int main(){
dfs(0);
return 0;
}有一群海盗（不多于20人），在船上比拼酒量。过程如下：打开一瓶酒，
所有在场的人平分喝下，有几个人倒下了。再打开一瓶酒平分，
又有倒下的，再次重复...... 直到开了第4瓶酒，坐着的已经所剩无几，
海盗船长也在其中。当第4瓶酒平分喝下后，大家都倒下了。
等船长醒来，发现海盗船搁浅了。他在航海日志中写到：
“......昨天，我正好喝了一瓶.......奉劝大家，开船不喝酒，喝酒别开船......”
请你根据这些信息，推断开始有多少人，每一轮喝下来还剩多少人。
如果有多个可能的答案，请列出所有答案，每个答案占一行。
格式是：人数,人数,...
例如,有一种可能是：20,5,4,2,0
答案写在“解答.txt”中，不要写在这里！
//正确做法,dfs每次喝醉了的人
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[5];//每次喝醉了的
int vis[21]={0};
int initnum;
void dfs(int step,int left){
if(step==4){
if(a[0]+a[1]+a[2]+a[3]==initnum){
if((1.0/initnum+1.0/(initnum-a[0])+1.0/(initnum-a[0]-a[1])+1.0/(initnum-a[0]-a[1]-a[2]))==1.0){
cout<<initnum<<","<<initnum-a[0]<<","<<initnum-a[0]-a[1]<<","<<initnum-a[0]-a[1]-a[2]<<",0"<<endl;
}
}
return;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=left;i++){
if(vis[i]==0){
vis[i]=1;
a[step]=i;
dfs(step+1,left-a[step]);
vis[i]=0;
}
}
return;
}
int main(){
memset(vis,0,sizeof(vis));
for(int i=20;i>=4;i--){
initnum=i;
dfs(0,i);
}
return 0;
}//Bug做法，dfs每次还醒着的人
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[21];
int vis[21]={0};
int cnt;
void dfs(int step,int left){
if(step==4){
if(a[0]>a[1]&&a[1]>a[2]&&a[2]>a[3]){
if((a[1]*100+a[2]*10+a[3])
+(a[0]*100+a[2]*10+a[3])
+(a[0]*100+a[1]*10+a[3])
+(a[0]*100+a[1]*10+a[2])
==(a[0]*1000+a[1]*100+a[2]*10+a[3])){
cout<<a[0]<<","<<a[1]<<","<<a[2]<<","<<a[3]<<",0"<<endl;
}
}
return;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=left;i++){
if(vis[i]==0){
vis[i]=1;
a[step]=i;
dfs(step+1,left-a[step]);
vis[i]=0;
}
}
return;
}
int main(){
memset(vis,0,sizeof(vis));
for(int i=20;i>=4;i--){
dfs(0,i);
}
return 0;
}Catalan数：
出栈次序
X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，
按照编号先后发车，夹在其它车流中，缓缓前行。
路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。
X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，
可能的次序有多少种？
为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。
现在足足有16辆车啊，亲！需要你计算出可能次序的数目。
这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）。
【解题思路】
解法一：
我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：
f(1) = 1 //即 1
f(2) = 2 //即 12、21
f(3) = 5 //即 123、132、213、321、231
然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑：
元素a只可能出现在1号位置，2号位置，3号位置和4号位置(很容易理解，一共就4个位置，
比如abcd,元素a就在1号位置)。
分析：
1) 如果元素a在1号位置，那么只可能a进栈，马上出栈，此时还剩元素b、c、d等待操作，
就是子问题f(3)；
2) 如果元素a在2号位置，那么一定有一个元素比a先出栈，即有f(1)种可能顺序（只能是b），
还剩c、d，即f(2)， 根据乘法原理，一共的顺序个数为f(1) * f(2)；
3) 如果元素a在3号位置，那么一定有两个元素比1先出栈，即有f(2)种可能顺序（只能是b、c），还剩d，即f(1)，
根据乘法原理，一共的顺序个数为f(2) * f(1)；
4) 如果元素a在4号位置，那么一定是a先进栈，最后出栈，
那么元素b、c、d的出栈顺序即是此小问题的解，即f(3)；
结合所有情况，即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);
为了规整化，我们定义f(0) = 1；于是f(4)可以重新写为：
f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)
然后我们推广到n，推广思路和n=4时完全一样，于是我们可以得到：
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)
解法二：
排列公式：C(n,2n)/(n+1) 【其中C(n,2n)表示2n里取n）】
或者C(2n,2n)-C(n-1,2n)
答案：35357670
#include<iostream>
using namespace std;
#define MAX 16+1
int main()
{
int temp;
int a[MAX] = {0};
a[0] = a[1] = 1;
for(int i=2;i < MAX;i++)
{
int j = i;
int sum = 0;
int k = 1;
do
{
sum += a[i-j]*a[i-k];
k++;
}while(--j);
a[i] = sum;
cout<<"f("<<i<<")"<<" = "<<a[i]<<endl;
}
return 0;
} 神奇6位数
有一个6位的正整数，它有个很神奇的性质：
分别用2 3 4 5 6去乘它，得到的仍然是6位数，
并且乘积中所包含的数字与这个6位数完全一样！
只不过是它们的顺序重新排列了而已。
请计算出这个6位数。
这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性的文字）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int vis1[11]={0};
int vis2[11]={0};
void momo(int x){
while(x)
{
vis1[x%10]++;
x/= 10;
}
return;
}
bool checkout(int x){
while(x)
{
vis2[x%10]++;
x/= 10;
}
for(int i=0;i<10;i++){
if(vis1[i]!=vis2[i]){
return false;
}
}
return true;
}
int main(){
for(int i=100000;i<200000;i++){
memset(vis1,0,sizeof(vis1));
momo(i);
bool flag=1;
for(int j=2;j<=6;j++){
memset(vis2,0,sizeof(vis2));
if(!checkout(j*i)){
flag=0;
break;
}
}
if(flag==true)
{
cout<<i<<endl;
break;
}
}
return 0;
} 六角幻方
把 1 2 3 ... 19 共19个整数排列成六角形状，如下：
* * *
* * * *
* * * * *
* * * *
* * *
要求每个直线上的数字之和必须相等。共有15条直线哦！
再给点线索吧！我们预先填好了2个数字，第一行的头两个数字是：15 13，
参见图【p1.png】，黄色一行为所求。
请你填写出中间一行的5个数字。数字间用空格分开。
这是一行用空格分开的整数，请通过浏览器提交答案，
不要填写任何多余的内容（比如说明性的文字等）
#include<iostream>
using namespace std;
bool vis[19] = {0};
int a[17] = {0};
void dfs(int step)
{
if(step == 5)
{
if(15+13+a[0] != a[1]+a[2]+a[3]+a[4])
return;
}
if(step == 6)
{
if(15+13+a[0] != 15+a[1]+a[5])
return;
}
if(step == 10)
{
if(15+13+a[0] != a[5]+a[6]+a[7]+a[8]+a[9])
return;
else if(15+13+a[0] != a[0]+a[4]+a[9])
return;
}
if(step == 11)
{
if(15+13+a[0] != 13+a[2]+a[6]+a[10])
return;
}
if(step == 14)
{
if(15+13+a[0] != a[10]+a[11]+a[12]+a[13])
return;
else if(15+13+a[0] != 13+a[3]+a[8]+a[13])
return;
}
if(step == 15)
{
if(15+13+a[0] != a[5]+a[10]+a[14])
return;
else if(15+13+a[0] != a[0]+a[3]+a[7]+a[11]+a[14])
return;
}
if(step == 16)
{
if(15+13+a[0] != a[1]+a[6]+a[11]+a[15])
return;
else if(15+13+a[0] != a[4]+a[8]+a[12]+a[15])
return;
}
if(step == 17)
{
if(15+13+a[0] != a[14]+a[15]+a[16])
return;
else if(15+13+a[0] != 15+a[2]+a[7]+a[12]+a[16])
return;
else if(15+13+a[0] != a[9]+a[13]+a[16])
return;
else
{
for(int i=5;i<10;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}
else
{
for(int i=0;i<19;i++)
{
if(!vis[i])
{
a[step] = i+1;
vis[i] = true;
dfs(step+1);
vis[i] = false;
}
}
}
}
int main()
{
vis[12] = vis[14] = true;
dfs(0);
return 0;
} 
顺丰集团工作强度 113人发布
