2025.10.21 模拟赛

博弈

模拟 博弈论

思路分析

根据题意，选择的两个元素若是一奇一偶那么最终值相对于它们的和将会减少 $1$，否则不变。所以对于第一个人，肯定是优先选择同奇同偶的。第二个人需要最小化答案，那么会优先选择一奇一偶的。

问题

但是第一个人在奇数和偶数都很多的情况下，会进行什么操作呢？它会优先选择两个奇数的消掉。这样就可以让第二个人没有奇数用；不消偶数的原因是不管任何情况合出来都会增加一个偶数。

正确思路

所以先进行若干次理想型操作，即第一个人反复拿两个奇数合成一个偶数，第二个人拿一个偶数一个奇数合成一个偶数。即每次消除三个奇数，然后答案减去一。可以 $\mathcal{O}(1)$ 计算完成。

对于最后剩下的元素，再进行不超过一轮以后，只会剩下偶数，此时和不变。可以直接模拟最后的操作。

• [n] 对于每个前缀都进行计算。时间复杂度 $\mathcal{O}(n)$。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("makise.in");
ofstream cout("makise.out");
 
LL a[kMaxN], n, c0, c1, ans;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
    c0 += a[i] % 2 == 0;
    c1 += a[i] % 2 == 1;
    LL x0 = c0, x1 = c1;
    LL sub = x1 / 3;
    x1 %= 3;
    ans += a[i];
    x0 += sub;
    if (x1 >= 2) {
      x1 -= 2;
      x0++;
    } else if (x0 >= 2) {
      x0--;
    } else if (x0 && x1) {
      x0--, x1--;
      sub++;
    }
    if (x0 && x1) {
      sub++;
    }
    cout << ans - sub << ' ';
  }
  return 0;
}

购物

贪心 优先队列 排序

赛时思路

考虑较多次地选择 $b$ 最大（其次 $a$）的的元素，枚举其它元素的选择次数（最多不超过 $\min (2n,m)$），然后用优先队列每次选择其它元素当中可选的最大值。

注意

赛时思路是错误的。考虑这个 $n=2,m=3$ 的样例

$$\left(\begin{array}{cc}0& 100\\ 10& 0\\ 5& 99\end{array}\right)$$

我们把 $(0,100)$ 单独搞出去，枚举其它的选多少个。如果什么都不选就是 $100$。当选择其它的一个时，程序将贪心地选择 $10$。此时并不优。但是当选择其它的两个是，我们会选择 $5$，这直接导致了我们错过了最优解 $5+99$。

猜想

这似乎需要通过反悔贪心实现，不过我的实现仍然无法成功地通过大样例。

• [p] 好在只挂了 $15$ 分。

对于这道题目，一共有两种思路。他们都是正确的。

正确思路一

既然我们不一定会选择 b_\max 较多次，于是我们就可以直接枚举选择哪个 $b_i$，那么就必定同样会选择 $a_i$。对于其它元素 $j\ne i$ 的 $b_j$ 我们都不会再次选择了，所以我们把所有大于 $b_i$ 的 $a_j$ 给选了。可以通过排序后二分或双指针实现。时间复杂度 $\mathcal{O}(m{\log }_{2}m)$。

正确思路二

直接把一个物品拆成两个物品 $a_i,b_i$ 从大到小加入优先队列当中（$a$ 还是 $b$ 的信息仍要保留）。对于新的一个元素，如果是 $a$ 直接选上即可；如果是 $b$，如果以前已经选过了其对应的 $a$，直接选上即可；否则若剩余步数允许就把它的 $a$ 选上之后反复选 $b$，和答案求个 $\max$（注意这里不要 break 也不是实际选上了）。时间复杂度 $\mathcal{O}(m{\log }_{2}m)$。

• [n] 我赛后改题实现的是正确思路二。

#include <algorithm>
#include <fstream>
#include <queue>
#include <utility>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("shop.in");
ofstream cout("shop.out");
 
LL f[kMaxN], t, n, m;
pair<LL, LL> a[kMaxN];
 
struct Node {
  LL id, val, tp;
 
  Node(LL id, LL val, LL tp) : id(id), val(val), tp(tp) {}
 
  friend bool operator<(const Node& a, const Node& b) {
    return a.val != b.val ? a.val < b.val : a.tp < b.tp;
  }
};
 
