模拟赛-2025-07-28

2025深圳南宁夏令营模拟赛 - 比赛详情 - 云斗学院

第一次拿 MVP，有点小激动。$100+60+80+0=240pts.$

先列一下卡常经验：

1. 相信爆搜 + 剪枝拉满也有机会 AC，T1 我就是这么过的，赛时总耗时 72ms，我写的正解 25ms。

2. 多次枚举清空用 memset()，不要自己用 for() 清空。T3 我赛时总耗时 ≥6169ms，只是换成 memset()，直接降到 2293ms。

3. 先想暴力做法，再试图在暴力的基础上优化。

4. 发现 $n$ 大值域小，考虑从值域入手（桶）。

T1 木石走路

题意简述：有 $n\times m$ 的网格，上面有 $k$ 个障碍物，分别在 $(x_i,y_i)$。起点在 $(1,1)$，终点在 $(n,m)$。每次只能向右走或向下走。即从 $(i,j)$ 可以走到 $(i+1,j)$ 或 $(i,j+1)$，不能回头。问：至少再添加几个障碍物，才能使得不能从起点走到终点？（障碍物不能添加在起点或终点）

范围：$1\le n,m\le3000.$

赛时思路

范围 3k，一眼 $O(n^2)$。想到了两个思路：DP 或转为无向图用 Tarjan 求割点。

• 一开始把 Tarjan 打出来并调好了，可是发现这样不对，因为就算整个图不连通起点和终点也可能连通。

• 再想了想 DP，憋了半天硬是想出来从起点和终点 DP 两次了，可是推了半天也不知道怎么用这个求 “堵点”。一开始想到转移 “某点是否可能成为堵点” 这个状态，发现根本行不通。

• 后来考虑爆搜 + 剪枝拉满。首先我们枚举堵点，

  • 这个点一定得在起点到终点的路径上吧，结合双向 DP，如果两次 DP 某个点都被遍历到了，说明确实在路径上。

  • 如果这个点四周都是空的，肯定不可能是堵点。

• 尝试把每个决定枚举的点堵上，然后跑一遍连通性。

DP 复杂度：$O(mn)$；搜索：$\le O(m^2n^2)$。总复杂度：$\le O(m^2n^2)$。居然 AC 了！！而且绰绰有余。

老师：还有这种操作。

正解

第一次 DP 的结果，即到起点的方案数记为 $f(x,y)$，第二次 DP 即到终点的方案数记为 $g(x,y)$，如果某个点满足 $f(x,y)\times g(x,y)=f(n,m)$，说明这个就是我们想要的堵点。

太妙了！！！！！

注意到 “方案数” 有这样的性质（其实是废话），记起点为 $s$，终点为 $t$。

• $s\to u$ 的方案数 = $u\to s$ 的方案数。

• $t\to u$ 的方案数 = $u\to t$ 的方案数。

那么堵点有什么性质呢？所有 $s\to t$ 的路径都要经过它，所以自然有 $f(x,y)\times g(x,y)=f(n,m)$，排列组合的乘法原理。

但是我们要枚举每个点 $u$，求 $u\to t$ 的长度，这样做复杂度太高了。反过来从 $t$ 开始 DP 就好了。

总复杂度：$O(mn)$。

T2 买椟还珠

题意简述：有 $n$ 个物品，每个物品有一个美观值 $a_i$、价值 $b_i$。现在希望从这些物品里选出 $k$ 个，使得选出的物品的价值之和与最小美观值的积最大。

形式化语言就是：$S=\{(a_i,b_i)\}_1^n$，求一个 $S_0\subset S$ 且 $|S_0|=k$，使得下式的值最小：

$$\min\{a_i\}\times\sum{b_i},(a_i,b_i)\in S_0$$

范围：$1\le n\le 10^7,1\le a_i,b_i\le10^5.$

赛时思路

$10^7$ 这种级别是 $O(n)$ 没错了。思路好难想，但大概就是锁定了 DP。想出了 $O(nk)$ DP：

• 按照美观值从大到小排序，依次决定又不要把第 $i$ 个物品选入。这样做的道理是：美观值越来越小，选了当前这个显然之前的都能选。

• 自然想到设计状态 dp[i][j] 表示前 i 个物品里选 j 个，能达到的最大价值和；同时还要维护 dp2[i][j]，记录达成 dp[i][j] 时最小的美观值。最后我们遍历一遍，求出 dp[1..n][k] * dp2[1...n][k] 的最大值，即为答案。注意不能取 dp[n][k] * dp2[n][k] 哦。

• 转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + value[i])，和背包有亿点像。如果我们用决定放入第 i 个物品，就把 dp2[i][j] 设为 a[i]。

• 但是这样肯定爆空间，$10^7$ 的规模不是开玩笑的。当然滚动优化，注意这样我们就必须一边 DP 一边统计 ans 了。

其实赛时我还特判了 $k=0,k=1,k=n$ 三种情况，这三种情况不排序也不 DP，直接统计答案。不过对结果好像影响不大。

排序复杂度：$O(n\log n)$；DP：$O(nk)$。总复杂度：$O(nk)$。结果：$60pts$。

正解

