目录
1A：跑步训练（填空5分_模拟）
2B：纪念日（填空5分_日期计算）
3C：合并检测（填空10分_数学）
4D：REPEAT程序（填空10分_模拟）
5E：矩阵（填空15分_dp）
6F：整除序列（编程题15分）
解析代码（模拟）
7G：解码（编程题20分）
解析代码（二叉树的数组遍历）
8H：走方格（编程题20分）
解析代码（dp）
9I：整数拼接（编程题25分）
解析代码1（暴力_超时）
解析代码2（数学+哈希）
10J：网络分析（编程题25分）
解析代码1（普通并查集_超时）
解析代码2（带权并查集_正解）
1A：跑步训练（填空5分_模拟）
题目描述：
小明要做一个跑步训练。
初始时，小明充满体力，体力值计为 10000 。如果小明跑步，每分钟损耗 600 的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是均匀变化的。
小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达 0 ，他就停止锻炼。
请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。
题目解析：
首先求出每秒的损耗，之后模拟跑步休息的锻炼过程就可以，答案3880
#include <iostream>
using namespace std;int main()
{int power = 10000;int minute = 0;while (power >= 600) // 两分钟-300{minute += 2;power -= 300;}//cout << power << endl; // 600体力跑60秒，剩余的体力还能跑 power / 10 秒cout << minute * 60 + power / 10 << endl; // 以秒输出，答案3880return 0;
}2B：纪念日（填空5分_日期计算）
题目描述：
2020 年 7 月 1 日是中国 共 产 党 成立 99 周年纪念日。
中国 共 产 党 成立于 1921 年 7 月 23 日。
请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包含多少分钟？
题目分析：打开计算器，答案52038720
贴个代码：
#include<iostream>
using namespace std;
int yearDay(int year)
{if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)){return 366;}return 365;
}
int main()
{int time = 0;for (int i = 1922; i <= 2020; ++i){time += yearDay(i);}time -= 22;cout << time * 24 * 60 << endl;return 0;
}3C：合并检测（填空10分_数学）
题目描述：
新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情， A 国准备给大量民众进病毒核酸检测。
然而，用于检测的试剂盒紧缺。为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（ k 个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k 个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看，如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用了 k+1 个试剂盒完成了 k 个人的检测。
A 国估计被测的民众的感染率大概是 1，呈均匀分布。请问 k 取多少能最节省试剂盒？
题目解析：感染率是1%。。。加个百分号这么难。。。。。。答案10
核心思路：假设总人数为100人，那么就有，对于k枚举 1~100 的范围内
（1）对于 总人数100%k==0 的情况：需要的总的试剂盒为：（100/i）+ i
解释：（100/i）：100个人中每次分为i个人 为 1组，那么总共就分为了 100/i组
解释： +i是因为 它有1%的阳性率，（概率呈均匀分布）那么这100个人中就必定有人为阳性，那么就需要对，患阳性的那一组重新进行i个人的检测
（2）对于 总人数100%k!=0 的情况：需要的总的试剂盒为：（100/i）+ 1 + i
解释：对于除不尽的情况需要进行+1 处理，即被分为了（100/i）+1组，剩下的的解释就与上面相同
#include<iostream>
using namespace std;int main()
{int ans = 0;int sum = 0x3f3f3f3f; // 初始化为一个很大的数，因为要求的是小于的情况for (int i = 1; i <= 100; i++) // 枚举所有的检测数 {if (100 % i == 0){if (100 / i + i < sum){sum = 100 / i + i;ans = i; // 题目要求的是被分为多少组是最小的，所以需要进行记录}}else{if (100 / i + 1 + i < sum){sum = 100 / i + 1 + i;ans = i; // 记录当前最小的检测数}}}cout << ans << endl;return 0;
}4D：REPEAT程序（填空10分_模拟）
题目描述：
附件 prog.txt 中是一个用某种语言写的程序。
其中 REPEAT k 表示一个次数为 k 的循环。循环控制的范围由缩进表达，从次行开始连续的缩进比该行多的（前面的空白更长的）为循环包含的内容。
例如如下片段：REPEAT 2:A = A + 4REPEAT 5:REPEAT 6:A = A + 5A = A + 7A = A + 8 A = A + 9该片段中从 A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的循环两次中。
REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 循环中。
A = A + 5 实际总共的循环次数是 2 × 5 × 6 = 60 次。
请问该程序执行完毕之后，A 的值是多少？
题目解析：
从题目中看出REPEAT就是一个for循环，后面的数字就是循环次数，循环控制的范围由缩进表达。然后模拟出题就可以。
答案403
#include<iostream>
using namespace std;int main()
{int a = 0;for (int i = 0; i < 2; i++) // 枚举所有的检测数 {a += 4;for (int j = 0; j < 5; ++j){for (int k = 0; k < 6; ++k){a += 5;}a += 7;}a += 8;}a += 9;cout << a << endl; // 答案403return 0;
}5E：矩阵（填空15分_dp）
题目描述：
把 1∼2020 放在 2×1010 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以 2020 的余数即可。
题目解析：
f [ i ] [ j ]：第一行放 i 个数字，第二行放 j 个数字的方案数量；
- 将当前数放在第一行：f [ i ] [ j ] += f[ i - 1] [ j ]；
- 将当前数放在第二行：f [ i ] [ j ] += f[ i ] [ j - 1 ]；
答案：1340
#include <iostream>
using namespace std;int f[1020][1020];
int main()
{f[0][0] = 1; // 两行一个数字都不放，也是一种方案for (int i = 0; i <= 1010; i++){for (int j = 0; j <= i; j++){if (i - 1 >= j) // 转移前的状态也要合法，即第一行的数量不小于第二行的数量f[i][j] += f[i - 1][j] % 2020;if (j - 1 >= 0)f[i][j] += f[i][j - 1] % 2020;}}cout << f[1010][1010] << endl; // 答案1340return 0;
}6F：整除序列（编程题15分）
题目描述：
有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输出这个序列中值为正数的项。
【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。
【评测用例规模与约定】
对于 80% 的评测用例，1 ≤ n ≤ 10^9。
对于所有评测用例，1 ≤ n ≤ 10^18。
解析代码（模拟）
#include <iostream>
using namespace std;int main()
{long long n = 0;cin >> n;while (n >= 1){cout << n << " ";//n >>= 1;n /= 2;}return 0;
}7G：解码（编程题20分）
题目描述：
小明有一串很长的英文字母，可能包含大写和小写。在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。
例如，连续的 5 个 a，即 aaaaa，小明可以简写成 a5（也可能简写成 a4a、aa3a 等）。
对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。
为了方便表达，小明不会将连续的超过 9 个相同的字符写成简写的形式。
现在给出简写后的字符串，请帮助小明还原成原来的串。
输入格式
输入一行包含一个字符串。输出格式
输出一个字符串，表示还原后的串。样例输入
H3el5o2样例输出
HHHellllloo数据范围
对于所有评测用例，字符串由大小写英文字母和数字组成，长度不超过100。
请注意原来的串长度可能超过 100。
题目解析：直接模拟即可。
#include <iostream>
#include <string>
using namespace std;int main()
{string str;cin >> str;int n = str.size();for (int i = 0; i < n; ++i){int n = (str[i] - '0');if (n >= 0 && n <= 9){for (int j = 0; j < n - 1; ++j) // 之前已经输出一个了{cout << str[i - 1];}}else{cout << str[i];}}return 0;
}解析代码（二叉树的数组遍历）
#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
long long arr[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}int maxv = -INF;int depth = 1, res = 1;for (int i = 1; i <= n; i *= 2){long long s = 0; // 完全二叉树每层的开头为2^(n-1)，结尾则是 2^n - 1for (int j = i; j <= i * 2 - 1 && j <= n; j++) // j++就是同一层的下一个{s += arr[j];}if (s > maxv){maxv = s;res = depth;}depth++;}cout << res << endl;return 0;
}8H：走方格（编程题20分）
题目描述：
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。
现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下走。
注意，如果行号和列数都是偶数，不能走入这一格中。
问有多少种方案。
【输入格式】
输入一行包含两个整数 n, m。
【输出格式】
输出一个整数，表示答案。
【评测用例规模与约定】
对于所有评测用例，1≤n≤30,1≤m≤30。
解析代码（dp）
题目解析：简单的dp，dp [ i ] [ j ] 表示走到第 n 行第 m 列的方案数
#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0, m = 0;cin >> n >> m;vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));// dp [ i ] [ j ] 表示走到第 n 行第 m 列的方案数dp[0][1] = 1;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){if (i % 2 == 1 || j % 2 == 1){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}cout << dp[n][m] << endl;return 0;
}9I：整数拼接（编程题25分）
题目描述：
样例输入
4 2 1 2 3 4样例输出
6【评测用例规模与约定】
对于 30% 的评测用例，1≤n≤1000，1≤K≤20，1≤Ai≤10^4。
对于所有评测用例，1≤n≤10^5，1≤K≤10^5，1≤Ai≤10^9。
解析代码1（暴力_超时）
题目解析：暴力模拟：（时间超限，过了0个民间测试用例。。。）
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{int n = 0, k = 0;cin >> n >> k;vector<int> arr(n);for (int i = 0; i < n; ++i){cin >> arr[i];}int cnt = 0;for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (i == j)continue;string tmp1 = to_string(arr[i]);string tmp2 = to_string(arr[j]);string tmp = tmp1 + tmp2;long long x = atoi(tmp.c_str());if (x % k == 0)++cnt;}}cout << cnt << endl;return 0;
}解析代码2（数学+哈希）
根据题意可推出，A与B拼接可以推出等式 A + 10 ^ x + B ，题目可以翻译成是求A + 10 ^ x + B % K == 0的个数。
通过观察等式A + 10 ^ x ^ +B % K == 0进行等价变形，变成(A + 10 ^ x) % K = -B % K ，并且B与x正相关，则可以用一个哈希表存起来A + 10x，用空间换时间，那么我们的两重循环就可以换成一个只枚举A，调用哈希只需要O(1)的时间，到现在看来题目就迎刃而解了，此时时间复杂度为O(n)。补充： - B % K == (K - (B % K)) % K（感兴趣的话百度了解一下）
//#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int N = 100010;
typedef long long ll;
ll arr[N], hash_table[11][N];
int main()
{int n = 0, k = 0;cin >> n >> k;for (int i = 0; i < n; ++i){cin >> arr[i];ll t = arr[i] % k;for (int j = 0; j < 11; ++j){hash_table[j][t]++;t = t * 10 % k;}}ll res = 0;for (int i = 0; i < n; ++i){int len = to_string(arr[i]).size();res += hash_table[len][(k - (arr[i] % k)) % k];ll t = arr[i] % k;while (len--){t = t * 10 % k;}if (t % k == (k - (arr[i] % k)) % k)--res; //判重 如果查找到的值包括自己，减掉自己}cout << res << endl;return 0;
}10J：网络分析（编程题25分）
题目描述：
小明正在做一个网络实验。
他设置了 n 台电脑，称为节点，用于收发和存储数据。
初始时，所有节点都是独立的，不存在任何连接。
小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在网线连接，称为相邻。
小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小。
【输入格式】
输入的第一行包含两个整数 n,m，分别表示节点数量和操作数量。节点从1 至 n 编号。
接下来 m 行，每行三个整数，表示一个操作。
如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 a=b 时，表示连接了一个自环，对网络没有实质影响。
如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。
【输出格式】
输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示进行
完上述操作后节点 1 至节点 n 上存储信息的大小。【样例输入】
4 8 1 1 2 2 1 10 2 3 5 1 4 1 2 2 2 1 1 2 1 2 4 2 2 1【样例输出】
13 13 5 3
【评测用例规模与约定】
对于 30% 的评测用例，1≤n≤20，1≤m≤100。
对于 50% 的评测用例，1≤n≤100，1≤m≤1000。
对于 70% 的评测用例，1≤n≤1000，1≤m≤10000。
对于所有评测用例，1≤n≤10000，1≤m≤100000，1≤t≤100。
解析代码1（普通并查集_超时）
暴力做法： 观察题意有两个操作：
- 将两个点合并。
- 将a点所在的集合全部点都加上t。
首先先说下暴力做法，连接用普通并查集维护，然后对于每次要加上权值时，遍历集合每个点即可。时间复杂度是O(n*m),显然是会超时的，但是得到的分数非常可观，能拿70%的分数。
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int N = 10010;
int w[N], p[N];
int Find(int x)
{if (x != p[x])p[x] = Find(p[x]);return p[x];
}
void Union(int a, int b)
{int x = Find(a);int y = Find(b);if (x != y) p[x] = y;
}
int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i){p[i] = i;}for (int i = 0; i < m; ++i){int a, b, c;cin >> a >> b >> c;if (a == 1){Union(b, c);}else{int x = Find(b);for (int i = 1; i <= n; ++i){if (x == Find(i))w[i] += c;}}}for (int i = 1; i <= n; ++i){cout << w[i] << " ";}return 0;
}解析代码2（带权并查集_正解）
本题正解是用带权并查集做，根据题意的两个操作来看：1.将两个点合并。2.将a点所在的集合全部点都加上t。如果我们要优化时间的话，能下手的就只有第二个操作了。
那首先我们定义，每个结点的权值就是到根节点权值和。那我们第二个操作可以看成是，每次在a点所在集合的根节点加上t。那我们这样定义可以保证每个点权值都正确吗？答案是可以的，我们并查集存在路径压缩的操作，所以权值和是可以通过路径压缩来维护。那这样我们每次添加的时候，就只需要让根结点添加即可，时间复杂度就从O(nm) 降到了O(n).
还没完，我们现在需要根据上边的新定义，来保证我们的压缩路径和结点合并的合法性。
先看结点合并，当我们两个结点合并的时候是意味着我们两个树会进行合并，比如下面这个例子，如果权值为5的根结点要合并到权值为4的根节点上，那根据我们上边的定义，那权值为5的根结点将会全部加上4，那这显然就不对了。那要解决这个问题的话，我们可以让5的权值减去4，这样就能保证合法。合并起来的话，权值依旧不变。
接下来就是处理路径压缩了，那对于我们的x结点有三种情况，第一种x就是根结点，这种情况我们就直接返回即可，第二种就是x的父节点就是根节点，那这种情况我们也是直接退出（并查集最多压缩成两层，不清楚的话就需要去复习下基础并查集了）。最后一种就是我们要处理的，x经过若干层才到根结点。那我们压缩路径要做的就是让x直接指向根节点，在这种情况下，那随着我们压缩路径，x最终变成第三层，那我们此时的x权值就要更新成，d[x] += d[p[x]](加上x父亲指向上边结点的权值）。
那到此为止，细节处理完毕，直接coding解决。最终时间复杂度O(N*logN) 并查集的压缩路径时间为logn，但是一般实际运行速度可以看成O(1)
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int N = 10010;
int p[N], d[N];
int Find(int x)
{if (p[x] == x || p[p[x]] == p[x])return p[x];int r = Find(p[x]);d[x] += d[p[x]];p[x] = r;return r;
}
int main()
{int n = 0, m = 0;cin >> n >> m;for (int i = 1; i <= n; ++i){p[i] = i;}while (m--){int a, b, t;cin >> t >> a >> b;if (t == 1){a = Find(a), b = Find(b);if (a != b){d[a] -= d[b]; //合并时，a结点的权值要减去b结点的权值p[a] = b;}}else{a = Find(a);d[a] += b; // 直接往根结点上加权}}for (int i = 1; i <= n; ++i){if (Find(i) == i) // 如果是根结点，权值就为自己printf("%d ", d[i]);else // 如果不是根结点，权值需要加上根节点的值printf("%d ", d[i] + d[Find(i)]);}return 0;
}
