©2020-2024 ioDraw All rights reserved
2020/11/14裂开了
<>第十一届蓝桥杯国赛C/C++B组总结
主要是对填空进行总结（大题根本就不会 ），填空感觉做的还行？希望能拿到好成绩。
答案不一定正确，主要是看该答案的人比较多，欢迎讨论。
代码也是回来现敲的，欢迎指错。
<>试题 A: 美丽的 2
本题总分:5 分
【问题描述】
小蓝特别喜欢 2,今年是公元 2020 年,他特别高兴。
他很好奇,在公元 1 年到公元 2020 年(包含)中,有多少个年份的数位中包含数字 2?
正确答案：
563
代码：
略- -。。。。。
<>试题 B: 扩散
本题总分:5 分
【问题描述】
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点:(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色,其它位置都是白色的。
每过一分钟,黑色就会扩散一点。具体的,如果一个格子里面是黑色,它就会扩散到上、下、左、右四个相邻的格子中,使得这四个格子也变成黑色(如果原来就是黑色,则还是黑色)。
请问,经过 2020 分钟后,画布上有多少个格子是黑色的。
正确答案：
20312088
思路：
就是BFS，把这四个点push进一个队列，然后每次出队把其四周的点变黑（注意去重），然后标记时间，时间=2020就退出即可。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include
<cstring> #include<stack> #include<set> #include<map> #include<queue> #include
<algorithm> #include<unordered_set> #define ll long long #define pii
pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back
#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using
namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;
char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =
getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48
); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,
a% b); } queue < pair<pair<int, int>, int > >q;
//记录下每一个<x,y>坐标是第t秒变黑的x,y,t分别对应前面的三个维度 map<pii, int> vis; int nexti[4][2] = { {1
,0},{0,1},{-1,0},{0,-1} }; int main() { q.push(mp(mp(0, 0), 0)); q.push(mp(mp(
2020, 11), 0)); q.push(mp(mp(11, 14), 0)); q.push(mp(mp(2000, 2000), 0)); vis[mp
(0, 0)] = 1; vis[mp(2020, 11)] = 1; vis[mp(11, 14)] = 1; vis[mp(2000, 2000)] = 1
; ll ans = 4; int bf = -1; while (1) { auto p = q.front().first; int time = q.
front().second; /*if (bf != time) { bf = time; cout << time << endl; }*/ if (
time== 2020)break;//这个是2020分钟生成的 for (int i = 0; i < 4; i++) { int nx = p.first
+ nexti[i][0]; int ny = p.second + nexti[i][1]; if (!vis[mp(nx,ny)]) { vis[mp(nx
, ny)] = 1; ans++; q.push(mp(mp(nx, ny), time + 1)); } } q.pop(); } cout << ans;
}
(要跑挺久，我直接附上截图了）
<>试题 C: 阶乘约数
本题总分:10 分
【问题描述】
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
正确答案：
39001250856960000
思路：
其实就是把从那些因子中挑出来问你最多能组成多少个数。
为了防止2*3=6的重复计算，我们不能直接挑，所以要先用唯一分解定理分解成素因子乘积的形式
如：5!=1*2*3*4*5=23*31*51;
所以现在的情况变成了：2有4种选择（0、1、2、3个），3有2种选择（0、1个），5有2种选择（0、1个）.即每个素因子的选择个数是其幂次+1。
所以对于100！的答案就是把2-100的每一个数进行分解，记录下每一个素因子的个数，然后+1乘起来即可
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include
<cstring> #include<stack> #include<set> #include<map> #include<queue> #include
<algorithm> #include<unordered_set> #define ll long long #define pii
pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back
#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using
namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;
char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =
getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48
); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,
a% b); } int flag[105]; int main() { int i; for (int i = 2; i <= 100; i++) {
int tmp = i; for (int j = 2; j <= tmp; j++) { while (tmp % j == 0) { tmp /= j;
flag[j]++; } } } ll ans = 1; for (int i = 1; i <= 100; i++) { ans *= flag[i] + 1
; } cout << ans; }
<>试题 D: 本质上升序列
本题总分:10 分
【问题描述】
小蓝特别喜欢单调递增的事物。
在一个字符串中,如果取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。
例如,在字符串 lanqiao 中,如果取出字符 n 和 q,则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。
小蓝发现,有些子序列虽然位置不同,但是字符序列是一样的,例如取第二个字符和最后一个字符可以取到 ao,取最后两个字符也可以取到
ao。小蓝认为他们并没有本质不同。
对于一个字符串,小蓝想知道,本质不同的递增子序列有多少个?
例如,对于字符串 lanqiao,本质不同的递增子序列有 21 个。它们分别是
l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。
请问对于以下字符串(共 200
个小写英文字母,分四行显示):(如果你把以下文字复制到文本文件中,请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件
inc.txt,内容与下面的文本相同)
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个?
正确答案：
3616159
思路：
我们先考虑如果出现重复的字符串怎么办：比如axxbxxxb，那么有两个ab递增子序列，则对于该ab递增子序列，在其后面延展字母构成新的递增子序列个数我们可以发现肯定是前一个ab的递增子序列的个数要>=第二个的，可以说第二个的答案是第一个是子集。那么我们对于同一种的递增子序列我们只需要记录其最早出现的即可，后续的出现也不需要管了。
基于上述所讲，我们可以使用BFS，使用队列，队列内记录字符串以及该递增子序列最后一个字符的位置，对于每次队首的字符串s，其末尾位置设为t，我们只需要从t+1到s.size()-1位置找到任何比s[t]大的即可插入到队列中去，这个过程进行去重、计数即可。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include
<cstring> #include<stack> #include<set> #include<map> #include<queue> #include
<algorithm> #include<unordered_set> #define ll long long #define pii
pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back
#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using
namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;
char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =
getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48
); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,
a% b); } map<string, int> vis; int main() { queue<pair<string, int>> q; string
s; cin >> s; int i; ll ans = 0; for (i = 0; i < s.size(); i++) { string tmp = ""
; tmp += s[i]; if (!vis[tmp]) { vis[tmp] = 1; q.push(mp(tmp, i)); ans++; } }
while (q.size()) { string t = q.front().first; int pos = q.front().second; q.pop
(); for (int i = pos + 1; i < s.size(); i++) { if (s[i] > s[pos] && !vis[t + s[i
]]) { vis[t + s[i]] = 1; q.push(mp(t + s[i], i)); ans++; } } } cout << ans; }
这题也需要点时间直接放截图了：
<>试题 E: 玩具蛇
本题总分:15 分
【问题描述】
小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将玩具蛇放进去。
下图给出了两种方案:
正确答案：
552
思路：
这题。。。有点简单是怎么回事。。。。就是无脑DFS，枚举4*4个蛇头的位置，然后往下搜就完事了。。。。感觉还不如B、C、D的难度大。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include
<cstring> #include<stack> #include<set> #include<map> #include<queue> #include
<algorithm> #include<unordered_set> #define ll long long #define pii
pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back
#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using
namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;
char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =
getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48
); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,
a% b); } int vis[5][5]; int nexti[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }; ll ans
= 0; void dfs(int x, int y,int count) { if (x >= 4 || x < 0 || y >= 4 || y < 0)
return; if (count == 16) { ans++; } for (int i = 0; i < 4; i++) { int nx = x +
nexti[i][0]; int ny = y + nexti[i][1]; if (!vis[nx][ny]) { vis[nx][ny] = 1; dfs(
nx, ny, count + 1); vis[nx][ny] = 0; } } } int main() { int i; for (i = 0; i < 4
; i++) { for (int j = 0; j < 4; j++) { vis[i][j] = 1; dfs(i, j, 1); vis[i][j] =
0; } } cout << ans; }
大题略了。。自己都一知半解疯狂骗分就不误人子弟了。
这里分享一下我答答疑那题的思路（不保证正确）：
<>试题 H: 答疑
本题总分:20 分
【问题描述】
有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。
一位同学答疑的过程如下：
* 首先进入办公室，编号为 i 的同学需要 si 毫秒的时间。
* 然后同学问问题老师解答，编号为 i 的同学需要 ai 毫秒的时间。
* 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可
以忽略。
* 最后同学收拾东西离开办公室，需要 ei 毫秒的时间。一般需要 10 秒、
20 秒或 30 秒，即 ei 取值为 10000，20000 或 30000。
一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群
里面发消息的时刻之和最小。
思路：
贪心，贪心策略：s+a+e从小到大排序即可。证明过程：