csp认证2021年九月部分题解
题意
设有一长度为$n$的数组$A$， 给出数组$B$表示数组$A$的前缀最大值， 即
设$sum$表示$\sum_{i = 1}^n A_i$， 求$sum$可能的最大值和最小值
数据范围
$n \leq 100, 0 \leq B_i \leq 10^5$
题解
分两种情况来考虑
$B_i > B_{i - 1}$
此时的$A_i$必须等于$B_i$， $sum$的最大最小值都要加$B_i$
$B_i = B_{i - 1}$
此时的$A_i$可以是0到$B_i$之间的任何一个整数， $sum$最小时$A_i = 0$, $sum$最大时$A_i = B_i$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <cstdio>
int n;
int b[102];
int mxs, mns;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
for(int i = 1; i <= n; i ++)
{
mxs += b[i];
if(b[i] > b[i - 1]) mns += b[i];
}
printf("%d\n%d\n", mxs, mns);
return 0;
}
|
题意
给出一个长度为$n$的非负整数序列$A$， 你可以选择一个$p$， 让所有的$A_i < p$变成零， 求如何选取$p$使得得到的非零段数量最多， 最后只要输出答案的数量即可， 不要求给出$p$
数据范围
$70\%$数据满足$n \leq 1000$
$100\%$数据满足$n \leq 5 \times 10^5, 0 \leq A_i \leq 10^4$
题解
70分做法
暴力的枚举$p$, 求答案， 时间复杂度$O(n \times p)$
代码
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 <iostream>
#include <cstdio>
int n;
int a[500005];
int ans;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int p = 0; p <= 10000; p ++)
{
int res = 0;
for(int i = 1; i <= n; i ++)
if(a[i] >= p && a[i - 1] < p)
res ++;
ans = std:: max(ans, res);
}
printf("%d\n", ans);
return 0;
}
|
100分做法
题意转化为大于等于$p$的连续子段的数量的最大值， 那么我们很容易可以想到其中的递推关系， $p$的答案可以由$p + 1$转移而来， 即在$p + 1$状态的基础上将所有的$A_i = p$添加进状态里
利用并查集思想， 我们倒序枚举$p$， 每次将所有的$A_i = p$加入到并查集中， 分三种情况
$A_{i + 1}, A_{i - 1}$都不在并查集中
此时$A_i$新开辟了一个段落， $ans ++$
$A_{i + 1}, A_{i - 1}$都在并查集中
此时$A_i$连接了两个并查集， 并查集数量$- 1$， $ans —$
$A_{i + 1}, A_{i - 1}$中有且仅有一个在并查集中
并查集数量不变， 大小改变， $ans$不变
代码
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 <iostream>
#include <cstdio>
#include <vector>
int n;
int a[500005];
bool in[500005];
int ans, res;
std:: vector<int> pos[10004];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
pos[a[i]].push_back(i);
}
for(int i = 10000; i >= 1; i --)
{
for(int j = 0; j < pos[i].size(); j ++)
{
int p = pos[i][j];
if(!in[p - 1] && !in[p + 1]) res ++;
if(in[p - 1] && in[p + 1]) res --;
in[p] = true;
}
ans = std:: max(ans, res);
}
printf("%d\n", ans);
return 0;
}
|
题意
抽卡游戏， 有$n$种卡牌， 每次抽卡， 获得第$i$张卡牌的概率为$p_i$， 如果你抽到一张已抽到过的卡牌， 这张卡牌会转换为一枚硬币， 你可以用$k$枚硬币换一张你没有获得过的卡牌
$PS:$你会把硬币攒在手里， 等能够通过兑换获得所有卡牌时， 一次性兑换并停止抽卡
求获得所有$n$种卡牌的期望抽卡次数
数据范围
$20\%$数据， $1 \leq n, k \leq 5$
另外$20\%$数据， 所有$p_i$均相等
$100\%$数据， $1 \leq n \leq 16, 1 \leq k \leq 5, p_i \geq \frac{1}{10000}, \sum_{i = 1}^n p_i = 1$
题解
这显然是一道期望$dp$题， 那么我们的$dp$数组表示的肯定是概率， 再看一眼数据范围， 极有可能是状压$dp$
考虑状态的设计
既然是抽卡次数的期望， 那么把次数加进状态里
状态压缩， 鉴于状态用0和1来表示， 只能表示每种卡是否获得过
这个题目中还有另外一个设定， 那就是可以用$k$枚硬币换一张卡牌， 那我们还需要手中的硬币数量这个参数， 但是仔细一想， 我们知道了当前抽卡的次数， 也知道了当前哪些卡被抽到过（即已抽到了多少种卡）， 这两个一减不就是手中的硬币数量吗？
举个例子， 你当前抽了$i$次卡， 抽到的卡状态为$j$, 假设$j$中已抽到的卡用1来表示， 并且$j$中含有$cnt[j]$个1
那么我们手中的硬币数量就一定是$i - cnt[j]$
那么我们就可以很容易的设计出$dp$状态了， 设$dp[i][j]$为当前抽了$i$张卡， 抽到的卡组成的状态为$j$的概率
具体转移看代码
另外据说ccf的评测机， 没有spj， 要输出小数点后10位才可以， 而且本题精度要求较高， 需要使用long double
代码
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
| #include <iostream>
#include <cstdio>
int n, k;
long double p[21];
int cnt[1 << 17];
long double dp[102][1 << 17];
long double ans; 答案
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) scanf("%Lf", &p[i]);
int m = n * k, s = 1 << n;
for(int i = 0; i < s; i ++)
for(int j = 0; j < n; j ++)
cnt[i] += ((i >> j) & 1);
dp[0][0] = 1.00000000;
for(int i = 1; i <= m; i ++)
for(int j = 0; j < s; j ++)
{
for(int l = 0; l < n; l ++)
if((j >> l) & 1)
dp[i][j] += (dp[i - 1][j] + dp[i - 1][j - (1 << l)]) * p[l];
if(cnt[j] + (i - cnt[j]) / k == n)
ans += dp[i][j] * (long double)i, dp[i][j] = 0;
}
printf("%.10Lf\n", ans);
return 0;
}
|
$dp$可以写成记忆化搜索的形式， 所以这题也可以写搜索