2025.9.27 模拟赛

乘法减法按位或

数学 结论 位运算

首先 $\mathcal{O}(n^2)$ 是非常好想的，但是发现优化很难。观察到值域较小，所以可以想到设 $d{p}_i$ 表示满足 $a_j|a_k=i$ 最大的 $j\times k$。然而根本不会转移，所以直接趋势。

不过，观察式子中 $i\times j$ 是一个二次项，增长幅度特别快，而 $-k(a_i|a_j)$ 是一次项，当 $i,j$ 过大的时候后面的那一项几乎可以忽略，所以可以猜测答案 $(i,j)$ 肯定在靠后的位置。

严格证明如下：

• [n] 假设 $(n-1,n)$ 是最终最大的，那么我们需要推翻这个结论的话一定会有一个更大的。设更大的为 $(i,n)$，最好情况下该二元组的值为 $in-0=in$，而 $(n-1,n)$ 最坏情况下值为 $n(n-1)-2kn$。所以有方程 $in\ge n(n-1)-2kn$，解得 $i\ge n-2k-1$（也可以不取等），所以我们只需要枚举 $i\in [n-2k-1,n]$ 即可。

时间复杂度 $\mathcal{O}(kn)$。

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 3e5 + 5;
 
LL a[kMaxN], t, n, k;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    LL ans = -1e18;
    for (LL i = max(1LL, n - 2 * k - 1); i <= n; i++) {
      for (LL j = 1; j <= n; j++) {
        if (i != j) {
          ans = max(ans, i * j - k * (a[i] | a[j]));
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

队列

数学

首先，把 $n$ 个同学变成 $n$ 个点，$a$ 要站在 $b$ 前面可以看做 $a$ 往 $b$ 连一条边，那么最后会形成一个图，有多个连通块。如果一个连通块可以满足条件，那么这个连通块是一条链（因为不仅有前后关系还要相邻）。

如何判断每个连通块是否是链？每个点的入度、出度均不超过 $1$，且没有环。判环用拓扑排序即可。注意去重边。去掉重边之后若剩下 $m$ 条边那么连通块数量为 $n-m$，这些连通块彼此之间没有前后关系因此方案数 $(n-m)!$。

时间复杂度 $\mathcal{O}(n+m)$（去重边我带了个 $\log$）。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5, kMod = 1e9 + 7;
 
LL id[kMaxN], od[kMaxN], n, m, cnt, sum, ans = 1;
vector<LL> e[kMaxN];
queue<LL> q;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].push_back(v);
  }
  for (LL i = 1; i <= n; i++) {
    sort(e[i].begin(), e[i].end());
    e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
    od[i] = e[i].size();
    for (int j : e[i]) {
      id[j]++;
    }
  }
  if (count_if(id + 1, id + n + 1, [](LL i) {
    return i > 1;
  }) || count_if(od + 1, od + n + 1, [](LL i) {
    return i > 1;
  })) {
    cout << "0\n";
    return 0;
  }
  for (LL i = 1; i <= n; i++) {
    if (!id[i]) {
      q.push(i);
    }
  }
  for (; q.size(); q.pop()) {
    LL t = q.front();
    cnt++;
    for (LL i : e[t]) {
      if (!--id[i]) {
        q.push(i);
      }
    }
  }
  if (cnt != n) {
    cout << "0\n";
    return 0;
  }
  for (LL i = 1; i <= n; i++) {
    sum += e[i].size();
  }
  sum = n - sum;
  for (LL i = 1; i <= sum; i++) {
    ans = ans * i % kMod;
  }
  cout << ans << '\n';
  return 0;
}

权值

数学 等比数列求和 快速幂 乘法逆元

贡献可以拆为

1. 所有满足条件序列的数量；
2. 每个数的出现次数之和。

首先是第一问，对于长度为 $i$ 且取值范围在 $[1,n]$ 的整数序列，一共有 $n^i$ 种。因此序列数量为 $f(n,m)=\sum _{i=0}^m{n}^i$。这是一个等比数列，应用等比数列求和公式得到

