⏰总用时：170/240 🎯总分：39/150
| 题号 |
时间 |
结果 |
满分 |
难度 |
备注 |
| 1 |
5 |
✅ |
5 |
🌕 |
|
| 2 |
5 |
✅ |
5 |
🌕 |
|
| 3 |
5 |
✅ |
10 |
🌕 |
|
| 4 |
20 |
❌ |
10 |
🌓 |
🔹 用 BFS、queue 遍历
🔹 输入地图时用 char 而不是 int |
| 5 |
35 |
❌ |
10 |
🌓 |
🔸 快速计算 $a^b(mod p)$
🔸 快速计算 $a*b(mod p)$ |
| 6 |
20 |
20% |
15 |
🌓 |
🔹 二叉树
🔹 先算出每个节点所在层数，再根据层数算总和，这样不会超时 |
| 7 |
40 |
40% |
20 |
🌓 |
🔸 模拟
🔸 用 map 容器，以外卖店的视角存储订单信息
🔸 可以通过的，要注意易错的细节❗❗❗ |
| 8 |
30 |
40% |
20 |
🌓 |
🔹 并查集（不过没用） |
| 9 |
10 |
❌ |
25 |
🌑 |
🔸 状压dp
🔸 fill()：初始化数组，填充内容可不为0 |
| 10 |
|
|
25 |
|
|
1 【填空】平方和
题目
小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
注意，平方和是指将每个数分别平方后求和。
请问，在 1 到 2019 中，所有这样的数的平方和是多少？
解析
注意审题，求的是满足条件的数字平方之和，不是个数❗❗❗
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <bits/stdc++.h>
using namespace std;
bool check(int x){
int t;
while(x){
t=x%10;
if(t==2 || t==0 || t==1 || t==9)
return true;
x=x/10;
}
return false;
}
int main(){
long long sum=0;
for(int i=1;i<=2019;i++){
if(check(i)) sum+=(i*i);
}
cout<<sum;
return 0;
}
|
2 【填空】数列求值
题目
给定数列 1,1,1,3,5,9,17,⋯，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。
解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int a=1,b=1,c=1,t;
for(int i=1;i<=20190324;i++){
if(i<=3) continue;
t=c;
c=(a+b+c)%10000; // 第 i 项
a=b;b=t;
// cout<<i<<": "<<a<<" "<<b<<" "<<c<<endl;
}
cout<< c;
return 0;
}
|
3 最大降雨量
题目
由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。
这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使用。
每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术 施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。
由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？
解析
4 迷宫
题目
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
1
2
3
4
|
010000
000100
001001
110000
|
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D < L < R < U。
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
|
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
|
解析
🟠 利用 BFS 从后往前找出每个点到终点的最短路径，使用 queue 容器完成遍历
🟡 再从前往后按字典顺序查找答案
🟢 输入地图时必须用 char 类型，不能用 int，不然会报错（不知道为啥
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
55
56
57
58
59
60
61
|
#include <bits/stdc++.h>
using namespace std;
char g[40][60]; // 存储原始迷宫
int dp[40][60]; // 存储最短路径
int x[4]={1,0,0,-1};
int y[4]={0,-1,1,0};
char c[4]={'D','L','R','U'};
// 检查坐标是否在给定范围内、且未访问过
bool check(int x,int y){
return (x>0 && x<=30 && y>0 && y<=50 && g[x][y]=='0' && dp[x][y]==-1);
}
// 求出每个点到终点的最短路径
void bfs(){
queue<pair<int,int>> q; // 存储每次遍历到的坐标
q.push({30,50});
memset(dp,-1,sizeof(dp)); // 没遍历过的初始化为 -1
dp[30][50]=0;
while(!q.empty()){
pair<int,int> t=q.front(); // 考虑队首元素，注意是元素类型是 pair！！！
q.pop();
for(int i=0;i<4;i++){ // 遍历下、左、右、上
int xi=t.first+x[i];
int yi=t.second+y[i];
if(check(xi,yi)){
dp[xi][yi]=dp[t.first][t.second]+1;
q.push({xi,yi});
}
}
}
}
int main(){
// 1. 输入迷宫
for(int i=1;i<=30;i++)
for(int j=1;j<=50;j++)
cin>>g[i][j]; // 这里不能用 int 存，不知道为啥
// 2. 找每个点到终点的最短路径
bfs();
// 3. 输出答案
string s="";
int i=1,j=1;
while(i!=30 || j!=50){
for(int k=0;k<4;k++){
int xi=i+x[k];
int yi=j+y[k];
if(xi>0 && xi<=30 && yi>0 && yi<=50 && g[xi][yi]=='0' && dp[i][j]-dp[xi][yi]==1){
s+=c[k];
i=xi,j=yi;
break;
}
}
}
cout<<s;
return 0;
}
|
5 RSA解密
题目
RSA 是一种经典的加密算法。它的基本加密过程如下。
首先生成两个质数 p, q，令 n=p×q，设 d 与 (p-1)×(q-1) 互质，则可找到 e 使得 d×e 除 (p-1)×(q-1) 的余数为 1。
n,d,e 组成了私钥，n,d 组成了公钥。
当使用公钥加密一个整数 X 时（小于 n ），计算 $C=X^dmod n$ ，则 C 是加密后的密文。
当收到密文 C 时，可使用私钥解开，计算公式为 $X=C^emod n$ 。
现在你知道公钥中 n=1001733993063167141, d=212353，同时你截获了别人发送的密文 C=20190324，请问，原文是多少？
解析
🟠 【计算 e】
已知 de=kt+1 ，其中 t=(p-1)(q-1) ，需要求 e 。这个人的方法有点笨，她直接穷举 k ，然后算出了 k=174637 ,具体见 f2() 函数。然后她把 t 关于 d 展开， (kt+1) 里面有多少个 d ， e 的值就是多少： e=k·(t/d)+(k·(t%d)+1)/d 。
🟡 【快速计算 $a^b(mod p)$ 】
🟢 【快速计算 $a*b(mod p)$ 】
因为题目中的数字都比较大，如果直接一步步算的话，很容易溢出。这种方法也很好理解，精髓在于把 a 和 b 二进制展开来计算。举个 a=5,b=7,p=3 的例子：
5×7 % 3 = ($2^2+0+2^1$) ($2^2+2^1+2^0$) % 3
= ($2^2+0+2^1$) × $2^2$ % 3 + ($2^2+0+2^1$) × $2^1$ % 3 + ($2^2+0+2^1$) × $2^0$ % 3
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 求 n 除 1 外的最小因数
ll f1(ll n){
int m=pow(n,0.5);
for(int i=2;i<=m;i++){
if(n%i==0)
return i;
}
return -1;
}
// 注意这求的是 k，不是 e！！！
ll f2(ll t,ll d){
ll s=t+1;
ll c=1;
while(s%d!=0){
s=(s%d+t)%d;
c++; // 记录 s 中 t 的个数
}
return c;
}
// 快速求 a*b%n
ll f3(ll a, ll b, ll n){
ll c=0;
while(b){
if(b&1)
c=(c+a)%n;
b>>=1;
a=(a<<1)%n;
}
return c;
}
// 快速求 a^b%n
ll f4(ll a, ll b, ll n){
ll c=1;
while(b){
if(b&1)
c=f3(c,a,n);
a=f3(a,a,n);
b>>=1; // 这里又忘加 "=" 了！！！
}
return c;
}
int main(){
ll n=1001733993063167141;
ll d=212353;
ll c=20190324;
ll q,p,e,x,t,k;
// 1. 求 p,q
p=f1(n); // 891234941
q=n/p; // 1123984201
t=(p-1)*(q-1); // 1001733991047948000
// 2. 求 e
k=f2(t, d); // 174637
e=k*(t/d)+(k*(t%d)+1)/d; // 823816093931522017
// 3. 求 x
x=f4(c,e,n); // 33020213146994036
cout<<x<<endl;
return 0;
}
|
6 完全二叉树的权值
题目
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 $A_1,A_2,…A_N$ ，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
输入描述
第一行包含一个整数 N（1≤N≤$10^5$）。
第二行包含 N 个整数 $A_1,A_2,…A_N (-10^5≤A_i≤10^5)$ 。
输出描述
输出一个整数代表答案。
解析
🟠 【注意超时问题】 一开始用 while(n) 循环，里面又嵌套了一个循环输入每一层的每个节点，结果超时了。 后来改成了用一个 for 循环，计算第 i 个节点所在的层数，虽然循环总次数应该都是 n，但是这种方法不会超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,t,s,max=1;
int sum[10000];
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&t);
s=log(i)/log(2)+1;
sum[s]+=t;
}
for(int i=1;i<=s;i++){
max=sum[max]>sum[i] ? max : i;
}
cout<<max;
return 0;
}
|
7 外卖店优先级
题目
“饱了么"外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中?
输入描述
输入第一行包含两个整数 N 和 K 。
第二行包含 N 个整数 $A_1, A_2,…,A_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
|
#include <bits/stdc++.h>
using namespace std;
struct u{
map<int,int> t; // 表示用户有订单的时刻和订单数量
};
u user[100005];
int main(){
int n,m,t,ts,id,cnt=0;
map<int,int>::iterator it;
cin>>n>>m>>t;
for(int i=0;i<m;i++){ // 输入订单信息
scanf("%d %d",&ts,&id);
(user[id].t[ts])++;
}
for(int i=1;i<=n;i++){
int s=0,t1=0,t2=0,flag=0;
for(it=user[i].t.begin();it!=user[i].t.end();it++){
t1=t2;t2=it->first;
if(s-(t2-t1-1) <0) s=0; // 注意这里的 s 应该减去多少！！！
else s-=(t2-t1-1);
if(s>5) flag=1; // 注意这里也要判断一下！！！
if(s<=3 && flag) flag=0;
s+=(it->second*2);
if(s>5) flag=1;
if(s<=3 && flag) flag=0;
}
if(user[i].t.count(t)!=1)
s-=(t-t2);
if(s>5) flag=1;
if(s<=3 && flag) flag=0;
if(flag) cnt++;
}
cout<<cnt;
return 0;
}
|
8 修改数组
题目
给定一个长度为 n 的数组 $A=[A_1,A_2,…A_n]$ ，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 $A_2,A_3…A_n$ 。
当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1…A_{i-1}$ 中出现过。如果出现过，则小明会给 $A_i$ 加上 1 ；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 1 ，直 到 $A_i$ 没有在 $A_1…A_{i-1}$ 中出现过。
当 $A_n$ 也经过上述修改之后，显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入描述
第一行包含一个整数 n 。
第二行包含 n 个整数 $A_1,A_2,…A_n$ 。
其中，$1≤ n ≤ 10^5, 1≤ A_i ≤ 10^6$ 。
输出描述
输出 n 个整数，依次是最终的 $A_1,A_2,…A_n$ 。
解析
🟠 用 map 等 STL 容器容易超时，这道题不用可以过 80% 的样例，用了只能过 40% 。非必要不使用❗❗❗
🟡 dev 数组开大会爆栈 ❗❗❗ 可以用 static 或者修改分配的栈大小 ❗❗❗
🟢 过80%的简单代码（会超时）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,t;
static int b[1000005]={0}; // 注意这里不用static会爆栈！！！
cin>>n;
for(int i=0;i<n;i++){
cin>>t;
if(b[t]==1){ // 找到第一个没用被用掉的 t
while(b[t]==1) // 这里是超时的原因！！！
t++;
}
b[t]=1; // 这里多了个 "="
cout<<t<<" ";
}
return 0;
}
|
🟣 优化后的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,t;
static int a[1000005]={0};
cin>>n;
for(int i=0;i<n;i++){
cin>>t;
while(a[t]!=0){
a[t]++; // 用 a[t] 记录 t 出现的次数！！！
t+=(a[t]-1); // 加速遍历！！！
}
a[t]++;
cout<<t<<" ";
}
return 0;
}
|
9 糖果
题目
糖果店的老板一共有 m 种口味的糖果出售。为了方便描述，我们将 m 种口味编号 1∼ m。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 k 颗一包整包出售。
幸好糖果包装上注明了其中 k 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定 n 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。
输入描述
第一行包含三个整数 n,m,k。
接下来 n 行每行 k 个整数 $t_1,t_2,…t_k$ ，代表一包糖果的口味。
其中，1≤n≤100, 1≤m≤20, 1≤k≤20, $1≤t_i≤m$ 。
输出描述
输出一个整数表示答案。如果小明无法品尝所有口味，输出 −1。
解析
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
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,k,t;
set<int> s; // 用于判断 n 包糖的总种类数
cin>>n>>m>>k;
int a[105]; // 每包糖的状态
static int dp[1<<20+1]; // 每个状态所需的最小包数
// 1. 输入并存储每包糖的状态
for(int i=1;i<=n;i++){ // 遍历每包糖
int x=0,y;
for(int j=1;j<=k;j++){ // 遍历一包糖的每颗糖
cin>>y;
x |= (1<<(y-1)); // 加上这颗糖的状态
s.insert(y); // 更新总种类
}
a[i]=x;
}
// 2. 判断总共是否有 m 种糖，如果没有则输出 -1 并退出
if(s.size()<m){
cout<< -1; return 0;
}
// 3. 动态规划找出每个状态所需的最小包数
fill(dp,dp+(1<<20)+1,0xffff); // 初始化
dp[0]=0; // 设置 base case
t=(1<<m)-1; // m 个 1
for(int i=1;i<=n;i++){
for(int j=t;j>=0;j--) // 遍历每个状态，决定要不要加这包糖
dp[j|a[i]]=min(dp[j|a[i]],dp[j]+1);
}
cout<<dp[t];
return 0;
}
|
10 组合数问题
菜菜的秘密花园