A B C D E F

A 选择题

A C A D B A D A C C

最后一题的复杂度计算可以了解什么是调和级数

大概是这样的 $\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor$ 约等于 $nlog(n)$

C 选项可以把代码看出枚举每个数 $i$ 可以作为那些数 $j$ 的因子。这样枚举下来就枚举了所有数的因子个数。

B

略

C

• 40 分做法：

​ $r \leq 10^6$，我会枚举，只需要直接枚举 $[l, r]$ 范围内所有的数，满足条件就加起来即可。

• 满分做法：

​ 可以想到，要在 $[l, r]$ 中找到 $k$ 倍数的和，实际上等价于在 $[0, r]$ 找到 $k$ 倍数的和，然后减去 $[0, l - 1]$ 的 $k$ 倍数的和，就可以求得原问题的结果。

​ 那现在只需要考虑 $[0, n]$ 内 $k$ 倍数的和。

​ 易证得，这里面最大的 $k$ 倍数就是 $\lfloor \frac{n}{k} \rfloor \times k$。

​ $x \times k \leq n \Rightarrow x \leq \frac{n}{k}$ 得证。

​ 我们还知道 $k$ 的倍数组成的是等差数列，那只需要等差数列求和公式就可以求出倍数和了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll cal(ll n, ll k)
{
    return (n / k + 1) * (n / k) * k / 2;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll l, r, k;
    cin >> l >> r >> k;
    cout << cal(r, k) - cal(l - 1, k) << endl;
}

D

• $7 + 8$ 分做法

  我会模拟，我只需要模拟这个输赢的过程，枚举每一个位置作为起点，然后开始模拟过程，因为连续的 D 不超过 $30$，所以那个输的钱用 int 都能存的下，只需要更新最大值就可以。

• $30$ 分做法

  我会模拟，并且我还知道每次输的时候不管输多少，只要赢一次，总会赢一块钱，所以我不需要维护真实输了多少钱，只需要碰到 U 的时候把当前的钱数量 $+1$ 即可，然后和上面一样枚举每个位置作为起点就足以。

• $60$ 分做法

  基于上面这个，并且我知道 $m = n$，也就是整个序列我都可以选，根据 $30$ 分做法我们可以想到，我们选更长的区间一定不会更差，因为只要最后一个点是赢就可以了。所以我们只需要看序列有几个 U，那我们全选了就能得到多少钱。

• $100$ 分做法

  现在题目限制了不能选长度超过 $m$ 的区间，根据 $60$ 分的做法，实际上我们要求的是长度为 $m$ 的区间里，最多能有几个 U，只需要前缀和维护 U 的数量，然后取最大的区间就可以了，或者直接双指针移动也可以。

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

const int N = 3e5 + 9;

int main() {
  
  int n, m;	cin >> n >> m;
  string s;	cin >> s;
  int now = 0, ans = 0;
  for(int i = 0; i < n; i ++) {
  	if(s[i] == 'U') now ++;
  	if(i >= m) now -= s[i - m] == 'U';
  	ans = max(ans, now);
  }
  cout << ans;
  
  return 0;
}

E

• 测试点 4 ~ 5 做法，当 $Ca$ 或 $Cb$ 为 0 时
  • 此时发现，每个机器人都只能去另一个非 0 的仓库，那么直接计算每个机器人到另一个仓库的距离总和即可
• 测试点 6 ~ 7 做法，当 $Ca$ 或 $Cb$ 为 $n$ 时
  • 此时可以注意到存在一个仓库能够容纳所有的机器人
  • 那不妨让所有机器人都去到这个仓库，计算当前距离总和 sum
  • 然后发现另一个仓库还能容纳一些机器人，于是尝试把当前仓库的机器人调整一部分到另一个仓库
  • 这里比较重要的是，我们会选择能够使 sum 下降的多的机器人去到另一个仓库，而不是离另一个仓库近的机器人
  • 所以计算所有机器人从当前仓库去到另一个仓库对 sum 的影响
  • 然后取影响中能使 sum 减少且不超过另一个仓库大小的机器人移动过去即可
• 测试点 8 ~ 10 做法，当 $Ca + Cb = n$ 时
  • 此时可以仿照上面的做法，先把机器人都移动到 A 仓库
  • 然后把其中 $Cb$ 个机器人再移动到 B 仓库中，这里按照移动对答案的减少程度选前 $Cb$ 大就可以了
• 测试点 11 ~ 13
  • 还是仿照上面的做法，可以发现，至少需要移动 $n - Ca$ 个机器人
  • 但最多可以移动 $Cb$ 个机器人，所以如果继续移动能够使的 sum 减少就再接着移动减少答案