$$f(n,m)=\sum _{i=0}^m{n}^i=\{\begin{array}{ll}m+1& \text{if}n=1\\ \frac{n^{m+1}-1}{n-1}& \text{else}\end{array}$$

至于每个数的出现次数之和，由于每个数的地位相等，因此每个数的出现次数之和也相等。对于 $1$，可以采用容斥，用总序列数量减去不使用 $1$ 的序列数量，即

$$\sum _{i=0}^m{n}^i-\sum _{i=0}^n(n-1{)}^i=f(n,m)-f(n-1,m)$$

再将这个数乘上 $n$ 即可得到所有数的出现次数之和，再加上一类贡献，得到最终答案

$$f(n,m)+n\times f(n,m)-n\times f(n-1,m)=(n+1)f(n,m)-n\times f(n-1,m)$$

用快速幂和乘法逆元即可。时间复杂度 $\mathcal{O}(t({\log }_{2}m+{\log }_{2}n))$。

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMod = 1e9 + 7;
 
LL t, n, m;
 
LL pow(LL a, LL b) {
  LL res = 1;
  for (; b; b /= 2) {
    b % 2 && (res = res * a % kMod);
    a = a * a % kMod;
  }
  return res;
}
 
LL solve(LL n, LL m) {
  if (n == 1) {
    return m + 1;
  }
  return (pow(n, m + 1) - 1 + kMod) % kMod * pow(n - 1, kMod - 2) % kMod;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    cout << ((n + 1) * solve(n, m) % kMod - n * solve(n - 1, m) % kMod + kMod) % kMod << '\n';
  }
  return 0;
}

钓鱼

贪心 优先队列

20 分

瞎搜就行了。状态就是 $(i,j)$ 表示当前到达第 $i$ 个地点，当前深度为 $j$，然后它可以转移到 $(i+1,j\pm 1)$ 或者 $(i+1,j)$，累加以下贡献就行了。

50 分

可以发现上面的算法对于重复状态 $(i,j)$ 在不同时刻结果不一样，但是结果肯定是越大越好，因此采用动态规划，将贡献列为最优化属性。设 $d{p}_{i,j}$ 表示当前到达第 $i$ 个地点，深度为 $j$ 所可以获得的最大饱腹值，转移方程 $d{p}_{i,j}=\max (d{p}_{i-1,j},d{p}_{i-1,j\pm 1})+j\times (B_i-A_i)$。

80 分

想到了 100 分的思路，但是用的是双 $\log$ 实现，或者直接用费用流模拟贪心过程了导致的。

• [b] 赛时被 $\mathcal{O}(n^2)$ 暴力卡过去了，下次再搞大一点。

100 分

假设已经凿完了，我们可以将层数“抽丝剥茧”，把第一层抽下来，然后把第二层抽下来，不难发现第 $K$ 层会完全被包含在第 $K-1$ 层中，而且这两层左端点和右端点一定是不会重合的（因为如果重合了相邻深度差就会大于 $1$）。

因此这道题目可以简化为“区间覆盖”的形式，即进行若干次选择，每次选择 $[L,R]$ 对 $L\sim R$ 的每一个地点都凿深一个单位，并且每个地点都只能作为左端点和作为右端点最多一次。

由于涉及到区间求和，可以整一个前缀和 $P_i=\sum _{j=1}^i(B_j-A_j)$，这样我们选择一个区间的操作就可以简化为选择一前一后两个 $P_i$ 相减。这时候就和买股票那题很像了。

我们枚举右端点 $R$，因为一个点只能最多作为右端点一次，因此我们需要在之前的左端点中找到 $P_{L-1}$ 最小的然后让 $P_R$ 减去 $P_{L-1}$ 进行一次区间覆盖（当然如果结果是负数那就不要做了）。同时由于一个点只能作为左端点一次，因此 $L$ 用完之后就需要把 $L$ 扔掉。

这样不一定是最后的，原因是因为以后可能会有更大的 $P_R$ 来减 $P_{L-1}$ 会更优。但是注意到 $P_k-P_i=(P_k-P_j)+(P_j-P_i)$，也就是说先让 $P_R$ 减去 $P_{L-1}$ 之后，遇到后面更大的让它直接减 $P_R$ 而不是 $P_{L-1}$，是和不选 $P_R$ 直接让后面的减 $P_L$ 是一样的，因此我们只需要把 $P_R$ 额外放进队列，静待后面的 $P$ 减去 $P_R$ “反悔”就行了。最后将 $P_R$ 放入队列，作为以后的左端点。

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

#include <iostream>
#include <queue>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5;
 
LL p[kMaxN], n, ans;
priority_queue<LL, vector<LL>, greater<>> q;
 
int main() {
  // 输入并作前缀和
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1, a, b; i <= n; i++) {
    cin >> a >> b;
    p[i] = p[i - 1] + b - a;
  }
 
  // 反悔贪心
  q.push(p[0]);
  for (LL i = 1; i <= n; i++) {
    if (p[i] - q.top() > 0) {  // 进行区间覆盖
      ans += p[i] - q.top();
      q.pop();
      q.push(p[i]);            // 留下反悔机会
    }
    q.push(p[i]);
  }
  cout << ans << '\n';
  return 0;
}

渴鹅村

线段树 二分 离散化 树链剖分

本题主要就是靠随机树来保证做法复杂度的

20 分

