关于acm:ACM算法竞赛日常训练DAY2题解与分析比赛数学考试简单瞎搞题

101次阅读

共计 2372 个字符，预计需要花费 6 分钟才能阅读完成。

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 long
using 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 long
using 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 long
using 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 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬

正文完