赛前第二周 真题训练

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

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

No:1 带分数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.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全排列的同时并计数,符合条件输出当前排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.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进行排序,遍历就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.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 剪邮票

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.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 机器人繁殖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.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 递增三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
给定三个整数数组
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的值位置,令其减去起始位置就能得到数量,将乘积累加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.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 第几个幸运数

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

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

小明领到了一个幸运数字 59084709587505,他去领奖的时候,人家要求他准确地说出这是第几个幸运数字,否则领不到奖品。
请你帮小明计算一下,59084709587505是第几个幸运数字。
需要提交的是一个整数,请不要填写任何多余内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.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时即可认为连号,单独一个数字也可以认为连号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.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 核桃的数量

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.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;
}

Author: Junzhou Liu
Link: https://liujunzhou.top/2019/3/5/week2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
AliPay
WechatPay