🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 阅读原文获得更好阅读体验：https://www.eriktse.com/algorithm/1169.html

D. Little Tiger vs. Deep Monkey

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=4815

题意

现在猴子和老虎做同一套题，共有n题($1 \le n \le 40$)，每道题都是二选一。猴子每次都随机选（选对概率1/2）。得分高的获胜，问狮子至少要多少分才能使得胜率至少为p。

分析

这题意给的有点抽象，我们可以发现老虎的做题方式是不知道的，也无需知道，所以我们来对猴子处理出一些东西，我们可以求一个dp数组。

dp[i][j]表示猴子在前i题中恰好获得j分的概率。

因为猴子有一半概率做对，一半概率没做对，所以状态转移方程容易写，我们写正向的更容易理解：

$$dp[i][j] = 0.5 * dp[i-1][j] + 0.5 * dp[i-1][j-a_i]$$

注意后面这一项需要保证j >= a[i]。
。
处理完dp数组后，我们需要知道老虎至少需要多少分才能使得胜率至少为p，也就是说我们现在枚举一个老虎得分x，其胜率应该为dp[n][0] + dp[n][1] + ... + dp[n][x - 1]，即猴子得分不超过x的概率之和。枚举找出最小的x即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50;
const double eps = 1e-6;
int a[N];
double dp[N][N * 1000];

void solve()
{
    int n;double p;cin >> n >> p;
    for(int i = 1;i <= n; ++ i)cin >> a[i];
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    int sum = 0;
    for(int i = 1;i <= n; ++ i)
    {
        sum += a[i];
        for(int j = 0;j <= sum; ++ j)
        {
            dp[i][j] = 0.5 * dp[i - 1][j];
            if(j >= a[i])dp[i][j] += 0.5 * dp[i - 1][j - a[i]];
        }
    }

    double ans = 0.0;
    for(int i = 0;i <= sum; ++ i)
    {
        ans += dp[n][i];//猴子失败的概率
        if(ans + eps >= p)
        {
            cout << i << '\n';
            return;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _;cin >> _;
    while(_ --)solve();
    return 0;   
}

E - Greatest Common Divisor

题目链接：https://codeforces.com/gym/102823/problem/G

题意

给定一个数组，现在有一种操作：将所有数字都+1，问至少操作多少次，可以使得整个数组的gcd大于1。

分析

通过gcd的性质我们知道：

$$gcd(a, b) = gcd(a, a - b), a \ge b$$

于是我们可以先将数组非降序排列，然后做个差分，原数组的gcd就会等于差分数组的gcd。

又因为每次将原数组中的所有元素+1，等价于在查分数组的第一个元素+1而其余元素不动。

所以我们先求一个$g = gcd(d_2, d_3, ..., d_n)$，然后再考虑$d_1$的变化。

所以问题就转化为d[1]需要增加多少才能使得$gcd(d_1, g) > 1$。

我们可以发现，d[1]必须为g的质因子或质因子的倍数，所以我们可以将g分解质因子后逐个求差值然后取小即可。

需要注意对g=0和g=1的特判，无需再考虑n=1，因为n=1时有g=0成立。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 9, inf = 8e18;
int a[N], d[N], kase;

int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}

void solve()
{
    cout << "Case " << ++ kase << ": ";
    int n;cin >> n;
    for(int i = 1;i <= n; ++ i)cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = 1;i <= n; ++ i)d[i] = a[i] - a[i - 1];

    int g = 0;
    for(int i = 2;i <= n; ++ i)g = gcd(g, d[i]);
    if(g == 1)
    {
        cout << -1 << '\n';
        return;
    }

    if(g == 0)
    {
        cout << (a[1] == 1 ? 1 : 0) << '\n';
        return;
    }

    //对g进行质因数分解

    vector<int> v;
    int x = g;
    for(int i = 2;i <= x / i; ++ i)
    {
        if(x % i)continue;
        v.push_back(i);
        while(x % i == 0)x /= i;
    }
    if(x > 1)v.push_back(x);
    int ans = inf;
    for(auto &i : v)ans = min(ans, (i - a[1] % i) % i);
    cout << (ans == inf ? -1 : ans) << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int _;cin >> _;
    while(_ --)solve();

    return 0;
}

F. Array Merge

题目链接：https://codeforces.com/gym/102823/problem/A

题意

给定两个长度分别为n, m的数组a[], b[]，求一种拼接方法得到c[]，使得：

$$\sum_{i=1}^{n+m}c[i]$$

最小。

