Codeforces Round #737 (Div. 2)部分题解_codeforces737 div2

A题

题目陈述

陈述：将一个数组分成两个子序列，求两个子序列单独平均值的和的最大值

思路and证明

• 证明如下：
• A1,A2,A3…An（没有最大值）
  Amax
  现在从第一个集合选一个数k到第二个集合
• if k>avg(第一个集合）显而易见，第一个集合的avg1减少，第二个avg2也减少，总体必然减少
• else 第一个集合ave增加，第二个集合ave2减少，需要证明：增加的不如减少的多
• 如下图，(解析法反推回来,懒得写全了
  
• 所以一个集合最大数，其余第二个集合，即为正解

代码

    int x, mx;
    LL sum;
    double ave, ans;
    cin >> T;
    while (T--)
    {
        cin >> n;
        sum = 0;
        mx = -1e9;
        for (int i = 1; i <= n; i++)
        {
            cin >> x;
            if (x > mx)
                mx = x;
            sum += x;
        }
        ans = (double)(sum - mx) / (n - 1) + mx;
        printf("%.9lf\n", ans);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

B题

题目陈述

• 给定一个n个数的数组，是否能将其分为k个子序列，然后对这个子序列进行排序，得到一个递增的序列

思路

• 离散化处理，变成1~n
• 可以理解成为拼图，每一块是原序列一块拼图，如果x[i-1]+1==x[i]则需要多加一块拼图，反之则不需要
• 最后拼图总数tot<=k则是yes，反之是no

代码

    cin >> T;
    while (T--)
    {
        int tot = 0;
        cin >> n >> k;
        vci x(n), y(n);
        for (int i = 0; i < n; i++)
        {
            cin >> x[i];
        }
        y = x;
        sort(y.begin(), y.end());
        for (int i = 0; i < n; i++)
        {
            x[i] = lower_bound(y.begin(), y.end(), x[i]) - y.begin();
            //查询这个数在数组中是第几小的，离散化
        }
        reverse(x.begin(), x.end());
        x.pb(2e9);
        reverse(x.begin(), x.end());
        for (int i = 1; i <= n; i++)
        {
            if (x[i] != x[i - 1] + 1)
                tot++;
        }
        if (tot <= k)
            cout << "Yes" << el;
        else
            cout << "No" << el;
    }
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

C题

陈述

• 给定n个数，每个数有k个二进制位，求满足下列式子的数组方案数
  

思路

• 自己第一反应是数位dp……,不过貌似就可以一个式子求
• 那个式子也可以快速幂求出来，利用异或的性质，可以将n分奇偶性讨论
• 思想也算是数位dp的常规套路思想
• 总体思想：如果高位胜出，低位任意取；高位平局，继续往下算

预处理平局方案数

• 异或的性质得，我们要构造偶数个1
• 即n个位置选偶数个1的方案数
• 方案数推导如下
  

n为奇数

• 我们已经知道了对于任意n至少有的平局的方案数量，不妨用$d=2^{n-1}$来表示（draw平局）
• 显然n为奇数的时候，全选1，也是平局
• 因为n为奇数，所以无法构造胜利的情况
• 即每个位置都构造平局的情况，总共k个位置，所以总得方案数量表示为$(d+1{)}^k$

n为偶数

• 推导过程如下
  

代码实现

        cin >> n >> k;
        if (k == 0)
        {
            cout << 1 << el;
        }
        else
        {
            LL ans = 0;
            LL d = fpow(2, n - 1);//单个位置平局决策方案数
            LL s = d * 2 % md;
            if (n & 1)
            {
                cout << fpow(d + 1, k) << el;
            }
            else
            {
                dwn(i, k, 1)
                {
                    ans = ans + fpow(d - 1 + md, k - i) * fpow(s, i - 1) % md;
                   //-1是去除掉全选的情况，+mod怕是负数
                    ans %= md;
                }
                ans = (ans + fpow(d - 1 + md, k)) % md;//第一个位置就赢了的情况
                //-1是去除掉全选的情况，+mod怕是负数
                cout << ans << el;
            }
        }
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