纯暴力，修改只改 a[x] = y，然后查询就爬取整个一条链，每个节点 $\mathcal{O}(n{\log }_{2}n)$（使用 STL kth-element 可以到 $\mathcal{O}(n)$）计算 $v$ 值，链最长 $\mathcal{O}(n)$，所以总时间复杂度 $\mathcal{O}(m\times n^2(\times \log n))$。

不过由于树是随机生成的，期望高度 $\log n$，时间复杂度可能跑不到上界，但是我的数据还是太超模了所以卡不过去。

50 分

预先计算所有的 $v$ 值，修改只需要修改所有的祖先。预处理 $v$ 值时间复杂度 $\mathcal{O}(n^2(\log n))$。由于树高期望 $\log n$，因此修改时间复杂度 $\mathcal{O}(n(\log n))$ 查询和路径长度有关系，随机数据的话也许时间复杂度为 $\mathcal{O}(\log n(\log n))$ 吧，不过实测会更慢。可以通过 $n,m\le 1000$ 的数据点

100 分

首先看到路径上查询，先写个树链剖分。值域太大了，但是只用到比大小因此可以离散化。首先快速查询第 $k$ 大，我们通常采用权值线段树处理。查询 $v$ 的值，这里有两种办法：对于每一个节点维护它的子树内所有 $a$ 的值的权值线段树，然后 dfs 做一个线段树合并，这样就能快速查子树第 $k$ 小；或者树套树，用树链剖分的普通线段树套上权值线段树，然后在多颗权值线段树上同时二分找第 $k$ 小。由于后面的方案不影响整体时间复杂度，而且可以复用维护 $v$ 的树套树，因此我选择用后面的方式实现。

现在我们获得了所有的 $v$ 值，那就用树套树维护它。对于查询路径 $v$ 值第 $k$ 小，我们先树剖把他剖成若干条链，然后在存着权值线段树的根的普通线段树上查询，得到若干个可以覆盖整个询问路径的权值线段树的根，然后在这些权值线段树上同时二分第 $k$ 小。时间复杂度 $\mathcal{O}({\log }^{3}n)$，原因是树剖一个 $\log$，外层线段树一个 $\log$，内层一个 $\log$。

至于查询，往上遍历祖先，对 $a$ 值和 $v$ 值的树套树进行修改。由于树高期望 $\log n$，因此时间复杂度也是 $\mathcal{O}({\log }^{3}n)$ 的。

因此总时间复杂度为 $\mathcal{O}(m{\log }^{3}n)$。

不过我没有卡树上莫队，如果你实现得非常好是可以过的。要卡的就加个强制在线操作，不过这样子就无法离散化导致常数爆炸了。但是树上带修莫队本身复杂度也就不咋地，应该是过不了的。

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
template <class T>
using Ref = const T &;
 
const int kMaxN = 1e5 + 5, kMaxM = 128 * kMaxN;
 
// 操作类
struct Operation {
  int o, x, y, k;
};
 
int a[kMaxN], k[kMaxN], fa[kMaxN], dep[kMaxN], siz[kMaxN], son[kMaxN], top[kMaxN], dfn[kMaxN], rnk[kMaxN], v[kMaxN], n, m, cnt;
int val[kMaxN], q;
vector<int> e[kMaxN];
vector<Operation> opt;
 
// 权值线段树动态开点
struct Node {
  int lc, rc, sum;
};
 
// 权值线段树
struct ValueSegmentTree {
  Node tr[kMaxM];
  int cnt;
 
  // 合并儿子节点
  void pushUp(int p) {
    tr[p].sum = tr[tr[p].lc].sum + tr[tr[p].rc].sum;
  }
 
  // 修改 x 处值增加 d
  void modify(int &p, int l, int r, int x, int d) {
    if (!p) {
      p = ++cnt;
    }
    if (l == r) {
      tr[p].sum += d;
      return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
      modify(tr[p].lc, l, m, x, d);
    } else {
      modify(tr[p].rc, m + 1, r, x, d);
    }
    pushUp(p);
  }
 
  // 多个结点同时线段树二分查询第 k 小
  int query(Ref<vector<int>> &v, int l, int r, int k) {
    if (l == r) {
      return l;
    }
    int sum = 0;
    for (int p : v) {
      sum += tr[tr[p].lc].sum;
    }
    int m = (l + r) / 2;
    if (k <= sum) {
      vector<int> nxt;
      for (int p : v) {
        nxt.push_back(tr[p].lc);
      }
      return query(nxt, l, m, k);
    }
    vector<int> nxt;
    for (int p : v) {
      nxt.push_back(tr[p].rc);
    }
    return query(nxt, m + 1, r, k - sum);
  }
} w_tr, v_tr;
 
int w_rt[4 * kMaxN], v_rt[4 * kMaxN];
 
