2025.10.23 模拟赛

字符串

分治 线段树

思路

首先看到每次都得砍半，所以划分子问题的个数不会超过 $\mathcal{O}({\log }_{2}n)$，可以直接分治求解。

设 $d{p}_{i,j,c}$ 表示 $[i,j]$ 为 $c$ 好串需要的最少替换数，那么令 $m=\frac{i+j}{m}$，有

$$d{p}_{i,j,c}=\min \left(\sum _{i=1}^m[s_i\ne c]+d{p}_{m+1,j,c+1},d{p}_{i,m,c+1}+\sum _{i=m+1}^r[s_i\ne c]\right)$$

求和部分可以做前缀和。但是 DP 数组不能直接存储。注意到递归树是一个线段树的结构，所以可以用类似线段树的节点标号方式。时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

const int kMaxN = 131072 + 5;
 
int dp[4 * kMaxN][26], pre[kMaxN][26], n;
string s;
 
int solve(int p, int l, int r, char c) {
  if (dp[p][c - 'a'] != -1) {
    return dp[p][c - 'a'];
  }
  if (l == r) {
    return s[l] != c;
  }
  int m = (l + r) / 2;
  int s = (m - l + 1) - (pre[m][c - 'a'] - pre[l - 1][c - 'a']), 
      t = (r - m) - (pre[r][c - 'a'] - pre[m][c - 'a']);
  return dp[p][c - 'a'] = min(s + solve(2 * p + 1, m + 1, r, c + 1), solve(2 * p, l, m, c + 1) + t);
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> s;
  s = " " + s;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      pre[i][j] = pre[i - 1][j] + (s[i] == 'a' + j);
    }
  }
  memset(dp, -1, sizeof(dp));
  cout << solve(1, 1, n, 'a') << '\n';
  return 0;
}

枪战地牢

序列dp

悲伤的事

我赛时的思路完全错误了。我最开始认为他会一只往右跑了之后回到最左边，但是第二个样例是蛇形走位，所以我就修改代码支持了蛇形走位，但是大样例一直 WA，鏖战两个半小时，无力战胜，最终挂 $35$ 分。

性质

首先我们需要从题面当中获得一些性质。

• 由于 AWP 耗时最长，所以 AWP 只能用于杀死 Boss。
• 一次往右走最多一次不会更劣。
• 由于 $2$，结束在 $n$ 或 $n-1$ 不会更劣。

疑问

这个结论和我之前的思路产生了巨大的偏差，因为我的算法固执地认为走到头再回来一定是最优的（$n$ 那里多走两次），这样子前面的边都只走了 $2$ 次。但是实际上，对于 $i$（到了 $i$ 但是杀了前 $i-1$）想要到 $i+2$，可以杀了 $i$ 的小怪和扣 Boss 一滴血然后到 $i+1$，同样做这种操作在 $i+1$，然后返回 $i$ 终结 Boss 再到 $i+1$ 终结 Boss，最后到 $i+2$。同样移动了四步，均摊每个边走两次，而边权 $d$ 是恒定的，所以这样子做一定不劣。

转移

现在我们设 $d{p}_i$ 表示当前到了 $i$，但是在 $i$ 这里啥也没干需要耗费的最小时间。第一种转移：把 $i$ 的小怪手枪毙掉，然后 AWP 直接秒 Boss

$$d{p}_{i+1}=d{p}_i+a_i\times r_1+r3+d$$

然后是先把 $i$ 小怪全杀死再干 Boss 一滴血，然后跑到 $i+1$ 那里再回来，杀死 Boss 再到 $i+1$。

$$d{p}_{i+1}=d{p}_i+\min ((a_i+1)\times r_1,r_2)+d+d+r_1+d$$

最后就是我疑问板块那里的转移了。

$$d{p}_{i+2}=d{p}_i+\min ((a_i+1)\times r_1,r_2)+d+\min ((a_{i+1}+1)\times r_1,r_2)$$

