2020牛客寒假算法基础集训营3 (A、C、D、F、H、I)_2022牛客寒假算法基础集训营3

题目链接

A - 牛牛的DRB迷宫I

题意: 一个人走迷宫有三种走法，该点为 ‘R’ 就只能向右走， 为 'D’就只能向下走，为’B’向下向右都可以。需要求从左上角 (1,1) 到 右下角 (n,m) 有多少种走法。

想法: 起点路线数初始化为1，其余点初始化为0，然后遍历询问当前点的上面和左边是否可以走到当前点，如果可以就加到当前点的路线数上一直更新到终点输出即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int ok[55][55], m, n;
char a[55][55];

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n; i++) {
		for(int j = 1;j <= m; j++) {
			scanf(" %c", &a[i][j]);
		}
	}
	
	ok[1][1] = 1;
	for(int i = 1;i <= n; i++) {
		for(int j = 1;j <= m; j++) {
			if(a[i-1][j] == 'B' || a[i-1][j] == 'D') ok[i][j] = (ok[i][j]+ok[i-1][j])%mod ;
			if(a[i][j-1] == 'B' || a[i][j-1] == 'R') ok[i][j] = (ok[i][j] + ok[i][j-1])%mod ;
		}
	}
	printf("%d\n", ok[n][m]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

C - 牛牛的数组越位

题意: 一个人喜欢瞎搞数组下标，但是有些看似不合法的输入却是合法的, 如题中给出的: 数组a[5] [5]中 a[-1] [8] 与a[1] [-2] 其实都是代表的a[0] [3]。这里遵循一个规则: 对于数组a[n] [m]中查找a[x] [y] 的位置其实是 a的首地址+m*x+y。 然后题目要你验证这个人输入的是否合法或者是否有风险。

想法: 这个题目直接用二维数组还不好开，因为n和m的范围给的是一个乘积，所以可以用一位数组模拟二维的。这个题目思路没什么难点，就是输出格式需要注意一下，我在比赛时卡在了这个样例

1
5 1 5
0 0 1
1 0 2
2 0 3
3 0 4
4 0 5
1
2
3
4
5
6
7

我错误的代码会输出这样的:

1
 2
 3
 4
 5
Accepted
1
2
3
4
5
6

就是没有考虑清楚换行时候的条件，以为数组下标 i % m == 1的时候就证明这个数是新的一行的第一个数，否则就是后面的，我第一个数输出前不带空格，后面的带空格，就会导致有上面的本来是第一个数但是跳到了else里面会多输出一个空格。一维数组模拟二维题面都已经给出了，就不说了。

代码如下:

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

int a[20000007];
int T, n, m, p, x, y, val;

int main() {
	scanf("%d", &T);
	while(T--) {
		int ok = 1;
		for(int i = 0;i < n*m; i++) a[i] = 0;
		scanf("%d %d %d", &n, &m, &p);
		
		while(p--) {
			scanf("%d %d %d", &x, &y, &val);
			if(ok == -1) continue;
			if(x < 0 || y < 0 || x >= n || y >= m) ok = 0;
			int k = x*m+y;
			if(k < 0 || k >= m*n) {ok = -1; continue;}
			a[k] = val;
		}
		
		if(ok == -1) {
			printf("Runtime error");
			if(T >= 1) puts("");
			continue;
		}
		for(int i = 1;i <= n*m; i++) {
			if(i%m == 1 || i == 1 || m == 1) printf("%d", a[i-1]);
			else printf(" %d", a[i-1]);
			if(i%m == 0) puts("");
		}
		if(ok == 1) printf("Accepted");
		if(ok == 0) printf("Undefined Behaviour");
		if(T >= 1) puts("");
	}
}
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

D - 牛牛与二叉树的数组存储

题意：讲了一下二叉树长什么样子，满的和不满的用数组表示的方法，当前点的父亲下标是该点的下标/2，左儿子为该点下标 * 2，右儿子为该点下标 * 2+1 然后要你利用给出的数组来判断这棵树的节点个数，根结点，然后按照节点值由小到大的顺序给出每个节点的父亲，左儿子，右儿子分别是谁，并且题目保证这些数字都是连续的。

想法: 开两个map，一个存节点的父亲，一个存节点的两个儿子，顺序输出即可。

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

const int N = 100005;
int a[4*N], n;
map<int, int> fa;
map<int, pair<int, int> > son;

int main() {
	scanf("%d", &n);
	int num = 0, head = 0;
	for(int i = 0;i <= 4*n; i++) a[i] = -1;
	for(int i = 1;i <= n; i++) {
		scanf("%d", &a[i]);
		if(a[i] != -1) {
			if(!head) head = a[i];
			num++;
		} 
	}
	
	for(int i = 1;i <= n; i++) {
		if(a[i] != -1) {
			fa[a[i]] = a[i/2];
			son[a[i]] = make_pair(a[i*2], a[i*2+1]);
		}
	}
	
	
	printf("The size of the tree is %d\n", num);
	printf("Node %d is the root node of the tree\n", head);
	
	for(int i = 1;i <= num; i++) {
		printf("The father of node %d is %d, the left child is %d, and the right child is %d\n", i, fa[i], son[i].first, son[i].second);
	}
}
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

F - 牛牛的Link Power I

题意：一个01串，需要求出每个为1节点之间的下标距离之和。

想法: 两个for循环暴力枚举这是我一开始的想法，n = 1e5,O($n^2$)的复杂度肯定过不了。然后就想到后面的数要和前面的每一个数都要减一遍，那么可以用前缀和来节省时间，当前点乘以前面1出现的次数再减去累积的前缀和， 时间复杂度直接变成了O(n)。

代码如下：

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

const int mod = 1e9+7;
int n;
char s[100005];
bool sta;

int main() {
	scanf("%d", &n);
	bool sta = 0;
	long long pre = 0, ans = 0, num = 0;
	for(int i = 1;i <= n; i++) {
		scanf(" %c", &s[i]);
		if(!sta && s[i] == '1') {
			sta = 1;
			pre += i;
			num++;
		}
		else if(sta && s[i] == '1') {
			ans = (ans + (i*num-pre) % mod) % mod;
			pre += i;
			num++;
		}
	}
	printf("%lld\n", ans);
}
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

H - 牛牛的k合因子数

题意：给定1-n的范围，输入k查询这个范围内 "k合因子数"有多少个。 k合因子数指的是一个数的因子中有k个合数，就叫这个数为k合因子数。

想法: 首先预处理1-n之间的所有质数，一来可以验证一个数的因子是否为合数，而来可以直接跳过1-n之间的质数达到剪枝，( O(n) )。 之后循环判断1-n之间每一个数是几合子数，判断是对i 取根号存到数组中，(O(nlogn)) 。总的时间复杂度: O(n+nlogn)。

代码如下:

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

const int M = 100001;
bool isprime[M];
int n, m, k;
int ans[100005];

void solve() {
	for(int i = 2;i <= M; i++) isprime[i] = 1;
	for(int i = 3;i <= M; i++) if(!(i%2)) isprime[i] = 0;
	for(int i = 2;i <= M; i++) {
		if(isprime[i]) {
			for(int j = i*2; j<= M; j += i)
				isprime[j] = 0;
		}
	}
}

int main() {
	solve();
	scanf("%d %d", &n, &m);
	for(int i = 4;i <= n; i++) {
		if(isprime[i]) continue;
		int t = sqrt((double(i)));
		int num = isprime[i]?0:1;
		for(int j = 2;j <= t; j++) {
			if(i%j==0) {
				if(!isprime[j]) num++;
				if(!isprime[i/j] && j != i/j) num++;
			}
		}
		ans[num]++;
//		cout << "i: " << i << " num: " << num << endl;
	}
	
	while(m--) {
		scanf("%d", &k);
		printf("%d\n", ans[k]);
	}
}
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

I - 牛牛的汉诺塔

题意: 求汉诺塔移动时三个点两两移动的次数(即 A->B A->C B->A B->C C->A C->B 的次数)

想法: 打表找规律，直接模拟汉诺塔的话肯定超时。

找规律需要一点时间，不难发现表中的规律分奇偶：

• 当n为奇数时 第1、4、5项与上一行的数相等，第6项等于 上一行的第5项*2+ i/2，第3项等于同行第6项，第2项等于同行第6项 + (i+1)/2。

• 当n为偶数时 第2、3、6项与上一行的数相等，第五项等于上一行的第6项*2， 第1、4项等于同行第5项 + i/2。

打表代码如下:

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

map<string, int> num;
int n, sum;

void Move(int n, char A, char B, char C) {
	string t = "";
	if (n == 1) {
		t += A; t += C;
		num[t]++;
		sum++;
	}
	else {
		Move(n - 1, A, C, B);
		t += A; t += C;
		num[t]++;
		sum++;
		Move(n - 1, B, A, C);
	}
}

void Hanoi(int n) {
	if (n <= 0)
		return;
	Move(n, 'A', 'B', 'C');
}


int main() {
	for(int i = 1;i <= 10; i++) {
		Hanoi(i);
		printf("A->B:%d  ", num["AB"]);
		printf("A->C:%d  ", num["AC"]);
		printf("B->A:%d  ", num["BA"]);
		printf("B->C:%d  ", num["BC"]);
		printf("C->A:%d  ", num["CA"]);
		printf("C->B:%d  ", num["CB"]);
		printf("SUM:%d\n", sum);
		num.clear();
		sum = 0;
	}
}
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

AC代码如下：

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

long long num[62][10];
int n;

int main() {
	num[1][1] = 0; num[1][2] = 1; num[1][3] = 0; num[1][4] = 0; num[1][5] = 0; num[1][6] = 0;
	num[2][1] = 1; num[2][2] = 1; num[2][3] = 0; num[2][4] = 1; num[2][5] = 0; num[2][6] = 0;
	
	scanf("%d", &n);
	for(int i = 3;i <= n; i++) {
		if(i%2) {
			num[i][1] = num[i-1][1];
			num[i][2] = num[i-1][5]*2 + i/2 + (i+1)/2;
			num[i][3] = num[i-1][5]*2 + i/2;
			num[i][4] = num[i-1][4];
			num[i][5] = num[i-1][5];
			num[i][6] = num[i-1][5]*2 + i/2;
		}
		else {
			num[i][1] = num[i-1][6]*2 + i/2;
			num[i][2] = num[i-1][2];
			num[i][3] = num[i-1][3];
			num[i][4] = num[i-1][6]*2 + i/2;
			num[i][5] = num[i-1][6]*2;
			num[i][6] = num[i-1][6];
		}
	}
	long long sum = (long long)(pow(2,n))-1;
	printf("A->B:%lld\n", num[n][1]);
	printf("A->C:%lld\n", num[n][2]);
	printf("B->A:%lld\n", num[n][3]);
	printf("B->C:%lld\n", num[n][4]);
	printf("C->A:%lld\n", num[n][5]);
	printf("C->B:%lld\n", num[n][6]);
	printf("SUM:%lld\n", sum);
}
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