计蒜客蓝桥模拟(5)
2.素数个数 3.连连看 5.末尾零的个数 6.藏宝图
org,先%为敬,感觉比第一次难度大点,审题老是审不明白就做..耽误好多时间..希望考场能好好读题. 1.矩阵求和
给你一个从 n×n 的矩阵,里面填充 1 到 n×n.例如当 n 等于 3 的时候,填充的矩阵如下。
现在我们把矩阵中的每条边的中点连起来,这样形成了一个新的矩形,请你计算一下这个新的矩形的覆盖的数字的和。比如,n=3 的时候矩形覆盖的数字如下。
那么当 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>