时间复杂度 $\mathcal{O}(n)$。不得不说赛时真的是太糖了，居然最简单的性质都认为是错的。

using LL = long long;
 
const LL kMaxN = 1e6 + 5;
 
LL a[kMaxN], dp[kMaxN], n, r1, r2, r3, d;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> r1 >> r2 >> r3 >> d;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  fill(begin(dp), end(dp), 1e18);
  dp[1] = 0;
  for (LL i = 1; i <= n; i++) {
    dp[i + 1] = min(dp[i + 1], dp[i] + a[i] * r1 + r3 + d);
    dp[i + 1] = min(dp[i + 1], dp[i] + min((a[i] + 1) * r1, r2) + d + d + r1 + d);
    dp[i + 2] = min(dp[i + 2], dp[i] + min((a[i] + 1) * r1, r2) + d + min((a[i + 1] + 1) * r1, r2) + d + r1 + d + r1 + d);
  }
  cout << min(dp[n + 1] - d, dp[n - 1] + min((a[n - 1] + 1) * r1, r2) + d + r1 * a[n] + r3 + d + r1) << '\n';
  return 0;
}

序列

线段树 二分

暴力和初步优化

首先考虑如何单次 $\mathcal{O}(n^2)$ 做暴力。首先令 $l\leftarrow x+1,r\leftarrow n-y$，$[l,r]$ 就是查询的区间。把这个区间当中所有 $a_i=i$ 的都找出来，那么应该优先删 $i$ 最大的，否则后面的 $a_i=i$ 就删不了了。删了之后打标记做前缀和，得到 $a_i=i-k$（$k$ 是 $i$ 之前已删除节点数）。一直模拟。

如何优化？可能我们并不需要在意删除的顺序。假设 $i$ 前面有最多 $cnt$ 个可删除的节点（按照某种顺序删除），那么 $i$ 实际的下标区间在 $[i-cnt,i]$，只有 $a_i$ 属于这个区间 $i$ 才可能被删，如果满足总能找到某种顺序删除。

所以维护已删除数量 $cnt$，对于新的 $a_i$，如果 $cnt\ge a_i$，那么 $cnt\leftarrow cnt+1$。最后 $cnt$ 就是答案。时间复杂度 $\mathcal{O}(qn)$。

优化

考虑优化。注意到我们的算法过程是从左到右的，因为依赖前面的 $cnt$，所以我们考虑再右端点上做功夫。把所有询问离线下来，对右端点进行排序，左端点的话就维护若干个 $cn{t}_l$，表示 $l$ 到当前的 $r$ 的最大删除数量。

那么当右端点往右扩展时，新加的元素要拼在后面，对于所有的 $cn{t}_l\ge a_r$，都要 $cn{t}_l\leftarrow cn{t}_l+1$。看起来很难搞，但是注意到 $cn{t}_l$ 随着 $l$ 的递增而递减，所以可以用线段树维护 $cn{t}_l$，然后在线段树上二分出一段前缀均满足 $cn{t}_l\ge a_r$，把这个前缀的值都 $+1$。最后查询 $cn{t}_l$（$l$ 是当前询问的左端点）即可。

时间复杂度 $\mathcal{O}(q{\log }_{2}n)$。

const int kMaxN = 3e5 + 5;
 
int a[kMaxN], tr[4 * kMaxN], tag[4 * kMaxN], ans[kMaxN], n, q;
tuple<int, int, int> p[kMaxN];
 
void addTag(int p, int d) {
  tr[p] += d;
  tag[p] += d;
}
 
void pushDown(int p) {
  if (tag[p]) {
    addTag(2 * p, tag[p]);
    addTag(2 * p + 1, tag[p]);
    tag[p] = 0;
  }
}
 
void modify(int p, int l, int r, int s, int t, int d) {
  if (s > t) {
    return;
  }
  if (s <= l && r <= t) {
    addTag(p, d);
    return;
  }
  pushDown(p);
  int m = (l + r) / 2;
  if (s <= m) {
    modify(2 * p, l, m, s, t, d);
  }
  if (m < t) {
    modify(2 * p + 1, m + 1, r, s, t, d);
  }
  tr[p] = min(tr[2 * p], tr[2 * p + 1]);
}
 
