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$可以写成记忆化搜索的形式, 所以这题也可以写搜索