计蒜客蓝桥模拟(5)

  1. 2.素数个数
  2. 3.连连看
  3. 5.末尾零的个数
  4. 6.藏宝图

org,先%为敬,感觉比第一次难度大点,审题老是审不明白就做..耽误好多时间..希望考场能好好读题.
1.矩阵求和

给你一个从 n×n 的矩阵，里面填充 1 到 n×n.例如当 n 等于 3 的时候，填充的矩阵如下。

1
2
3
1 2 3
4 5 6
7 8 9

现在我们把矩阵中的每条边的中点连起来，这样形成了一个新的矩形，请你计算一下这个新的矩形的覆盖的数字的和。比如，n=3 的时候矩形覆盖的数字如下。

1
2
3
  2
4 5 6
  8

那么当 n 等于 101的时候，矩阵和是多少？

这道题一开始就没认真读,大概是听多了大佬吐槽蓝桥水的话,觉得第一题很简单,以为就是求一个十字型的和.后来才注意到是求一个矩形的和.

我的思路是分开求,第一部分从上到下依次往两边阔,第二部分反之.

代码

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
#include <iostream>
using namespace std;
long long  arr[150][150];

int main(int argc, const char * argv[]) {
    int k = 0;
    for (int i = 1; i <= 101; i++) {
        for (int j = 1; j <= 101; j++) {
            k++;
            arr[i][j] = k;
            
        }
    }
    long long sum = 0;
    int m = 0;
    for (int i = 1; i <= 51; i++) {
        for (int j = 51 - m; j <= 51 + m; j++) {
            sum += arr[i][j];
        }
        m++;
    }
    m = 0;
    for (int i = 101; i >= 52; i--) {
        for (int j = 51 - m; j <= 51 + m; j++) {
            sum += arr[i][j];
        }
        m++;
    }
    cout << sum;
    return 0;
}

题解给的思路是找规律,发现需要计算的点到中心点的距离（横坐标加纵坐标的距离和）都是小于等于 n / 2 的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main() {
	int sum  = 0, n, cnt = 0;
	cin >> n;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			++cnt;
			if(abs(n / 2 - i) + abs(n / 2 - j) <= n / 2){
				sum += cnt;
			}
		}
	}
	cout << sum << endl;
	return 0;
}

2.素数个数

用 0,1,2,3,4,5,6,7. 8个数组成的所有整数中，质数有多少个（每个数字必须用到且只能用一次）。

提示：以 0开始的数字是非法数字。

emmmm这道题一开始又没看到每个数都需要用到..有wa了好久

思路简单,看了题解我写的还是麻烦了,判断了每个数是否重复

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
#include <iostream>
using namespace std;

bool iscommon(int n){
    int book[10] = {0};
    
    while (n) {
        book[n % 10]++;
        n /= 10;
    }
    for (int i = 0; i < 8; i++) {
        if (book[i] != 1) {
            return false;
        }
    }
    return true;
}


bool flag[100000000];
void fun(){
    long long i, j;
    for (i = 0; i < 76543211; i++){
        flag[i] = true;
    }
    flag[0] = flag[1] = false;
    for (i = 2; i < 76543211; i++){
        if (!flag[i])   continue;
        for (j = i * i; j < 76543211; j += i){
            flag[j] = false;
        }
    }
}
int main(int argc, const char * argv[]) {
    int cnt = 0;
    fun();
    for (int i = 10234567; i <= 76543210; i++) {
        if (flag[i] && iscommon(i)) {
            cnt++;
        }
    }
    cout << cnt;
    return 0;
    
}

题解用的搜索, 通过全排列枚举了所有的数.通过num * 10 + i的方式算出一个数,通过num!=0来排除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
#include <iostream>
using namespace std;
const int M = 7;
bool f[N],vis[10];
int sum;

void init() {
	for(int i = 2; i < N; i++) {
		f[i] = true;
	}
	for(int i = 2; i * i < N; i++) {
		if(f[i]) {
			for(int j = i * i; j < N; j+= i){
				f[j] = 0;
			}
		}
	}
}

void dfs(int num,int cnt) {
	if(cnt == M + 1){
		if(f(num)) {
			++sum;
		}
		return ;
	}
	for(int i = num ? 0 : 1; i <= M; ++i) {
		if(!vis[i]) {
			vis[i] = true;
			dfs(num * 10 + i, cnt++);
			vis[i] = false;
		}
	}
}

int main() {
	init();
	dfs(0,0);
	cout << sum << endl;
}

3.连连看

这道题我一开始用手算,肯定也没这么简单..除非找到合适的函数

1
2
3
4
1 4 2 5
2 1 2 1
3 1 3 2
2 5 3 4

还是用深搜,看来蓝桥还是很重视这个.


5.末尾零的个数

求N!末尾0的个数,要想出现0,就是2 * 5,2的个数肯定多余5,所以只要统计5的个数就行

说实话,刚看到这道题我是懵逼的,尽管思路一看就知道了,然而一个死循环怎么跳出来是个问题,对于运算顺序这个忘了,回去翻cpp😢

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main() {
    int n, ans = 0;
    cin >> n;
    while (n) {
        ans += n = n / 5;
    }
    cout << ans << endl;
    return 0;
}

6.藏宝图

搜索不解释,我用深搜过的,题解是广搜.


深夜了,先写到这,明天补充..

script>