// 在树链线段树上修改 x 点。在 t 权值线段上修改，根为 rt
void modify(ValueSegmentTree &t, int *rt, int p, int l, int r, int x, int val, int d) {
  t.modify(rt[p], 1, q, val, d);
  if (l == r) {
    return;
  }
  int m = (l + r) / 2;
  if (x <= m) {
    modify(t, rt, 2 * p, l, m, x, val, d);
  } else {
    modify(t, rt, 2 * p + 1, m + 1, r, x, val, d);
  }
}
 
// 获取同一条树链上 s~t 的权值线段树的所有根
void getRoot(int *rt, int p, int l, int r, int s, int t, vector<int> &res) {
  if (s <= l && r <= t) {
    res.push_back(rt[p]);
    return;
  }
  int m = (l + r) / 2;
  if (s <= m) {
    getRoot(rt, 2 * p, l, m, s, t, res);
  }
  if (m < t) {
    getRoot(rt, 2 * p + 1, m + 1, r, s, t, res);
  }
}
 
// 获取离散化之后的值
int getHash(int x) {
  return lower_bound(val + 1, val + q + 1, x) - val;
}
 
// 处理出父亲、深度、子树大小和重儿子
void dfs1(int x, int f) {
  fa[x] = f;
  dep[x] = dep[f] + 1;
  siz[x] = 1;
  for (int i : e[x]) {
    if (i == f) {
      continue;
    }
    dfs1(i, x);
    siz[x] += siz[i];
    if (siz[i] > siz[son[x]]) {
      son[x] = i;
    }
  }
}
 
// 获取链头、dfs 序
void dfs2(int x, int t) {
  top[x] = t;
  dfn[x] = ++cnt;
  rnk[cnt] = x;
  if (!son[x]) {
    return;
  }
  dfs2(son[x], t);
  for (int i : e[x]) {
    if (i == fa[x] || i == son[x]) {
      continue;
    }
    dfs2(i, i);
  }
}
 
// 查询子树中 A 值的第 k 小
int querySubtree(int x, int k) {
  vector<int> v;
  getRoot(w_rt, 1, 1, n, dfn[x], dfn[x] + siz[x] - 1, v);
  return w_tr.query(v, 1, q, k);
}
 
// 查询路径上 V 值的第 k 小
int queryPath(int x, int y, int k) {
  vector<int> v;
  for (; top[x] != top[y]; x = fa[top[x]]) {
    if (dep[top[x]] < dep[top[y]]) {
      swap(x, y);
    }
    getRoot(v_rt, 1, 1, n, dfn[top[x]], dfn[x], v);
  }
  if (dep[x] > dep[y]) {
    swap(x, y);
  }
  getRoot(v_rt, 1, 1, n, dfn[x], dfn[y], v);
  return v_tr.query(v, 1, q, k);
}
 
int main() {
  // 输入
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    val[++q] = a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> k[i];
  }
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
 
  for (int i = 1, o, x, y, k; i <= m; i++) {
    cin >> o >> x >> y;
    if (o == 1) {
      opt.push_back(Operation {o, x, y});
      val[++q] = y;
    } else {
      cin >> k;
      opt.push_back(Operation {o, x, y, k});
    }
  }
 
  // 离散化
  sort(val + 1, val + q + 1);
  q = unique(val + 1, val + q + 1) - val - 1;
 
  // 树链剖分
  dfs1(1, 0);
  dfs2(1, 1);
 
  // 插入 A 值到线段树
  for (int i = 1; i <= n; i++) {
    modify(w_tr, w_rt, 1, 1, n, dfn[i], getHash(a[i]), 1);
  }
 
  // 插入 V 值到线段树
  for (int i = 1; i <= n; i++) {
    v[i] = querySubtree(i, k[i]);
    modify(v_tr, v_rt, 1, 1, n, dfn[i], v[i], 1);
  }
 
  // 操作与询问
  for (auto &i : opt) {
    auto &&[o, x, y, k] = i;
    if (o == 1) {
      int old = getHash(a[x]), now = getHash(y);
      a[x] = y;
      modify(w_tr, w_rt, 1, 1, n, dfn[x], old, -1);
      modify(w_tr, w_rt, 1, 1, n, dfn[x], now, 1);
      for (int cur = x; cur; cur = fa[cur]) {
        old = v[cur];
        now = querySubtree(cur, ::k[cur]);
        if (old != now) {
          modify(v_tr, v_rt, 1, 1, n, dfn[cur], old, -1);
          modify(v_tr, v_rt, 1, 1, n, dfn[cur], now, 1);
          v[cur] = now;
        }
      }
    } else {
      cout << val[queryPath(x, y, k)] << '\n';
    }
  }
  return 0;
}