计蒜客蓝桥模拟(5)

  1. 1.矩阵求和
  2. 2.素数个数
  3. 3.连连看
  4. 5.末尾零的个数
  5. 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>