Zth's Blog

记录学习路上的点滴

0%

csp202109

csp认证2021年九月部分题解

202109-1.数组推导

题意

设有一长度为$n$的数组$A$, 给出数组$B$表示数组$A$的前缀最大值, 即

设$sum$表示$\sum_{i = 1}^n A_i$, 求$sum$可能的最大值和最小值

数据范围

$n \leq 100, 0 \leq B_i \leq 10^5$

题解

分两种情况来考虑

  1. $B_i > B_{i - 1}$

    此时的$A_i$必须等于$B_i$, $sum$的最大最小值都要加$B_i$

  2. $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; // mxs表示sum最大值, mns表示sum最小值

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;
}

202109-2.非零段划分

题意

给出一个长度为$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 ++) // 枚举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$加入到并查集中, 分三种情况

  1. $A_{i + 1}, A_{i - 1}$都不在并查集中

    此时$A_i$新开辟了一个段落, $ans ++$

  2. $A_{i + 1}, A_{i - 1}$都在并查集中

    此时$A_i$连接了两个并查集, 并查集数量$- 1$, $ans —$

  3. $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]; // 判断a[i]是否在并查集内
int ans, res;
std:: vector<int> pos[10004]; // 存放a[i] = p的所有i, 方便找位置

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 --) // 枚举p
{
for(int j = 0; j < pos[i].size(); j ++) // 找到a[i]
{
int p = pos[i][j];
// 更新res
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;
}

202109-4.收集卡牌

题意

抽卡游戏, 有$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$

考虑状态的设计

  1. 既然是抽卡次数的期望, 那么把次数加进状态里

  2. 状态压缩, 鉴于状态用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]; // dp状态
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); // 预处理出每一个状态中1的个数

dp[0][0] = 1.00000000; // dp数组初始化

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) // 如果状态中本次抽到的卡为0, 那么显然无法转移
dp[i][j] += (dp[i - 1][j] + dp[i - 1][j - (1 << l)]) * p[l]; // 两种转移路径, i - 1次中抽到或没抽到过第l张卡

if(cnt[j] + (i - cnt[j]) / k == n) // 抽卡可以立即结束
ans += dp[i][j] * (long double)i, dp[i][j] = 0; // 统计答案, 抽卡结束的标志即为dp[i][j] = 0, 无法向其他状态转移, 不写这句会出错
}

printf("%.10Lf\n", ans); // 控制输出为小数点后10位

return 0;
}

$dp$可以写成记忆化搜索的形式, 所以这题也可以写搜索