这周搜索类题目做的比较多

keywords{搜索,递归,剪枝,筛选,排序,去重unique,二分查找lower_bound upper_bound };

No:1 带分数

很常规的搜索题,搜索范围$9!$,第一时间想到用next_permutation将所1-9进行全排列,然后进行分割筛选,因为N最大是$1000^2$,所以整数部分最大也就六位,分母分子至少1位,分割规律也就出来了。其中筛选条件应该满足整数部分小于N,小数部分大于1,且值为整

#include <bits/stdcpp.h>
using namespace std;
int n,cnt=0;
int lis[10]= {0};
bool vis[10]= {0};
void check() {
	int inte=0,num=0,deno=0;
	for (int i=0; i<=6; i++) {
		inte=inte*10+lis[i];
		if (inte>=n) {
			break;
		}
		num=0;
		for (int j=i+1; j<=7; j++) {
			num=num*10+lis[j];
			deno=0;
			int k=j+1;
			for (; k<=8; k++) {
				deno=deno*10+lis[k];
				if (deno>num) {
					break;
				}
			}
			if(k>=8) {
				if(n==inte+num/deno&&num%deno==0) {
					cnt++;
				}
			}
		}
	}
}
void dfs(int depth) {
	if(depth==9) {
		check();
		return;
	}
	for(int i=1; i<10; i++) {
		if(vis[i]==0) {
			vis[i]=true;
			lis[depth]=i;
			dfs(depth+1);
			vis[i]=false;
		}
	}
}

int main(int argc, char** argv) {
	cin>>n;
	dfs(0);
	cout<<cnt;
	return 0;
}

No:2 排列数

dfs部分的代码和第一题类似,将0-9全排列的同时并计数,符合条件输出当前排列。

#include <bits/stdcpp.h>
using namespace std;
int n,cnt=0,lis[11]= {0};
bool vis[11]= {0};
void dfs(int depth) {
	if(depth>=10) {
		cnt++;
		if(cnt==n) {
			for(int i=0; i<10; i++) {
				cout<<lis[i];
			}
		}
		return;
	}
	for(int i=0; i<=9; i++) {
		if(vis[i]==0) {
			vis[i]=true;
			lis[depth]=i;
			dfs(depth+1);
			vis[i]=false;
		}
	}
}
int main(int argc, char** argv) {
	cin>>n;
	dfs(0);
}

No:3 错误票据

检测EOF作为数据输入是否结束,使用vector进行排序,遍历就可以了

#include <bits/stdcpp.h>
using namespace std;

int main(int argc, char** argv) {
	int n;
	cin>>n;
	vector<int> lis;
	int input,a,b;
	while(cin>>input&&input!=EOF) {
		lis.push_back(input);
	}
	sort(lis.begin(),lis.end());
	for(vector<int>::iterator i=lis.begin(); i<lis.end()-1; i++) {
		if(*(i+1)-*i==0) {
			a=*i;
		} else if(*(i+1)-*i==2) {
			b=*i+1;
		}
	}
	cout<<b<<" "<<a;
	return 0;
}

No:4 剪邮票

剪邮票
有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)

请你计算,一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

dfs搜索五个点,然后dfs判断是否满足要求

#include <bits/stdcpp.h>
using namespace std;
const int r = 3, c = 4;
bool vis[3][4]= {false};
int cnt;
int dir[4][2] = {
	{0, 1},
	{1, 0},
	{0, -1 },
	{ -1, 0},
};//四种状态

bool check(int x, int y) {
	if (x < 0 || x >= r || y < 0 || y >= c || vis[x][y]) {
		return false;
	}
	return true;
}

void dfs(int x, int y, int n) {
	if (n == 5) {
		cnt++;
		return ;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (check(nx, ny)) {
			vis[nx][ny] = true;
			dfs(nx, ny, n + 1);
			vis[nx][ny] = false;
		}
	}
}

int main(int argc, char** argv) {

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			vis[i][j] = true;
			dfs(i, j, 1);
			vis[i][j] = false;
		}
	}
	cout << cnt/5;
	return 0;
}

No:5 机器人繁殖

X星系的机器人可以自动复制自己。它们用1年的时间可以复制出2个自己,然后就失去复制能力。
每年X星系都会选出1个新出生的机器人发往太空。也就是说,如果X星系原有机器人5个,
1年后总数是:5 + 9 = 14
2年后总数是:5 + 9 + 17 = 31

如果已经探测经过n年后的机器人总数s,你能算出最初有多少机器人吗?

数据格式:

输入一行两个数字n和s,用空格分开,含义如上。n不大于100,s位数不超过50位。

要求输出一行,一个整数,表示最初有机器人多少个。

例如:
用户输入:
2 31

则程序应该输出:
5

再例如:
用户输入:
97 2218388550399401452619230609499

则程序应该输出:
8 

#include <bits/stdcpp.h>
using namespace std;

