难度：
签到：A
简单：CDGH
中等偏下：EFI
中等偏上：BJKL
A.阿宁的签到题
题意：
在这次寒假集训营中每一个题都有一个难度评分x。
题目分为以下等级：
very easy (1≤x≤7)
easy (7<x≤233)
medium (233<x≤10032)
hard (10032<x≤114514)
very hard (114514<x≤1919810)
can not imagine (1919810<x)
你拿到这次寒假集训营其中的一道题，并且对它评估了一个分数，请你根据以上划分输出等级
数据范围：
$$1 \leq x < 2^{31}$$
题解：模拟
按题目
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void JiuCherish(){
int n;
std::cin >> n;
if(n >= 1 and n <= 7) {
std::cout << "very easy" << endl;
} else if(n > 7 and n <= 233) {
std::cout << "easy" << endl;
} else if(n > 233 and n <= 10032) {
std::cout << "medium" << endl;
} else if(n > 10032 and n <= 114514) {
std::cout << "hard" << endl;
} else if(n > 114514 and n <= 1919810) {
std::cout << "very hard" << endl;
} else {
std::cout << "can not imagine" << endl;
}
}
|
B.阿宁的倍数
题意：
阿宁有一个长度为 n 的数组 a，下标从 1 开始，有 q 次操作。
修改操作：数组末尾增加一个数 x，数组长度加 1 。
询问操作：有多少个 i(i>x) ，满足 ai 是 ax 的倍数？
数据范围：
$$1 \leq n,q,a_i \leq 2\times 10^5$$
$$1 \leq op \leq 2$$
题解：
C. 阿宁的大背包
题意：
本质是杨辉三角：给你一个排列，按杨辉三角计算，问最后输出的那个背包最大值可以是多少。
数据范围：
$$1 \leq n \leq 10^3$$
题解：构造，暴力
考虑前n / 2为1，3，5，7…..，后面为6，4，2…构造即可。
代码
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
| void JiuCherish(){
int n;
std::cin >> n;
i64 ans = 0;
int w = n;
std::vector<i64> a;
if(!(n & 1)){
for(int i=0;i<n / 2;i++) {
i64 now = 2 * i + 1;
a.pb(now);
c[i] = now;
}
int ww = 0;
for(int i=n / 2;i<n;i++) {
i64 now = n - ww * 2;
c[i] = now;
a.pb(now);
ww++;
}
} else {
for(int i=0;i<=n / 2;i++) {
i64 now = 2 * i + 1;
a.pb(now);
c[i] = now;
}
int ww = n - 1;
for(int i=n/2 + 1;i<n;i++) {
a.pb(ww);
c[i] = ww;
ww -= 2;
}
}
std::vector<i64> b;
int cnt = 0;
while(1) {
if(a.size() <= 1) {
break;
}
b.clear();
for(int i=0;i<SZ(a) - 1;i++) {
b.pb((a[i] + a[i + 1]) % MOD);
}
a.clear();
for(int i=0;i<SZ(b) - 1;i++) {
a.pb((b[i] + b[i + 1]) % MOD);
}
}
if(!(n & 1))
std::cout << b[0] << endl;
else
std::cout << a[0] << endl;
for(int i=0;i<n;i++) {
std::cout << c[i] << ' ';
}
}
|
D.阿宁的毒瘤题
题意：
给定一个长度为 n 且仅有小写字母的字符串 s, 问 s 串的 “udu” 子序列的个数、
现在需要通过修改其中 s 串的一个字符（也可以不修改），使得修改后上面子序列的个数达到最小。
子序列定义：从原串的顺序取一些字符，组成新的字符串，例如”dudu”、”udu”是”dudovoudu”的子序列，而”uudd”不是。
题解：贡献
计算出每个位置的贡献，最后把贡献最大的替换掉即可。
代码
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
| void JiuCherish(){
std::string s;
std::cin >> s;
int n = s.size();
vector<i64> preU(n + 5),preUD(n + 5),afU(n + 5),afUD(n + 5),val(n + 5);
for(int i=1;i<=n;i++) {
preU[i] += preU[i - 1] + (s[i - 1] == 'u');
preUD[i] += preUD[i - 1] + (s[i - 1] == 'd' ? preU[i - 1] : 0);
}
for(int i=n;i>=1;i--) {
afU[i] += afU[i + 1] + (s[i - 1] == 'u');
afUD[i] += afUD[i + 1] + (s[i - 1] == 'd' ? afU[i + 1] : 0);
}
i64 mx = 0,idx = 0;
for(int i=1;i<=n;i++) {
if(s[i - 1] == 'u') {
val[i - 1] = preUD[i - 1] + afUD[i + 1];
} else if(s[i - 1] == 'd') {
val[i - 1] = preU[i - 1] * afU[i + 1];
}
}
for(int i=0;i<n;i++) {
if(val[i] > mx) {
mx = val[i];
idx = i;
}
}
s[idx] = 'z';
cout << s;
}
|
E.阿宁的生成树
题意：
给你一个 n 节点的完全图，编号从 1 到 n 。对于点 i, j （i < j），如果 j - i <= k , 那么 i 和 j 之间有一条边权为 lcm(i,j) 的边，否则有一条边权为 gcd(i,j) 的边。
试求出该完全图的最小生成树。
数据范围：
$$1 \leq n,k \leq 2 \times 10^5$$
F.阿宁的二进制
G.阿宁的整数配对
H.阿宁讨伐虚空
I. 阿宁前往沙城
J.阿宁指指点点
K.阿宁大战小红
L.阿宁睡大觉