-
第十四届蓝桥杯第二期模拟赛题解
第十四届蓝桥杯第二期模拟赛题解
蓝桥杯官网模拟赛排名(12月初更新)
A题(填空题)
题面
请找到一个大于 2022 的最小数，这个数转换成二进制之后，最低的 6 个二进制为全为 0 。
请将这个数的十进制形式作为答案提交。算法(枚举)
直接枚举即可。
更新：本题应该是只需要低六位都为0即可，一开始在做的时候以为第7位应该不能为0。代码(C++)
答案：2112（正解：2048）
#include#include #include using namespace std; string get(int x) { string s; while(x) { s += x % 2 + '0'; x /= 2; } if(s[0] == s[1] && s[1] == s[2] && s[2] == s[3] && s[3] == s[4] && s[4] == s[5] && s[0] == '0') { cout << "res"; } reverse(s.begin(), s.end()); return s; } int get_res(string s) { int res = 0; for(int i = 0; i < s.size(); i ++) res = res * 2 + s[i] - '0'; cout << res << endl; return res; } int main() { // string s; // // int x = 2022; // while(x) // { // s += x % 2 + '0'; // x /= 2; // } // // for(int i = 2023; i <= 10000; i ++) // cout << get(i) << endl; // 100001000000 get_res("100001000000"); // reverse(s.begin(), s.end()); // cout << s << endl; return 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
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
B题(填空题)
题面
我们计从 1949 年 10 月 1 日至 1949 年 10 月 2 日为经过了 1 天。请问从 1949 年 10 月 1 日至 2022 年 1 月 1 日经过了多少天？
算法(模拟)
模拟即可。
代码(c++)
答案：26390
#include#include #include using namespace std; int months[12] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30}; bool is_leapYear(int y) { return y % 400 == 0 || (y % 100 != 0 && y % 4 == 0); } int get(int y, int m, int d) { int res = d; for(int i = 1949; i < y; i ++) if(is_leapYear(i)) res += 366; else res += 365; for(int i = 0; i < m; i ++) res += months[i]; if(m > 2 && is_leapYear(y)) res ++; return res; } int main() { cout << get(2022, 1, 1) - get(1949, 10, 1) << endl; return 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
C题(填空题)
题面
8518 是一个非常特殊的数，如果把这个数看成 16 进制数，它的值为 (8518)16=8161616+51616+116+8=34072，而 34072 正好是 8518 的整数倍。9558 也是这样一个数，当看成 16 进制时是 38232。其实长度为 1 的数 0 到 9 都满足看成 16 进制后是自己的整数倍（1倍）。请问，除开长度为 1 的数，最小的满足这样条件的数是多少？
算法(枚举)
枚举即可。
代码(c++)
答案：1038
#include#include #include using namespace std; bool check(int x) { string s = to_string(x); int res = 0; for(int i = 0; i < s.size(); i ++) res = res * 16 + s[i] - '0'; return res % x == 0; } int main() { int x = 10; while(true) { if(check(x)) { cout << x << endl; break; } x ++; } return 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
D题(填空题)
题面
小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 到 9 之间的数字。现在小蓝想从这个矩阵的第一行第一列画一条折线到第 30 行 60 列，线只能沿水平向右走或竖直向下走，只能在有数字的地方拐弯。小蓝想知道，这样一条线经过的数字的和最大是多少。
本题的输入在文章底部。
算法(线性DP)
线性DP，状态计算为： f [ i , j ] = m a x ( m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) ) + v f[i,j]=max(max(f[i - 1][j], f[i][j - 1])) + v f[i,j]=max(max(f[i−1][j],f[i][j−1]))+v， v v v是该点的权值。答案为 f [ 30 ] [ 60 ] f[30][60] f[30][60]。
代码(c++)
答案：592
#include#include #include using namespace std; const int N = 35, M = 65; int n = 30, m = 60; char g[N][M]; int f[N][M]; int main() { for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1); // cout << "?" << endl; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j] - '0'; } cout << f[n][m] << endl; return 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
E题(填空题)
题面
将 2022 拆分成不同的质数的和，请问最多拆分成几个？
算法(判断质数,01背包求方案数)
可以通过枚举 2 2 2到 2022 2022 2022间的数，对于每个数判断一下是否是质数(共307个)，也可以用线性筛求解质数，接下来本题的意思就是在一堆质数中选取最多的质数个数来凑成2022，并且每一个质数只能选一次，直接上01背包的板子即可，但是需要注意，最终还需求解方案数，01背包的方案数求解就是最终的状态是通过哪一步得来的，一直往前找，一直到最开始的状态，这期间所经历得到状态个数就是答案。
代码(C++)
答案：32
#include#include #include using namespace std; const int N = 2100; int n = 307, m = 2022; int cnt = 0; int primes[N]; bool st[N]; int f[310][N]; void get_primes(int n) { for(int i = 2; i <= n; i ++) { if(!st[i]) { primes[++ cnt] = i; for(int j = i + i; j <= n; j += i) st[j] = true; } } } int main() { get_primes(2022); for(int i = 1; i <= n; i ++) for(int j = 2; j <= m; j ++) { if(primes[i] <= j) { f[i][j] = max(f[i - 1][j], f[i - 1][j - primes[i]] + primes[i]); } else f[i][j] = f[i - 1][j]; } int j = m, res = 0; for(int i = n; i; i --) if(f[i][j] != f[i - 1][j]) { j -= primes[i]; res ++; cout << primes[i] << ' '; } puts(""); // cout << f[n][m] << endl; cout << res << endl; return 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
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
F题
题面
小蓝正在拷贝一份文件，他现在已经拷贝了 t 秒时间，已经拷贝了 c 字节，文件总共有 s 字节，如果拷贝是匀速进行的，请问小蓝大概还需要拷贝多少秒？
输入格式
输入一行包含三个整数 t, c, s，相邻两个整数之间用一个空格分隔。
输出格式
输出一个整数，表示答案。数据保证答案正好是整数。
数据范围
对于 50% 的评测用例，1 <= t, c, s <= 10000。
对于所有评测用例，1 <= t, c, s <= 1000000000。算法(模拟)
模拟即可，对于通过求解速度 v = c / t v=c/t v=c/t的方式来解答本题会在样例 2 2 2就RE了，具体就是 c / t c/t c/t的计算方式会导致其值为0，导致程序中出现除0的代码行，不妨将整个式子写下来，即 a n s w e r = ( s − c ) / ( c / t ) = ( s − c ) × t / c answer=(s-c)/(c/t)=(s-c)\times t/c answer=(s−c)/(c/t)=(s−c)×t/c，题目保证答案一定为整数，只需注意数据范围最大为 1 e 9 1e9 1e9，分子相乘会爆 i n t int int，需要用 l o n g l o n g long\ long long long来表示答案。
代码(C++)
#include#include #include using namespace std; int t, c, s; // (s - c) * t / c // 1000000000 big data int main() { scanf("%d%d%d", &t, &c, &s); printf("%lld\n", (s - c) * 1ll * t / c); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
G题
题面
小蓝有 n 个单词，但是单词中有一些是重复的，请帮小蓝去除重复的单词。
输入格式
输入第一行包含一个正整数 n ，表示小蓝的单词数量。
接下来 n 行，每行包含一个由小写字母组成的单词。输出格式
请输出去除重复后的那些单词。如果一个单词出现了多遍，请保留第一次出现的单词，去除之后出现的单词，按输入的顺序输出。
数据范围
对于所有评测用例，1 <= n <= 100，每个单词的长度不超过 100。
算法(哈希表)
读取数据后，按顺序输出，在输出判断当前字符串是否输出过，没有出现过则输出一行后换行，否则跳过，再在哈希表中存下当前的字符串，在C++中可用 u n o r d e r e d ‾ m a p unordered\underline{~}map unordered map来当作哈希表使用。
代码(C++)
#include#include #include #include using namespace std; const int N = 110; int n; string words[N]; unordered_map<string, int> mp; int main() { cin >> n; for(int i = 0; i < n; i ++) { cin >> words[i]; // mp[words[i]] ++ ; } for(int i = 0; i < n; i ++) { string s = words[i]; if(!mp.count(s)) cout << s << endl; mp[s] ++ ; } return 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
H题
题面
一个字符串如果从左向右读和从右向左读相同，则称为一个回文串，例如 lanqiaoaiqnal 是一个回文串。小蓝有一个字符串，请将这个字符串右边加上一些字符，使其成为一个回文串。如果有多种方案，请输出最短的回文串。
输入格式
输入一行包含一个字符串，由小写英文字母组成。
输出格式
输出一行包含答案。
数据范围
对于所有评测用例，1 <= 字符串长度 <= 100。
算法(贪心,双指针)
枚举字符串中最长的回文后缀即可，枚举出来后，此时的前缀（可能为空）进行反转后就是应当加在最开始字符串的后面，输出答案即可。
代码(C++)
#include#include #include using namespace std; int n; string s; bool check(string s) { int i = 0, j = s.size() - 1; while(i < j) if(s[i ++] != s[j --]) return false; return true; } int main() { cin >> s; n = s.size(); for(int i = 0, len = n; i < n; i ++, len --) { string t = s.substr(i, len); if(check(t)) { string prev = s.substr(0, i); string post = prev; if(prev.size()) { reverse(post.begin(), post.end()); cout << prev + t + post << endl; return 0; } else { cout << t << endl; return 0; } } } return 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
- 44
- 45
- 46
I题
题面
给定一个字母矩阵。一个 X 图形由中心点和由中心点向四个45度斜线方向引出的直线段组成，四条线段的长度相同，而且四条线段上的字母和中心点的字母相同。
一个 X图形可以使用三个整数 r, c, L 来描述，其中 r, c 表示中心点位于第 r 行第 c 列，正整数 L 表示引出的直线段的长度。 对于 1 到 L 之间的每个整数 i，X图形满足：第 r-i 行第 c-i 列与第 r 行第 c 列相同，第 r-i 行第 c+i 列与第 r 行第 c 列相同，第 r+i 行第 c-i 列与第 r 行第 c 列相同，第 r+i 行第 c+i 列与第 r 行第 c 列相同。
例如，对于下面的字母矩阵中，所有的字母 L 组成一个 X图形，其中中间的 5 个 L 也组成一个 X图形。所有字母 Q 组成了一个 X图形。
LAAALA
ALQLQA
AALQAA
ALQLQA
LAAALA
给定一个字母矩阵，请求其中有多少个 X图形。输入格式
输入第一行包含两个整数 n, m，分别表示字母矩阵的行数和列数。
接下来 n 行，每行 m 个大写字母，为给定的矩阵。输出格式
输出一行，包含一个整数，表示答案。
数据范围
对于 50% 的评测用例，1 <= n, m <= 10。
对于所有评测用例，1 <= n, m <= 100。算法(枚举)
由于本题的数据量较小，暴力枚举即可，细节见代码。
代码(C++)
#include#include #include using namespace std; const int N = 110; int n, m; char g[N][N]; inline bool isInner(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } inline bool check(char c, int x, int y, int d) { int ax = x - d, ay = y - d; int bx = x - d, by = y + d; int cx = x + d, cy = y - d; int dx = x + d, dy = y + d; if(isInner(ax, ay) && isInner(bx, by) && isInner(cx, cy) && isInner(dx, dy)) { return c == g[ax][ay] && g[ax][ay] == g[bx][by] && g[bx][by] == g[cx][cy] && g[cx][cy] == g[dx][dy]; } return false; } inline int get(int x, int y) { char c = g[x][y]; int d = 1; while(check(c, x, y, d)) d ++; return d - 1; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1); int res = 0; for(int i = 2; i < n; i ++) for(int j = 2; j < m; j ++) res += get(i, j); printf("%d\n", res); return 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
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
J题
题面
小蓝有一个序列 a[1], a[2], …, a[n]，每次可以交换相邻的两个元素，代价为两个元素中较大的那个。请问，要通过交换将序列变为从小到大递增的序列，总代价最少为多少？
输入格式
输入一行包含一个整数 n ，表示序列长度。
第二行包含 n 个整数，表示给定的序列。输出格式
输出一行包含一个整数，表示最少代价的值。
数据范围
对于 30% 的评测用例，1 <= n <= 1000, 1 <= a[i] <= 1000。
对于 60% 的评测用例，1 <= n <= 50000, 1 <= a[i] <= 50000。
对于所有评测用例，1 <= n <= 1000000, 1 <= a[i] <= 1000000。算法(贪心,逆序对,树状数组)
我们考虑每一个后缀中的第一个元素 x x x应该被交换几次才应该满足最后的升序排列，情况一：如果后缀已经是升序，那么最小代价为0，不需要进行任何交换，情况二：后缀中小于 x x x的所有数都应当于x进行交换，并且最小代价为 c n t ( < x ) × x cnt(
- 证明：对应着情况一、二，情况一：升序，计算下一个后缀，情况二：我们花费了最小代价将其变为升序。
需要说明的是我们并不用手动的将其变为升序，因为只要不存在逆序对，那么这个序列就一定是升序的，我们会花费代价将有逆序对的后缀变为逆序对数量为0的后缀，即升序。
计算逆序对的方式有很多，在本题中最适合使用的是支持单点修改和区间查询的树状数组。
注意某点的代价极限为 1 e 6 × 1 e 6 1e6 \times 1e6 1e6×1e6，会爆 i n t int int，记得开 l o n g l o n g long\ long long long。代码(C++)
#include#include #include using namespace std; const int N = 1000010; typedef long long LL; int n; int a[N]; int tr[N]; int lowbit(int x) { return x & -x; } void add(int x, int v) { for(int i = x; i < N; i += lowbit(i)) tr[i] += v; } int query(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", &a[i]); LL res = 0; for(int i = n; i >= 1; i --) { int v = a[i]; res += query(v - 1) * 1ll * v; add(v, 1); } printf("%lld\n", res); return 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
- 44
- 45
- 46
- 47
附录
D题输入（30 × \times × 60）
174094882455171152761423221685761892795431233411387427793198 650286024865090061389344606618496378829135984076361542097372 601657541200146071777733599818266038012509478351201640618984 143988087783837107349651099683484992553337438088068198972282 890781586124258626539246182119762952003918195325258677229419 698255491250839396799769357665825441616335532825361862146291 503649293440596342887581257444442930778730382520372975343211 325351222640703400531067500454956482168314849207060705673849 265774579830223671554026061117300483012903885770893074783710 083450145620356667677191627276513995926532444279237315785832 411595106453089134746365281031552217482363035280722591085079 053410485925413958279617719034175332412908745680774313630190 429314820559328748143552689295945058801322270313370955837837 939182801848609300876356583948397645861551964542532682663945 625356614462682551015176002433628234343684739800880514363921 982340231989891351425389287014819359798014755509282450440511 590838726938103384801541373585690893606978941566666714061214 952341523168827712604946036245881214982452998386986623826275 782780208928205527678781609589000725521486468983551558405472 149903035076783644195574734088152324666290493119955560594634 905391288186024902215444250421277955403412298227858394469856 607272647132163832860126054679347881638761723785858733108109 249157334220127702410373959720286708183036202841837581704881 367895556630088230650972282944827258473951902831431040790814 079538232104075905120989173307660289899942087873076421916033 622143260549608274076012938515668898707915863945382394851328 164677964192631597026176253407553188801750590935427267220117 591817866992665840378311257621611574856498432538327068011953 631534031790352912617015229051836886166704989498756486878095 690013558017746707412183571476823027885971347137127534455141- 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
-
相关阅读:
【UIPickerView-UIDatePicker-应用程序对象 Objective-C语言】
Mac opencv 摄像头权限
SpringMVC调用流程
大话超越菜鸟C#的实践入门进阶必知点，深入浅出解析 32 算法入门 循环和递归
【Excel VBA和Python对照学习】创建字典
一文简要了解星闪技术优势点
R语言经典统计分析
修改Mysql数据库的用户名和密码【详细】
Go语言excelize包-06-样式设置（样式设置、区间使用样式、行使用样式、列使用样式）
数据分享|函数型数据分析部分省市新冠疫情数据
- 原文地址：https://blog.csdn.net/zygood_/article/details/127981632