priority_queue<Node> q;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    for (; q.size(); q.pop()) { }
    fill(f + 1, f + m + 1, 0);
    for (LL i = 1; i <= m; i++) {
      cin >> a[i].first >> a[i].second;
      q.emplace(i, a[i].first, 1);
      q.emplace(i, a[i].second, 2);
    }
    LL ans = 0, sum = 0;
    while (q.size()) {
      auto [id, val, tp] = q.top();
      q.pop();
      if (!n) {
        break;
      }
      if (tp == 1) {
        sum += val;
        ans = max(ans, sum);
        f[id] = 1;
        n--;
      } else {
        if (f[id]) {
          sum += val * n;
          ans = max(ans, sum);
          break;
        } else {
          if (n == 1) {
            continue;
          }
          ans = max(ans, sum + a[id].first + val * (n - 1));
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

划分

线段树 序列dp ST表 单调栈

思路

考虑 DP。由于和分段数量没有关系，所以设 $d{p}_i$ 表示若最后一段的最后一个元素为 $i$，所可以获得的最大价值。

转移如下：枚举最后一段实际的起点 $j$ $(1\le j\le i)$，那么前一段的终点就是 $j-1$，有 $d{p}_i=\underset{j=1}{\overset{i}{\max }}(d{p}_{j-1}+f(j,i))$，其中 $f(j,i)$ 为 $b_k$ 其中 $b_k\ge a_p$ $(p\in [j,i])$。不难发现可以通过倒叙枚举 $j$ 维护最小值，时间复杂度优化为 $\mathcal{O}(n^2)$。

优化

DP 状态设计已经足够简单了，如果优化转移复杂度呢？考虑维护全局最值，快速求出 $d{p}_{j-1}+f(j,i)$。

考虑线段树维护 $d{p}_{j-1}$ 和上面一大坨。首先我们思考，对于前面的所有状态每个的后方都加入一个 $a_i$，谁的最小值会改变谁不会？可以找到最后一个 $a_j\ge a_i$，$k\ge j$ 的就会改变，否则不会。

提示

可以用单调栈快速求，也可以用 ST 表维护 $a$ 的最小值然后二分。

现在对于 $k\in [j,i]$，$d{p}_k$ 后面的增量都会变成 $+b_i$。可以在线段树上直接做区间修改，拆成多段区间每段值都等于这一段 DP 最大值加上 $b_i$。

现在 $d{p}_i$ 就可以通过查询线段树全局最小值得到。由于是查询全局不需要写懒标记下放。

考虑 $d{p}_i$ 往后面的转移，作为 DP 值插入到线段树 $i$ 位置上即可。

找 $j$ 时间复杂度 $\mathcal{O}(n{\log }_{2}n)$，计算 DP 时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 10, kLog = 20;
 
ifstream cin("divide.in");
ofstream cout("divide.out");
 
struct Node {
  LL dp, mx;
 
  Node(): dp(-1e18), mx(-1e18) { }
} tr[4 * kMaxN];
 
LL a[kMaxN], b[kMaxN], f[kMaxN][kLog], lg[kMaxN], dp[kMaxN], n;
 
LL query(LL l, LL r) {
  LL k = lg[r - l + 1];
  return min(f[l][k], f[r - (1 << k) + 1][k]);
}
 
Node merge(const Node &a, const Node &b) {
  Node res{};
  res.dp = max(a.dp, b.dp);
  res.mx = max(a.mx, b.mx);
  return res;
}
 
// 修改增量
void modifyAdd(LL p, LL l, LL r, LL s, LL t, LL val) {
  if (s <= l && r <= t) {
    tr[p].mx = tr[p].dp + val;
    return;
  }
  LL m = (l + r) / 2;
  if (s <= m) {
    modifyAdd(2 * p, l, m, s, t, val);
  }
  if (m < t) {
    modifyAdd(2 * p + 1, m + 1, r, s, t, val);
  }
  tr[p] = merge(tr[2 * p], tr[2 * p + 1]);
}
 
// 修改dp值
void modifyDp(LL p, LL l, LL r, LL x, LL val) {
  tr[p].dp = max(tr[p].dp, val);
  if (l == r) {
    return;
  }
  LL m = (l + r) / 2;
  if (x <= m) {
    modifyDp(2 * p, l, m, x, val);
  } else {
    modifyDp(2 * p + 1, m + 1, r, x, val);
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
    f[i][0] = a[i];
  }
  for (LL i = 1; i <= n; i++) {
    cin >> b[i];
  }
  for (LL j = 1; j < kLog; j++) {
    for (LL i = 1; i + (1 << j) - 1 <= n; i++) {
      f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (LL i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  fill(begin(tr), end(tr), Node());
  modifyDp(1, 0, n, 0, dp[0] = 0);
  for (LL i = 1; i <= n; i++) {
    LL p = i;
    for (LL l = 1, r = i; l <= r; ) {
      LL m = (l + r) / 2;
      if (query(m, i) == a[i]) {
        p = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    modifyAdd(1, 0, n, p - 1, i - 1, b[i]);
    dp[i] = tr[1].mx;
    modifyDp(1, 0, n, i, dp[i]);
  }
  cout << dp[n] << '\n';
  return 0;
}

树上计数

树链剖分 点分治 树形dp 启发式合并

我写的暴力。

思路

首先可以枚举三元组的中间点，使得三个点到枚举的点距离相同。这个点肯定不会在边上。

枚举后以 $i$ 为根开始，跑出所有点的深度。那么我们求的以 $i$ 为中心的三元组肯定深度相同，且在 $i$ 的儿子的不同子树当中。这是一个组合数问题，可以线性解决。

时间复杂度 $\mathcal{O}(n^2)$。成功获得 $30$ 分。

正解是长链剖分+树形 DP $\mathcal{O}(n)$，当然淀粉质+树上启发式合并 $\mathcal{O}(n{\log }^{2}n)$ 也过了。