• 满分做法
  • 一个比较经典的 贪心，我们可以先考虑把全部机器人都放在一个 A 充电器，然后我们知道 $A$ 容纳不下这么多，但是我们知道把某个机器人 $x$ 从 $A$ 挪到 $B$ 之后，总路程 $ans$ 会变成 $ans + dis(x, A) - dis(x, B)$。 于是我们想到贪心的把多出来的机器人往 B 移动，并且如果 B 还有位置的情况下，且路程能更小，我们可以继续往 B 加机器人。

这题一开始有点精度问题，如果是获得 80+ 分的同学应该现在已经重测成满分了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
double dis(int x, int y, int ax, int ay) {
    return sqrt((ax - x) * (ax - x) + (ay - y) * (ay - y));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int ax, ay, ca;
    int bx, by, cb;
    int n;
    cin >> ax >> ay >> ca >> bx >> by >> cb >> n;
    double ans = 0;
    vector<double> s;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        ans += dis(x, y, ax, ay);
        s.push_back(dis(x, y, bx, by) - dis(x, y, ax, ay));
    }
    sort(s.begin(), s.end());
    for (int i = 0; i < n - ca; i++) {
        ans += s[i];
    }
    for (int i = max(n - ca, 0); i < min(cb, n); i++) {
        if (s[i] < 0) ans += s[i];
    }
    cout << fixed << setprecision(3) << ans << endl;
}

F

• $10$ 分做法 我会暴力搜索。因为 $n \le 20$ 非常小，每个时刻的宝箱只有三种选择：跳过、选道具卡、选分数卡。直接写个 DFS 递归枚举每一种选择，顺便记录当前已经选了多少张分数卡，当递归到最后时刻时，计算出当前方案的总得分并更新最大值即可。
• $25$ 分做法 注意到 $a_i = 0$ 的特殊性质。由于道具卡此时完全提供不了任何加成，选它和直接跳过是一样的，所以我们永远不会选择道具卡。问题退化成有 $n$ 个宝箱，各自有消耗时间 $t_i$ 和分数 $b_i$，我们要选最多 $K$ 个互不重叠的宝箱使总分最大。可以直接倒着 DP，转移方程为：

​ $$dp[i][j] = \max(dp[i+1][j], b_i + dp[i+t_i+1][j-1])$$

• $40$ 分做法 注意到 $t_i = 0$ 的特殊性质。开启宝箱不消耗任何额外时间，意味着时刻之间完全没有时间冲突，并且**选道具卡相当于后面选了几个得分卡，这个道具卡的分值就变成了得分卡的数量 $\times a[i]$ **，也就是每个位置我们都会选，下一个能选的位置永远是 $i+1$，直接从 $i+1$ 转移：

​ $$dp[i][j] = \max({dp[i+1][j], dp[i+1][j] + a_i \times j, dp[i+1][j-1] + b_i})$$

• $60 \sim 80$ 分做法

  如果想不到倒着dp，也不会延迟贡献，那我们可以正着做，但是需要枚举最后一共选了几个得分卡。然后再来转移。复杂度就是 $n \times K^2$。

• $100$ 分做法 现在我们要解决全数据，直接实现 $O(nK)$ 的倒推 DP。设 $dp[i][j]$ 表示从 $i$ 时刻开始往后考虑，取了 $j$ 个得分卡的最优得分。状态转移方程为：

​ $$dp[i][j] = \max(dp[i + 1][j], dp[i + t_i + 1][j] + a_i \times j, dp[i + t_i + 1][j - 1] + b_i)$$

实现时有两点需要注意：一是 $j=0$ 时无法从 $j-1$ 转移；二是必须把所有非法状态初始化为负无穷，只有 $dp[n+1][0] = 0$，防止道具卡在没有分数卡的情况下刷分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int M = 500 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll dp[N][M];
ll t[N], a[N], b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, K;
    cin >> n >> K;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> a[i] >> b[i];
    }
    memset(dp, -0x3f, sizeof(dp));
    dp[n + 1][0] = 0;
    ll ans = 0;
    for (int i = n; i >= 1; i--)
    {
        for (int j = 0; j <= K; j++)
        {
            if (i + t[i] <= n)
            {
                if (j - 1 >= 0)
                {
                    dp[i][j] = max({dp[i + 1][j], dp[i + t[i] + 1][j] + a[i] * j, dp[i + t[i] + 1][j - 1] + b[i]});
                }
                else
                {
                    dp[i][j] = max({dp[i + 1][j], dp[i + t[i] + 1][j] + a[i] * j});
                }
            }
            else
            {
                dp[i][j] = dp[i + 1][j];
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}