DAY2共三题：
- 较量（概率）
- 数学考试（前缀和与思维）
- 简略瞎搞题（dp）
视频解说：https://www.bilibili.com/video/BV1hP411o7RD/
作者：Eriktse
简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）
集体博客：www.eriktse.com
较量
- tag: 概率
传送门：https://ac.nowcoder.com/acm/problem/14734
咱们设对于每一道题：
- 事件A：本人做对了
- 事件B：听右边的，做对了
- 事件C：听左边的，做对了
三个事件的概率都曾经给出了，别离是$P(A), P(B), P(C)$。
设事件Y：该题做对了
咱们能够晓得事件$Y=A \cup B \cup C$，如果要正向求解$Y$是有肯定难度的，因为这里的$Y$实际上由7个最小项形成，而事件$\overline{Y}$仅有一个最小项形成（这里就不开展说了）。
容易失去表达式：
$$P(Y) = 1 - (1-P(A))(1-P(B))(1-P(C))$$
而后咱们能够枚举所有的序列，而后算一下以后这个情景对答案的奉献。
枚举序列能够用二进制数枚举，也能够用dfs，用dfs的话有个益处就是能够剪枝。
二进制枚举可能常数小点。
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 20;double a[maxn], b[maxn], c[maxn];double ans[maxn];double getp(int k){ return max(0.0, 1.0 - (1 - a[k]) * (1 - b[k]) * (1 - c[k]));}void dfs(int dep, int cnt, double p){ if(p == 0)return; if(dep == 13) { ans[cnt] += p; return; } //没对第i题 dfs(dep + 1, cnt, p * (1.0 - getp(dep))); //对了第i题 dfs(dep + 1, cnt + 1, p * getp(dep));}signed main(){ for(int i = 1;i <= 12; ++ i)scanf("%lf", a + i); for(int i = 1;i <= 12; ++ i)scanf("%lf", b + i); for(int i = 1;i <= 12; ++ i)scanf("%lf", c + i); //for(int i = 1;i <= 12; ++ i)printf("p[%lld] = %.2lf\n", i, getp(i)); dfs(1, 0, 1); for(int i = 0;i <= 12; ++ i)printf("%.6f\n", ans[i]); return 0;}数学考试
- tag: 前缀和，思维
传送门：https://ac.nowcoder.com/acm/problem/15553
这道题比较简单，咱们先解决出一个前缀和，而后从后往前去枚举左区间的左端点，而后更新答案即可。不须要晓得具体的右区间，只须要晓得右区间和取值的最值即可。
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 2e5 + 9, inf = 8e18;int a[maxn], prefix[maxn];void solve(){ int n, k;scanf("%lld %lld", &n, &k); for(int i = 1;i <= n; ++ i)scanf("%lld", a + i); for(int i = 1;i <= n; ++ i)prefix[i] = prefix[i - 1] + a[i]; int ans = -inf; int mx = prefix[n] - prefix[n - k]; for(int i = n - 2 * k + 1;i >= 1; -- i) { //将[i, i + k - 1]区间作为左区间更新答案 ans = max(ans, mx + prefix[i + k - 1] - prefix[i - 1]); //将区间[i + k - 1, i + 2 * k - 1]增加进右区间的汇合中取大 mx = max(mx, prefix[i + 2 * k- 1] - prefix[i + k - 1]); } printf("%lld\n", ans);}signed main(){ int _;scanf("%lld", &_); while(_ --)solve(); return 0;}简略瞎搞题
- tag: dp，bitset
传送门：https://ac.nowcoder.com/acm/problem/17193
不会应用bitset的同学能够看这篇文章：https://www.eriktse.com/technology/1073.html
咱们定义一个bitset b，其中b[i]若为1示意能够组成平方和为i的答案。
留神这里要用一个全0的新bitset s来存下b左移后的后果，而后再让b = s，否则可能会呈现大量的错误计算。
背包dp，具体看代码吧不难理解。
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 1e6 + 9;signed main(){ int n;scanf("%lld", &n); bitset<maxn> b; b[0] = 1; for(int i = 1;i <= n; ++ i) { int l, r;scanf("%lld %lld", &l, &r); bitset<maxn> s; for(int j = l;j <= r; ++ j) { s |= (b << (j * j)); } b = s; } printf("%lld\n", b.count()); return 0;}本文由eriktse原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言