int main(int argc, char** argv) {
	int n, s,cnt;
	vector<int> lis;
	cin >> n >> s;
	for (int i=1; ; i++) {//从1个机器人逐步递增计算
		cnt = i;
		lis.push_back(i);
		for (int j = 1; j <= n; j++) {
			cnt += lis[lis.size() - 1] * 2 - 1;
			lis.push_back(lis[lis.size() - 1] * 2 - 1);
		}
		if(cnt == s) {
			cout << i;
			return 0;
		}
	}
}

No:6 递增三元组

给定三个整数数组
A = [A1, A2, ... AN], 
B = [B1, B2, ... BN], 
C = [C1, C2, ... CN],
请你统计有多少个三元组(i, j, k) 满足:
1. 1 <= i, j, k <= N  
2. Ai < Bj < Ck  

【输入格式】 
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
第三行包含N个整数B1, B2, ... BN。
第四行包含N个整数C1, C2, ... CN。

对于30%的数据,1 <= N <= 100  
对于60%的数据,1 <= N <= 1000 
对于100%的数据,1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000 

【输出格式】
一个整数表示答案
【样例输入】
3
1 1 1
2 2 2
3 3 3

【样例输出】

27 

【样例输入】

3
1 2 3
2 3 5
3 4 5
【样例输出】
7

使用lower_bound()找到a中有多少个小于b的,b中有多少个小于c的,lower_bound()二分查找并返回第一个大于等于key的值位置,令其减去起始位置就能得到数量,将乘积累加即可

#include <bits/stdcpp.h>
using namespace std;
int a[100002],b[100002],c[100002];
int main(int argc, char** argv) {
	int n,cnt=0;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>a[i];
	};
	for(int i=0; i<n; i++) {
		cin>>b[i];
	}
	for(int i=0; i<n; i++) {
		cin>>c[i];
	}
	sort(a,a+n);
	sort(b,b+n);
	sort(c,c+n);
	for(int i=0; i<n; i++) {
		int k1 = (lower_bound(a,a+n,b[i]) - a);
		int k2 = (lower_bound(b,b+n,c[i]) - b);
		cnt += k1*k2;
	}
	cout<<cnt;
	return 0;
}

No:7 第几个幸运数

到x星球旅行的游客都被发给一个整数,作为游客编号。 
x星的国王有个怪癖,他只喜欢数字3,5和7。 
国王规定,游客的编号如果只含有因子:3,5,7,就可以获得一份奖品。

我们来看前10个幸运数字是: 
3 5 7 9 15 21 25 27 35 45 
因而第11个幸运数字是:49

小明领到了一个幸运数字 59084709587505,他去领奖的时候,人家要求他准确地说出这是第几个幸运数字,否则领不到奖品。
请你帮小明计算一下,59084709587505是第几个幸运数字。
需要提交的是一个整数,请不要填写任何多余内容。
#include <bits/stdcpp.h>
using namespace std;
int dir[3]= {3,5,7};
long long lucky=59084709587505;
set<long long> lis;//利用set去重,用vector的话需要先排序后用unique去重。
int main(int argc, char** argv) {
	long long tem=1;
	while(true) {
		for(int i=0; i<3; i++) {
			if(tem*dir[i]<=lucky) {
				lis.insert(tem*dir[i]);
			}
		}
		tem=*lis.upper_bound(tem);//返回最后一个大于tem的数
		cout<<tem<<" " ;
		if(tem==lucky) {
			break;
		}
	}
	cout<<lis.size();
	return 0;
}

No:8 连号区间

序列max-min =lenth时即可认为连号,单独一个数字也可以认为连号

#include <bits/stdcpp.h>
using namespace std;
int main(int argc, char** argv) {
	int lis[50000];
	int n,cnt=0,left,right;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>lis[i];
	}
	for(int i=0; i<n; i++) {
		cnt ++ ;
		left = right = lis[i] ;
		for( int j = i+1 ; j < n ; j ++ ) {
			left = min( left , lis[j] );
			right= max( right, lis[j] );
			cnt += ( right-left == j-i );
		}
	}
	cout<<cnt;
	return 0;
}

No:9 核桃的数量

关于求最小公倍数的问题,求三个数的最小公倍数,但也不复杂,最开始是想先求两个数的最小公倍数,然后再求其和第三个数的最小公倍数。后来想想直接求三个数的最小公倍数也不复杂,直接取三个数中的最大值,然后如果不能整除其中任意一个数,就递增,直到能同时整除三个数为止。

#include <bits/stdcpp.h>
using namespace std;
int check_lcm(int x,int y,int z) {
	int value;
	value=max(x,max(y,z));
	while((value%x!=0)||(value%y!=0)||(value%z!=0)) {
		value++;
	}
	return value;
}
int main(int argc, char** argv) {
	int a,b,c;
	cin>>a>>b>>c;
	cout<<check_lcm(a,b,c);
	return 0;
}