要求拼接后c[]中a, b内部的元素顺序不变。

例如n=2, m=3时a[1], b[1], a[2], b[2], a[3]是合法的，而a[1], a[3], b[1], a[2], b[2]是不合法的，因为此时a[3]在a[2]左边。

分析

如果不要求内部元素顺序不变，则肯定是将a[], b[]合并后排降序，可以使得式子结果最小（越靠左边的权重越低，所以放较大的数字）。

可现在要求内部元素顺序不变，就不太好搞了。

我们考虑两个相邻区间改变次序造成的影响：

现在有两段相邻的数组，a[i] ~ a[j]和b[l] ~ b[r]。

交换前的贡献为

$$ w1 = 1 * a[i] + 2 * a[i + 1] + ... + (j - i + 1) * a[j] + (j - i + 1 + 1) * b[l] + ... + (j - i + 1 + r - l + 1) * b[r]$$

交换后为

$$w2 = 1 * b[l] + ... + (r - l + 1) * b[r] + (r - l + 1 + 1) * a[i] + .. + (r - l + 1 + j - i + 1) * a[j]$$

我们可以发现

$$w2 - w1 = (r - l + 1) * \sum_{p=i}^{j}a_p - (j - i + 1) * \sum_{p=l}^{r}b_p$$

我们另其大于等于0，也就是使得这次交换有贡献。

$$w2-w1 \le 0$$

等价于：

$$\frac{\sum_{p=i}^{j}a_p}{(j - i + 1)} \le \frac{\sum_{p=l}^{r}b_p}{(r - l + 1)}$$

也就是说一段区间的均值越高，越应该靠前（左边）。

于是我们可以将a, b数组进行分块，即当有左右两块的均值大于左边这块的均值的时候，就应该合并成一大块。

比如下面这个例子：

b分块的时候过程是这样的：{2}均值小于{2, 6}均值，于是{2, 6}合并，{2, 6}均值大于{2, 6, 3}均值，于是{3}单独成一块。

分块后用栈的思想，每次从左边取出均值较大的，计算贡献，直到取完即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 9, inf = 8e18;
int a[N], b[N], kase;

struct Node
{
    int sum, cnt;
    Node(){sum = 0, cnt = 0;}
    Node(int a, int b){sum = a, cnt = b;}
    bool operator < (const Node &m)const
    {
        return sum * m.cnt < m.sum * cnt;
    }
    bool operator > (const Node &m)const
    {
        return m < *this;
    }
    Node operator + (Node m)
    {
        Node res;
        res.sum = sum + m.sum, res.cnt = cnt + m.cnt;
        return res;
    }
}sa[N], sb[N];

int ta, tb;

int f(int a[], int l, int r, int k)
{
    int res = 0;
    for(int i = l;i <= r; ++ i, ++ k)res += a[i] * k;
    return res;
}

void solve()
{
    cout << "Case " << ++ kase << ": ";
    int n, m;cin >> n >> m;

    for(int i = 1;i <= n; ++ i)cin >> a[i];
    for(int i = 1;i <= m; ++ i)cin >> b[i];
    ta = tb = 0;

    for(int i = 1;i <= n; ++ i)
    {
        Node x = Node(a[i], 1);
        while(ta && x + sa[ta] > sa[ta])x = x + sa[ta --];
        sa[++ ta] = x;
    }

    for(int i = 1;i <= m; ++ i)
    {
        Node x = Node(b[i], 1);
        while(tb && x + sb[tb] > sb[tb])x = x + sb[tb --];
        sb[++ tb] = x;
    }

    int i = 1, j = 1, ca = 1, cb = 1, ans = 0;
    while(i <= ta && j <= tb)
    {
        if(sb[j] < sa[i])
        {
            ans += f(a, ca, ca + sa[i].cnt - 1, ca + cb - 1);
            ca += sa[i].cnt;
            i ++;
        }else
        {
            ans += f(b, cb, cb + sb[j].cnt - 1, ca + cb - 1);
            cb += sb[j].cnt;
            j ++;
        }
    }
    while(i <= ta)
    {
        ans += f(a, ca, ca + sa[i].cnt - 1, ca + cb - 1);
        ca += sa[i].cnt;
        i ++;
    }
    while(j <= tb)
    {
        ans += f(b, cb, cb + sb[j].cnt - 1, ca + cb - 1);
        cb += sb[j].cnt;
        j ++;
    }
    cout << ans << '\n';

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int _;cin >> _;
    while(_ --)solve();

    return 0;
}