蓝桥杯校内模拟赛题解-1
1. 在计算机存储中,15.125GB 是多少MB ?
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。
答案: 15488
解析:
还要解析???
2. 1200000 有多少个约数(只计算正约数) 。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。
答案: 96
解析:
暴力解法:
1 2 3 4 5 6 int ans = 0 ;for (int i = 1 ; i <= 1200000 ; ++ i) { if (1200000 % i == 0 ) { ++i; } }
一般解法:
分解质因数, 得: 1200000 = 2^7 3 5^5.
约数个数为等于: 8 2 6 = 96.
3. 在1 至2019 中,有多少个数的数位中包含数字9 ?
注意,有的数中的数位中包含多个9 ,这个数只算一次。例如,1999 这个数包含数字9 ,在计算只是算一个数。
答案: 544
解析:
快速解法:
1 2 3 4 5 6 7 int ans = 0 ;for (int i = 1 ; i <= 2019 ; ++ i){ if (to_string (i).find ("9" ) != string::npos){ ans++; } } cout<<ans<<endl;
一般解法:
1 2 3 4 5 6 7 8 9 10 11 12 int ans = 0 ;for (int i = 1 ; i <= 2019 ; ++ i){ int now = i; while (now){ if (now % 10 == 9 ){ ans ++; break ; } now /= 10 ; } } cout<<ans<<endl;
4. 一棵包含有2019 个结点的树,最多包含多少个叶结点?
答案: 2018, 如果题目问的是二叉树就是1010.
解析:
正常的树叶子节点最多显然2018 个. 如果是二叉树, 为了保证叶子节点最多我们要使得每一个非叶子节点都有两个孩子. 显然, 一棵满二叉树满足这个条件.
对于一个2047
个节点的满二叉树, 共有1024
个叶子节点, 我们** “成对的”** 删去其中的28
个之后, 正好剩余2019
个节点. 删掉了28
个叶子节点后, 他们的父节点也就成为了新的叶子节点, 因此叶子节点减少了14
个. 答案就是1024 - 14
.
上述证明不严谨
5. 问题描述
一个正整数如果任何一个数位不大于右边相邻的数位,则称为一个数位递增的数,例如1135 是一个数位递增的数,而1024 不是一个数位递增的数。
给定正整数n ,请问在整数1 至n 中有多少个数位递增的数?
输入格式
输入的第一行包含一个整数n 。
输出格式
输出一行包含一个整数,表示答案。
样例输入
样例输出
评测用例规模与约定
对于40% 的评测用例,1 <= n <= 1000。
对于80% 的评测用例,1 <= n <= 100000。
对于所有评测用例,1 <= n <= 1000000。
题解:
暴力即可, 时间复杂度为O(n * log10(n)).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int n = 0 ;int ans = 0 ;cin>>n; for (int _ = 1 ; _ <= n; ++ _) { int i = _; int flag = 1 ; int last = i % 10 ; while (1 ){ i /= 10 ; if (i == 0 ) { break ; } if (last >= i % 10 ) { last = i % 10 ; }else { flag = 0 ; break ; } } ans += flag; } cout<<ans<<endl;
6. 问题描述
小明对类似于hello 这种单词非常感兴趣,这种单词可以正好分为四段,第一段由一个或多个辅音字母组成,第二段由一个或多个元音字母组成,第三段由一个或多个辅音字母组成,第四段由一个或多个元音字母组成。
给定一个单词,请判断这个单词是否也是这种单词,如果是请输出yes ,否则请输出no 。
元音字母包括a, e, i, o, u ,共五个,其他均为辅音字母。
输入格式
输入一行,包含一个单词,单词中只包含小写英文字母。
输出格式
输出答案,或者为yes ,或者为no 。
样例输入1
样例输出2
样例输入1
样例输出2
解析
暴力即可, 时间复杂度O(n).
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 53 54 inline bool aeiou (char c) { return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' ; } int pos = 0 ;int count = 0 ;int size = str.size ();for (; pos < size; ++pos) { if (!aeiou (str[pos])) { count++; } else { break ; } } if (count == 0 ) { cout << "no" << endl; return 0 ; } count = 0 ; for (; pos < size; ++pos) { if (aeiou (str[pos])) { count++; } else { break ; } } if (count == 0 ) { cout << "no" << endl; return 0 ; } count = 0 ; for (; pos < size; ++pos) { if (!aeiou (str[pos])) { count++; } else { break ; } } if (count == 0 ) { cout << "no" << endl; return 0 ; } count = 0 ; for (; pos < size; ++pos) { if (aeiou (str[pos])) { count++; } else { break ; } } if (count == 0 ) { cout << "no" << endl; return 0 ; } cout << "yes" << endl;
7. 问题描述
在数列a[1], a[2], …, a[n] 中,如果对于下标i, j, k 满足0<i<j<k<n+1 且a[i]<a[j]<a[k] ,则称a[i], a[j], a[k] 为一组递增三元组,a[j] 为递增三元组的中心。
给定一个数列,请问数列中有多少个元素可能是递增三元组的中心。
输入格式
输入的第一行包含一个整数n 。
第二行包含n 个整数a[1], a[2], …, a[n],相邻的整数间用空格分隔,表示给定的数列。
输出格式
输出一行包含一个整数,表示答案。
样例输入
样例输出
样例说明
a[2] 和a[4] 可能是三元组的中心。
评测用例规模与约定
对于50% 的评测用例,2 <= n <= 100,0 <= 数列中的数<= 1000 。
对于所有评测用例,2 <= n <= 1000,0 <= 数列中的数<= 10000 。
题解
乍一看1e5
还以为不能暴力, 结果一看n
的范围是1e3
, 果断暴力走起, 复杂度O(n^2).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 int n = 0 ;int data[1010 ] = {0 };cin>>n; for (int i = 0 ; i < n; ++ i){ cin>>data[i]; } int ans = 0 ;for (int i = 0 ; i < n; ++ i) { int flag = 0 ; for (int j = i-1 ; j >= 0 ; -- j){ if (data[j] < data[i]){ flag += 1 ; break ; } } for (int j = i+1 ; j < n; ++ j){ if (data[j] > data[i]){ flag += 1 ; break ; } } ans += (flag == 2 ); } cout<<ans<<endl;