2024牛客暑期多校训练营10

A Surrender to My Will 签到题

B std::pair 模拟，建立二叉树即可

D Is it rated?

题目大意

有 \(n\) 场\(\textbf{按顺序}\)的比赛，第 \(i\) 场比赛有表现分 \(p_i\)。参加第 \(i\) 场比赛后你的分数 \(r\) 将变为 \(r\times(1-k)+k\times p_i\)。你可以选择最多 \(m\) 场比赛不参加。给定初始分数 \(r_0\) 和参数 \(k\)。问经过至少 \(n-m\) 场比赛后，分数最高是多少。

题解做法

根据数据范围 \(k\geq0.1\), 经过至多 200 场后之前的分数影响将在精度误差之内, 故只需要考虑最后 \(\min(m+200,n)\) 场比赛即可.

场上某大佬做法（可忽略 k 范围）

const int N = 1e6 + 5;
ll a[N];
db k, p[N];
#define vt vct<db>
vt dfs (int l, int r)
{
    if (l == r) rty {0, k * a[l]};
    int m = l + r >> 1;
    vt L = dfs (l, m);
    vt R = dfs (m + 1, r);
    int i = 0, j = 0;
    vt ans = {0};
    while (i + 1 < L.sz && j + 1 < R.sz)
    {
        if (L[i] * p[j + 1] + R[j + 1] > L[i + 1] * p[j] + R[j])
            j++, ans.pb (L[i] * p[j] + R[j]);
        else
            i++, ans.pb (L[i] * p[j] + R[j]);
    }
    while (i + 1 < L.sz ) i++, ans.pb (L[i] * p[j] + R[j]);
    while (j + 1 < R.sz ) j++, ans.pb (L[i] * p[j] + R[j]);
    rty ans;
}
void solve()
{
    cin >> n >> m >> k >> x;
    p[0] = 1;
    fo (i, 1, n) p[i] = p[i - 1] * (1 - k), cin >> a[i];
    vt rp = dfs (1, n);
    db ans = 0;
    fo (i, n - m, n)
    {
        ans = max (ans, x * p[i] + rp[i]);<details>
<summary>点击查看代码</summary>

```

```
</details>
//      print (x * p[i] + rp[i])
    }
    sp (12);
    ANS;
    rty;
}

用类似归并排序的方式来求区间内选择 \(1\sim len\) 场的最大得分.

分析: 在相同场次下, 不同的选取方式大小关系与初始分数无关. 基于原始 dp \(f_{i,j}\) 表示前 \(i\) 场, 选了 \(j\) 场参加的最大得分. 寻找性质快速合并.

下面来证明正确性：

F Collinear Exception

按顺序模拟，可以加入时暴力标记新增直线覆盖的点，经分析复杂度正确