不是严格的 $O(n)$，因为仍要用 std::sort() 进行 $O(n\log n)$ 的排序。当然本题值域比较小，用桶排就能达到 $O(n)$ 了。但这不是重点。

注意到 n 很大，a, b 值域却较小，所以从值域入手是可行的。

仍然沿用上面的思路，按美观度从大到小排序。考虑对 DP 进行优化。之前的 DP 之所以有 $O(nk)$ 的复杂度，是因为我们计算 dp[i][k] 时依赖于 dp[i-1][k-1]，以此类推，我们需要 dp[i-1][1...k-1] 的信息。那有没有可能从 dp[i-1][k] “反” 求出 dp[i][k] 呢？其实是可以的！我们想知道少选一个物品能达到的最大价值是多少，其实只用减去前 i 我们选的物品中价值最小的那个就行了。

重新设计状态：令 sumValue[i] 表示前 i 个物品里选 k 个，能达到的最大价值和，同时 minBeauty[i] 表示此时最小的美观值。我们还要维护 choose[i][j]，记录此时价值为 j 的物品选了几个（这是关键！！）。为了每次找最小价值的物品能快点，我们还可以弄一个 minValue[i] 记录已选物品的最小价值是多少。

命名放飞自我。。但至少比 dp[] dp2[] dp3[] 强。

注意到我们肯定是不可能从前 1 个物品里选 k 个的（$k\gt1$ 时）。怎么办呢？不妨强制选前 $k$ 个，之后相当于考虑要不要用后面的物品来 “替换”。或者你可以像题解那样维护一个 cnt。当然了，理论上选够 k 个物品才能开始统计 ans。不过没对于选够 k 个物品的情况，肯定会比最终答案要小，所以不影响答案统计，所以不判断也行。

当然我们肯定要 “滚动” 优化……诶优化完居然得到了 0 维的状态，这还是 DP 吗。。于是我们就得到了和题解等价的方法。但是我看不懂题解的思路。算了，殊途同归吧。下面放一下关键代码：

struct Obj {
    int beauty, value;
    bool operator<(const Obj& another) const {
        return beauty > another.beauty;
    }
} o[MAXN + 1];

sort(o + 1, o + n + 1);
ull sumValue = 0, ans = 0;
int minBeauty = 1e9, minValue = 1e9;
for (int i = 1; i <= n; i++) {
    if (i <= k) { // 前 k 个必选
        sumValue += o[i].value;
        minBeauty = o[i].beauty;
        choose[o[i].value]++;
        minValue = min(minValue, o[i].value);
    } else {
        //if (sumValue - minValue + o[i].value > sumValue) {
        if (o[i].value > minValue) { // 简化逻辑，本质上相同
            sumValue = sumValue - minValue + o[i].value;
            minBeauty = o[i].beauty;
            choose[minValue]--, choose[o[i].value]++;
            while (not choose[minValue]) minValue++; // 找到新的最小价值
        }
    }
    ans = max(ans, sumValue * minBeauty);
}
cout << ans << '\n';

T3 七夜雪寂

题意简述：一年有 $n$ 个月，第 $i$ 个月有 $a_i$ 天。现在需要确定一周的天数 $m$。$m$ 需要满足：

• 每个月至少有 4 个星期，也就是最小的 $a_i$ 要满足 $a_i\div m\ge4$。

• 每个月的天数对 $m$ 取余，最多有 3 种结果。

范围：$1\le n\le2\times10^4,1\le a_i\le10^6$，另外保证 $1\le m\le 10^6$。

赛时思路

打暴力！先找出最小的 $a_i$，然后从 1 开始枚举可能的 $m$，对于每个 $m$ 又枚举对每个月的天数取余的结果，统计一共有几种余数。

然而这样还是太暴力了：$O(n^2)$，赛后测了一下只有 $50pts$。细细想了一下，发现以下规律（大胆猜想 + 尝试归纳）：

• 如果 $a_1\dots a_n$ 对 $m$ 取余的结果有 $x$ 种，那么 $a_1\dots a_n$ 对 $km$ 取余的结果一定有 $\ge x$ 种。$k$ 是任意正整数。证明：

  • 没想到怎么证。这个结论显然好吧。

• 那么我们这么做：对于每个数 $m$，如果我们能过确定它不满足要求，那么 $2m,3m,\dots$ 都不满足要求。我们标记那些不满足要求的数。接下来枚举 $m$ 的时候直接跳过。

• 我觉得这个做法和欧拉筛有异曲同工之妙。

我猜这个算法的时间复杂度可能在 $O(n)$。我不知道怎么证。在随机数据上测试发现时间复杂度接近 $O(n)$。

最终这道题得了 $80pts$，但是换成每次枚举用 memset() 清空就能 AC 了。可能 $O(n)$ 做 $10^6$ 还是有点吃力吧。但是我看正解好像也是 $O(n)$ 的。

更优解（正解）

居然是鸽巢原理。对于正确的 $m$，因为所有 $a_i\bmod m$ 只有 3 种结果，所以 4 个 $a_i$ 对 $m$ 取余，至少有两个余数相同。即：每 4 个 $a_i$ 至少有两个模 $m$ 同余。

那么