⏰总用时：177/ 🎯总分：0/150
| 题号 |
时间 |
结果 |
满分 |
难度 |
备注 |
| 1 |
20 |
❌ |
5 |
🌕 |
🔸【计算一个整数各位上的数字】：当 i/10!=0 时，不断取出 i%10 。 |
| 2 |
7 |
❌ |
5 |
🌕 |
🔹 确定一条直线要考虑斜率和截距 |
| 3 |
40 |
❌ |
10 |
🌓 |
🔸 整数问题常用【取模】 |
| 4 |
35 |
❌ |
10 |
🌕 |
🔹 二维数组太大容易引起报错：program received signal sigsegv, segmentation fault. （本题中用 int g[2022][2022]; 就报错了QAQ） |
| 5 |
45 |
❌ |
10 |
🌑 |
🔸 状压dp
🔸 移位操作较多，容易出错 |
| 6 |
25 |
❌ |
15 |
🌓 |
🔹 用迭代器循环时不能修改 set 内元素 |
| 7 |
5 |
❌ |
20 |
🌓 |
🔸 【博弈论】重点是判断必胜 |
| 8 |
|
|
20 |
|
|
| 9 |
|
|
25 |
|
|
| 10 |
|
|
25 |
|
|
1 【填空】卡片
题目
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 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
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[10]={2021,2021,2021,2021,2021,2021,2021,2021,2021,2021}; // 每个数字还剩的卡片数
for(int i=1;;i++){
int t=i/10, s=i%10;
while(t){
if(a[s]<=0){
cout<< i-1;
return 0;
}
else a[s]--;
s=t%10;
t=t/10;
}
if(a[s]<=0){
cout<<i-1;
return 0;
}
else a[s]--; // 这里还是 a[s]--，不是 a[t]！
}
return 0;
}
|
2 【填空】直线
题目
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点 (x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z，即横坐标 是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。
给定平面上 20×21 个整点 (x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即横 坐标是 00 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之 间的整数的点。
请问这些点一共确定了多少条不同的直线。
解析
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;
int main(){
map<pair<double,double>,bool> s;
for(int x1=0;x1<20;x1++){
for(int y1=0;y1<21;y1++){
for(int x2=0;x2<20;x2++){
if(x1==x2) continue;
for(int y2=0;y2<21;y2++){
double k=1.0*(y2-y1)/(x2-x1);
double b=1.0*(x2*y1-x1*y2)/(x2-x1);
s[{k, b}]=1; // 确定一条直线要考虑斜率和截距！！！
}
}
}
}
cout<< s.size()+20; // 最后加上斜率不存在的情况
return 0;
}
|
3 【填空】货物摆放
题目
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n=L×W×H。
例如，当 n=4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
请问，当 n=2021041820210418 （注意有 16 位数字）时，总共有多少种方案？
解析
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
|
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
set<long long> s; // 存储 2021041820210418 的所有因数
// 计算出 2021041820210418 的所有因数
void geti(long long x){
long y=pow(x,0.5);
for(long i=1;i<=y;i++){ // 只用遍历到 y，因为另一半是对称的
if(x%i==0){
s.insert(i);
s.insert(x/i); // 要记得把对称的另一半数字也添上去
}
}
return;
}
int main(){
// 1. 计算出 2021041820210418 所有因数
long long num=2021041820210418;
int cnt=0;
geti(num);
// 2. 遍历因数
cout<<s.size()<<endl;
for(const auto &i:s){
for(const auto &j:s){
if(num%(i*j)==0) // 只要 i*j 还是 num 的因数就符合
cnt++;
}
}
cout<<cnt;
return 0;
}
|
4 【填空】路径
题目
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
解析
🟠 这题是典型的【动态规划】。用 dp[j] 来记录点 1到点 j 的最小距离，初始化为一个不可能的取值：-1。
🟡 由题目定义，当 j∈[ 2, 22 ] 时，点 1 到点 j 的最小距离就是他们的最大公倍数 j 。
🟢 当 j∈[23, 2021] 时，点 1 到点 j 没有直接边，因此路径 ( 1, j ) 只能由中间点 i 实现，且点 i 到点 j 有直接边。即： dp[j]=min(dp[j], dp[i]+gbs(i,j))，i ∈[ j-21, j-1 ]
🔵 求 (a, b) 的最小公倍数：考虑大数，将大数挨个乘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
|
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int gbs(int a,int b){ // 求 a b 的最小公倍数
int c=max(a,b),t=c,d=min(a,b);
while(c%d)
c+=t;
return c;
}
int main(){
int dp[2022];
for(int j=0;j<=2021;j++) // 1 到每个点都初始化为一个不可能的取值
dp[j]=-1;
for(int j=2;j<=22;j++) // 1 到附近的 21 个点的最小值就是这个点的值
dp[j]=j;
for(int j=23;j<=2021;j++){
for(int i=j-21;i<j;i++){
if(dp[j]==-1)
dp[j]=dp[i]+gbs(i,j);
else dp[j]=min(dp[j], dp[i]+gbs(i,j));
}
}
cout<<dp[2021];
return 0;
}
|
5 回路计数
题目
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？
两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。
解析
🟠 【状压dp】 用 dp[i][j] 表示从 1 走到 j 且状态为 i 的方案数。其中 i 的二进制第1-21位分别表示是否经过该教学楼。
🟡 遍历每一种状态 i 和教学楼 j，若该状态经过该教学楼，则看这条路径是否可以由中转点 k 得到，即 i 是否满足 1→k→j，若满足则有转移方程 dp[i][j]+=dp[i-(1<<j)][k] 。注意经过 k 时还未经过 j 。
🔵 代码中移位操作较多，易出错。 此种方法需要运行好几秒，将 1 ~ 21 映射成 0 ~ 20 据说会快一点。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int n=22,m=1<<n;
ll dp[m][n]; // dp[i][j]：从 1 走到 j 且状态为 i 的方案数
bool e[n][n]; // 记录两点间是否连通
int main(){
// 判断两点间是否连通
memset(e,0,sizeof(e));
for(int i=1;i<n;i++){
for(int j=i+1;j<n;j++)
if(__gcd(i,j)==1)
e[i][j]=e[j][i]=1;
}
// 动态规划
dp[2][1]=1;
for(int i=2;i<=m-2;i++){ // 遍历每一种状态
for(int j=1;j<n;j++){ // 遍历每一个教学楼
if(i>>j & 1){ // 这个方案 i 经过了 j
for(int k=1;k<n;k++){ // 遍历每一个中转教学楼
if(i>>k&1 && e[j][k]) // 这个状态可以经过教学楼 k 中转达到
dp[i][j]+=dp[i-(1<<j)][k]; // 加上通过 k 到达 j 的方案数
}
}
}
}
// 合并倒数第二步落在各个教学楼的所有可能
ll ans=0;
for(int i=2;i<n;i++)
ans+=dp[m-2][i];
cout<<ans;
return 0;
}
|
6 砝码称重
题目
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 $W_1, W_2,…W_N$ 。
请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N 。
第二行包含 N 个整数：$W_1, W_2,…W_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
|
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main(){
int n,w[100],x,y;
set<int> s;
set<int>::iterator it; // 注意这个写法！
cin>>n;
for(int i=0;i<n;i++){
cin>>w[i];
}
s.insert(0);
for(int i=0;i<n;i++){
set<int> t=s;
for(it=t.begin();it!=t.end();it++){ // 用迭代器循环时不能修改 set 内元素！
s.insert(*it + w[i]);
s.insert(abs(*it - w[i]));
}
}
cout<<s.size()-1<<endl;
return 0;
}
|
7 异或数列
题目
Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 a 和 b，初始值均为 0。
有一个给定的长度为 n 的公共数列 $X_1,X_2,…,X_n$ 。Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：
选项 1：从数列中选一个 $X_i$ 给 Alice 的数异或上，或者说令 a 变为 a ⊕ $X_i$ 。（其中 ⊕ 表示按位异或）
选项 2：从数列中选一个 $X_i$ 给 Bob 的数异或上，或者说令 b 变为 b ⊕ $X_i$ 。
每个数 $X_i$ 都只能用一次，当所有 $X_i$ 均被使用后（n 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。 现在双方都足够聪明，都采用最优策略，请问谁能获胜？
输入格式
每个评测用例包含多组询问。询问之间彼此独立。
输入的第一行包含一个整数 T，表示询问数。
接下来 T 行每行包含一组询问。其中第 i 行的第一个整数 $n_i$ 表示数列长度，随后 $n_i$ 个整数 $X_1,X_2,…,X_{ni}$ 表示数列中的每个数。
输出格式
输出 T 行，依次对应每组询问的答案。 每行包含一个整数 1、0 或 −1 分别表示 Alice 胜、平局或败。
解析
🟠 【博弈论】 考虑好所有输赢的可能
✔ 只需考虑这最高位上 1 的个数。 我们用数组 a[20] 存储每位上 1 的个数，设最高位为 i 。
✔ 当 a[i]=1 时，先手赢。因为先手只要拿走这个数，最终异或的结果必定大于后手。
✔ 当 a[i] 为奇数、 n 为奇数时，先手赢。
✔ 当 a[i] 为奇数、 n 为偶数时，后手赢。
✔ 当 a[i] 为偶数时，最终这一位上二者会相同，继续看下一位。
🟡 我们用 sum 记录 n 个数的异或，若 sum=0 ，那么必然平局。（相当于每位上 1 的个数都为偶数）
🔵 注意在计数时不要忘记判断 if(x&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
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <bits/stdc++.h>
using namespace std;
int t,n,x,a[20]; // 存储一组数中每位的个数
void count(int x){ // 计算数 x 每位的 1 的个数
int cnt=0;
while(x){
if(x&1) a[cnt]++; // 注意只有这一位为1时，计数器才加一！！！
cnt++;
x=x>>1;
}
}
int main(){
scanf("%d",&t);
while(t>0){
t--;
scanf("%d",&n);
// 计算这 n 个数每位 1 的个数
int sum=0;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
scanf("%d",&x);
sum=sum^x;
count(x);
}
// 如果这 n 个数异或为0，那么平局
if(sum==0){
cout<<"0"<<endl;continue;
}
// 判断最高位
for(int i=19;i>=0;i--){
if(a[i]==1){ // 最高位只有1个1，先手赢
cout<<"1"<<endl;break;
}
else if(a[i]%2==1 && n%2==1){ // 最高位有奇数个1，总数为奇数，先手赢
cout<<"1"<<endl;break;
}
else if(a[i]%2==1 && n%2==0){ // 最高位有奇数个1，总数为偶数，后手赢
cout<<"-1"<<endl;break;
} // 最高位有偶数个1时，最终会被抵消，继续判断下一位
}
}
return 0;
}
|
8 左孩子右兄弟
9 括号序列
10 分果果
菜菜的秘密花园