int binarySearch(int p, int l, int r, int val) {
  if (l == r) {
    return tr[p] >= val ? l : l - 1;
  }
  pushDown(p);
  int m = (l + r) / 2, x = tr[2 * p];
  if (x >= val) {
    return binarySearch(2 * p + 1, m + 1, r, val);
  }
  return binarySearch(2 * p, l, m, val);
}
 
int query(int p, int l, int r, int x) {
  if (l == r) {
    return tr[p];
  }
  pushDown(p);
  int m = (l + r) / 2;
  if (x <= m) {
    return query(2 * p, l, m, x);
  }
  return query(2 * p + 1, m + 1, r, x);
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = i - a[i];
    if (a[i] < 0) {
      a[i] = 1e9;
    }
  }
  for (int i = 1; i <= q; i++) {
    cin >> get<0>(p[i]) >> get<1>(p[i]);
    get<0>(p[i])++;
    get<1>(p[i]) = n - get<1>(p[i]);
    get<2>(p[i]) = i;
  }
  sort(p + 1, p + q + 1, [](auto &&a, auto &&b) {
    return get<1>(a) < get<1>(b);
  });
  for (int i = 1, j = 1; i <= q; i++) {
    auto [l, r, id] = p[i];
    for (; j <= r; j++) {
      int x = min(binarySearch(1, 1, n, a[j]), j);
      modify(1, 1, n, 1, x, 1);
    }
    ans[id] = query(1, 1, n, l);
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
 

马自立

欧拉回路

• [c] 赛时被 T2 折磨，根本无心做这道题，其实是后三题当中最简单的。

思路

首先可以看作先构建重要路径的图，然后加入若干条边，最后图整个变成欧拉回路。（因为不需要的边没加入）

无向图欧拉回路要求每个点的度数为偶数（连通性不用判，因为保证联通），所以对于必须加入的重要边先标记它们的度数。那么枚举端点跑 DFS，每次在遍历非关键邻边，然后递归搜索，回撤的时候判断这个点的度数是否为奇数，如果是那么就加入当前遍历的边。

最后看一下所有加入的边的点集每个点的度数是否为偶数即可。

时间复杂度 $\mathcal{O}(n+m)$。

const int kMaxN = 5e5 + 5;
 
int d[kMaxN], f[kMaxN], t, n, m;
vector<pair<int, int>> g[kMaxN];
 
void dfs(int x) {
  f[x] = 1;
  for (auto [i, id] : g[x]) {
    if (f[i]) {
      continue;
    }
    dfs(i);
    if (d[i]) {
      d[i] ^= 1;
      d[x] ^= 1;
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    fill(d + 1, d + n + 1, 0);
    fill(f + 1, f + n + 1, 0);
    fill(g + 1, g + n + 1, vector<pair<int, int>>());
    for (int i = 1, u, v, c; i <= m; i++) {
      cin >> u >> v >> c;
      if (c == 1) {
        d[u] ^= 1;
        d[v] ^= 1;
      } else {
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
      }
    }
    bool b = 1;
    for (int i = 1; i <= n; i++) {
      if (!f[i]) {
        dfs(i); 
        if (d[i]) {
          b = 0;
          break;
        }
      }
    }
    if (!b) {
      cout << "No\n";
      continue;
    }
    cout << "Yes\n";
  }
  return 0;
}

总结

总分：$100+35+40+0=175$。

最惨的一次，也是最糖的一次。死磕第二题，结果第三第四题我完全有能力做出来的没有写，然后第二题甚至还认为正确的性质是错误的。我以后一定不要在死磕 T2 了，包括像去年 CSP 一样，哪怕 T2 最后代码再短再糖，长时间写不出来（且不确定解法正确性），必须去写 T3 或者 T4。