AcWing 第 114 场周赛

AcWing 5056. 2的整数次幂

可以运用位运算

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        if((n & (n - 1)) == 0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

AcWing 5057. 截断数组

利用前缀和来快速计算两个子数组的和,由于2≤n≤1e5，1≤ai≤1e6。前缀和会爆int, 所以需要开longlong

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e5+10;

ll a[N], s[N];

int main() {

    int n, p;
    cin >> n >> p;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    int mx = 0;
    for(int i = 1; i < n; i++) {
        int res = (s[i] % p) + ((s[n] - s[i]) % p);
        mx = max(mx, res);
    }
    cout << mx << endl;
    return 0;
}

AcWing 5058. 双色球

1.思考如何朴素的计算出约翰获胜的概率？

假设白球有n个，黑球有m个，且约翰和贝茜依次抽取完一次为一轮，从白球有n个，黑球有m个开始抽取，我们计算最多可以抽取多少轮，直到无法抽取，或特殊情况。我们枚举第i轮约翰抽取到了白球的概率pi，再求出总的概率相加，p=p1+p2+p3+....+pi+....

2.每一个pi如何求得呢？

假设有i个白球，j个黑球，约翰第一轮就抽中白球的概率为p1 = i / (i / j).。 如果第一次没有抽中，第二次才抽中，概率就为p2，这个有一个隐藏的信息就是如果约翰第二轮抽中则贝茜第一轮没有抽中白球，但是由于贝茜抽完会掉出一个球，就需要分类讨论第一轮掉的那一个球是白球还是黑球

• 情况1：为约翰第一轮没有抽中的概率乘以贝茜第一轮抽中黑球的概率乘以掉的球为一个白球的概率乘以约翰第二次抽中球的概率

(情况1)p = j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * i / (i + j - 3)

• 情况2：为约翰第一轮没有抽中的概率乘以贝茜第一轮抽中黑球的概率乘以掉的球为一个黑球的概率乘以约翰第二次抽中球的概率

(情况2)p = j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * i / (i + j - 3)

p2 = 情况1 + 情况2
再通过第二次没抽中的状态下写出p3我们可以发现这是一个递归计算，状态转移，这个概率可以通过递归计算或者动态规划来求解

3.如何求得递推关系式？

如果我们一个一个计算p1,p2,..pi，我们必须要知道pi的前一个pi-1的白黑球的状态，这样就会很麻烦，我们可以定义一个记忆化二维数组f[N][N], f[i][j]表示i个白球，j个黑球下约翰获胜的概率，我们只需要考虑在当前情况下的第一轮抽中和第二轮抽中

• 第一轮抽中：p = i / (i + j)

• 第二轮抽中：分贝茜第一轮掉落球的情况

  • 掉落黑球(少了3个黑球)： p = j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j-3]
  • 掉落白球(少了1个白球和两个黑球)： p = j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i-1][j-2]
    递推关系式就出来了

f[i][j] = i / (i + j) + j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j-3] + j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i-1][j-2]

再考虑一下数组越界和特殊情况即可
没有黑球约翰必赢,白球为0除外，需要初始化f[i][0]全为1

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip> 

using namespace std;

const int N = 1010;

double f[N][N];

int main() {

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) f[i][0] = 1; // 没有黑球约翰必赢,白球为0除外
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            double M = i + j;
            f[i][j] = (double) i / M;
            if(i >= 1 && j >= 2) f[i][j] += j / M * (j - 1) / (M - 1) * i / (M - 2) * f[i-1][j-2]; 
            if(j >= 3) f[i][j] += j / M * (j - 1) / (M - 1) * (j - 2) / (M - 2) * f[i][j-3];
        }
    }
    cout << setprecision(9) << f[n][m] << endl;
    return 0;
}