2025.9.23 模拟赛

赌局

背包dp 容斥 贪心

如果我们已经选择了一种方案（以下 $a,b$ 表示已选的），那么我们可以枚举最终是哪个人赢了，赌除了这个人以外的人的就要给你钱，赌了这个人的你就要给他钱，因此最坏情况下收益为

$$\underset{i\in [1,3]}{\min }\left(\underset{\text{输的人给你的}}{\underbrace{\sum _{j\ne i}{b}_j}}-\underset{\text{赢的人你给的}}{\underbrace{\sum a_i}}\right)$$

很显然 $j\ne i$ 求和那里不好处理，但是我们可以做容斥，用所有 $b$ 的和减去 $\sum b_i$，因此问题变成

$$\underset{i\in [1,3]}{\min }\left(\sum b-\sum b_i-\sum a_i\right)=\underset{i\in [1,3]}{\min }\left(\sum b-\sum (a_i+b_i)\right)$$

而已选的 $b$ 的和在统计答案时其实是常数，因此我们需要最大化 $\sum (a_i+b_i)$，即求

$$\sum b-\underset{i\in [1,3]}{\max }\sum (a_i+b_i)$$

但是这个 $\max$ 很难处理，因为我们并不清楚三个当中的哪一个才是 $\max$。而我们选择一个新的元素时，可能会改变 $\max \sum (a_i+b_i)$，也会导致 $\sum b$ 变化，这个变化是很难维护的。

因此我们需要将 $\max \sum (a_i+b_i)$ 作为限制，也就是限制三组当中的任何一组都要满足 $\sum (a_i+b_i)$ 不超过这个值，而在满足条件的情况下最大化 $\sum b$。

于是我们可以对每一组做 0/1 背包。将 $a_i+b_i$ 视为重量，$b_i$ 视为价值，这样子我们就可以得到在重量不超过一定值的情况下，价值的最大值，也就是上式的要求。

因此思路就很清晰了。

1. 对每一组做以 $a_i+b_i$ 为重量，$b_i$ 为价值的 0/1 背包；
2. 对背包做前缀 $\max$，得到重量不超过限制的最大价值（如果 dp 数组全初始化为 $0$ 就可以省略这一步）；
3. 枚举 $\sum (a_i+b_i)$ 的最大值，在每一组都不超过这个限制的情况下计算最大 $b_i$ 和。

时间复杂度 $\mathcal{O}(n\times nV)$。

#include <iostream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 505 * 505 + 5;
 
struct Node {
  LL a, b;
};
 
LL dp[4][kMaxN], n, ans;
vector<Node> v[4], itm;
 
// 01 背包
void solve(LL dp[kMaxN], const vector<Node> &itm) {
  for (auto i : itm) {
    for (LL j = kMaxN - 1; j >= i.a; j--) {
      dp[j] = max(dp[j], dp[j - i.a] + i.b);
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1, t, a, b; i <= n; i++) {
    cin >> t >> a >> b;
    v[t].push_back(Node{a, b});
  }
  for (LL i = 1; i <= 3; i++) {
    itm.clear();
    // 按照上述方式构建背包元素
    for (auto j : v[i]) {
      itm.push_back(Node{j.a + j.b, j.b});
    }
    solve(dp[i], itm);
  }
  for (LL i = 0; i < kMaxN; i++) {  // 枚举 sum(a[i]+b[i]) 的最大值
    LL sum = 0;
    for (LL j = 1; j <= 3; j++) {   // 枚举分组
      sum += dp[j][i];              // 在 sum(a[i]+b[i]) 不超过最大值的情况下求 b[i] 最大和
    }
    ans = max(ans, sum - i);        // 注意这里和式子一样要减最大值
  }
  cout << ans << '\n';
  return 0;
}

三元组

写了个 $\mathcal{O}(n^2)$ 的暴力，光荣获得 $10$ 分。

游戏

啥都没写。

连通性统计

啥都没写。

总结

总分：$100+10=110$。

花了两个多小时写了 T1，然后 T2 没怎么想就只写了暴力，后两题根本没动。还是相较于上次有进步，至少成功地写出了 T1 捍卫了最后的尊严，但是后面去写美丽的 CCH 题单了就没做了，其实还可以骗得更多分数。T2 正解好像也不是很复杂，等会看看。