2025.9.30 模拟赛

日记和最短路

最短路深度优先搜索广度优先搜索

首先一条边的边权字符串长度不一致很难搞，因为拼起来之后会错位，导致我们无法选择字典序最小的。因此可以将不同长度的字符串拆成多个字符，然后建虚点，这样就可以保证每条边i上边权都是一个字符。

现在对于第二问已经很好解决了。分层跑 BFS，每次让所有节点一起往后走一条边，但是必须满足走的边是所有可走的边当中字典序最小的那个。

这样我们每一步都走的字典序最小的，也就满足我们的任意一条路径任意前缀最小，也就有了答案最小。还原答案就是记录转移的上一个节点然后反向还原即可。

[!] 需要注意的一条边只有在终点可以到达 $n$ 时才是有效的，其余直接忽略。我们是在所有有效的边当中选取字典序最小的若干条。
[n] 所以我们需要需要建反向边，从 $n$ 开始跑 DFS 或 BFS 找到所有可以到 $n$ 的节点。
[c] 赛时我建反向边写错了，但是样例全过，最终直接炸缸。

然后是第一问，其实大差不差。同样是在反向图上先跑一遍 BFS 求出任意节点到 $n$ 的最短路。然后同样套用上面的板子，但是第一比较关键字改成到 $n$ 的距离，其次才是字典序。这样我们就成功完成了两个询问。

最后就是漫长的卡常过程。

开 long long 会 MLE，直接开 int；
数组开 $3 \times 1 0^{6}$ 会 MLE，卡在上界 $2.1 \times 1 0^{6}$ 刚刚好；
最后的分层 BFS 同一个点会在不同层里面访问多次，但是我们不能剪掉后来的因为后来的有可能字典序更小。所以我们只需要处理同层的，每一层每个点只能访问一次，这样子就可以保证入队次数不太多，剩下的就是玄学了。

时间复杂度 $O (能过)$ 。赛后 AC 代码。

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <set>
 
using namespace std;
 
const int kMaxN = 3e6 + 5;
 
int f[kMaxN], d[kMaxN], vis[kMaxN], n, m, cnt;
string w, ans;
vector<pair<int, char>> e[kMaxN];
vector<int> q, nxt;
vector<int> g[kMaxN];
pair<int, char> p[kMaxN];
 
void cover(int x) {
  if (f[x]) {
    return;
  }
  f[x] = 1;
  for (int i : g[x]) {
    cover(i);
  }
}
 
void bfs(int x) {
  queue<int> q;
  fill(d + 1, d + cnt + 1, 1e9);
  for (q.push(x), d[x] = 0; q.size(); q.pop()) {
    int t = q.front();
    for (int i : g[t]) {
      if (d[t] + 1 < d[i]) {
        d[i] = d[t] + 1;
        q.push(i);
      }
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  cnt = n;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v >> w;
    if (w.size() == 1) {
      e[u].emplace_back(v, w[0]);
      g[v].emplace_back(u);
      continue;
    }
    e[u].emplace_back(++cnt, w.front());
    g[cnt].emplace_back(u);
    for (int i = 1; i < w.size() - 1; i++) {
      e[cnt].emplace_back(cnt + 1, w[i]);
      g[cnt + 1].emplace_back(cnt);
      cnt++;
    } 
    e[cnt].emplace_back(v, w.back());
    g[v].emplace_back(cnt);
  }
  cover(n); 
  bfs(n);
  for (q.emplace_back(1); q.size(); ) {
    nxt.clear();
    int dis = 1e9;
    char c = 'z';
    for (int i : q) {
      for (auto j : e[i]) {
        if (d[j.first] < dis) {
          dis = d[j.first];
          c = j.second;
        } else if (d[j.first] == dis) {
          c = min(c, j.second);
        }
      }
    }
    for (int i : q) {
      for (auto j : e[i]) {
        if (d[j.first] == dis && j.second == c && !vis[j.first]) {
          nxt.emplace_back(j.first);
          p[j.first] = {i, j.second};
          vis[j.first] = 1;
        }
      }
    }
    for (int i : nxt) {
      vis[i] = 0;
    }
    if (p[n].first) {
      break;
    }
    swap(q, nxt);
  }
  for (int x = n; x != 1; x = p[x].first) {
    ans += p[x].second;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << ' ';
  ans.clear();
  q.clear();
  fill(p + 1, p + cnt + 1, pair<int, char>(0, 0));
  for (q.emplace_back(1); q.size(); ) {
    nxt.clear();
    char c = 'z';
    for (int i : q) {
      for (auto j : e[i]) {
        if (f[j.first] && j.second < c) {
          c = j.second;
        }
      }
    }
    for (int i : q) {
      for (auto j : e[i]) {
        if (f[j.first] && j.second == c && !vis[j.first]) {
          nxt.emplace_back(j.first);
          p[j.first] = {i, j.second};
          vis[j.first] = 1;
        }
      }
    }
    for (int i : nxt) {
      vis[i] = 0;
    }
    if (p[n].first) {
      break;
    }
    swap(q, nxt);
  }
  for (int x = n; x != 1; x = p[x].first) {
    ans += p[x].second;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
  return 0;
}

日记和欧拉函数

数学找规律结论质因数分解前缀和

首先我一眼就看见了 $\leq 1 0^{6}$ ，因此我先使用线性筛 $O (n)$ 求出所有欧拉函数的值。然后就是求 $φ^{x} (i)$ 。这个有点类似于 LCA 的倍增上跳，因此我们直接 $O (n lo g_{2} n)$ 预处理倍增加 $O (lo g_{2} n)$ 单次查询即可。（不过赛后发现暴力跳最多跳 $2 ⌈ lo g_{2} x ⌉$ ）

于是我们就可以预处理出 $S (n) = i = 1 \sum n φ^{(j = 1 m a x i φ (j) - B)} (i)$ ，最后 $S (r) - S (l)$ 就是答案了。

[p] 最后再加上 $B = 1 0^{9}$ 的 $f (i) = i$ 和 $B = 0$ 的 $f (i) = 1$ ，成功获得 $80$ 分。

现在就是进阶操作了。首先这个求和式子及其的不规则，所以是很难搞出来的。所以需要进行找规律。对于 $i \leq B$ ，由于 $φ (i) \leq i$ ，所以有 $φ (i) \leq B$ ，也就是 $j = 1 max i φ (j) - B \leq 0$ ，所以对于 $i \leq B$ 有 $f (i) = i$ 。

然后打标观察，在 $B$ 往后大约 $400$ 个数都是无规律的，但是 $400$ 个之后就都变成 $1$ 了。证明不太会，大概就是大于一个值了之后 $j = 1 max i φ (j) - B$ 就会大于等于 $60$ ，此时就一定会跳成 $1$ 。

可以找一个大于 $B + 60$ 的质数 $p$ ，那么有 $φ (p) = p - 1$ 也就有 $φ (p) - B \geq 60$ 即 $j = 1 max p φ (j) - B \geq 60$ ，往后这个数一定会更大所以最终都会变成 $1$ 。而设置 $400$ 的原因是这个数大小刚刚好，其实也可以直接暴力找大于 $B + 60$ 的第一个质数作为分界点。

而对于 $B \leq i \leq B + 400$ ，直接暴力求解欧拉函数即可。

#include <iostream>
 
using namespace std;
using LL = long long;
 
LL sum[401], t, b;
 
bool isPrime(LL x) {
  if (x <= 1) {
    return 0;
  }
  for (LL i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}
 
LL max(LL x) {
  for (LL i = x; i; i--) {
    if (isPrime(i)) {
      return i;
    }
  }
  return 2;
}
 
LL phi(LL x) {
  if (x == 1) {
    return 1;
  }
  LL ans = x;
  for (LL i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      ans = ans / i * (i - 1);
      for (; x % i == 0; x /= i) { }
    }
  }
  if (x > 1) {
    ans = ans / x * (x - 1);
  }
  return ans;
}
 
LL calc(LL x, LL y) {
  if (y <= 0) {
    return x;
  }
  while (y--) {
    if (x == 1) {
      break;
    }
    x = phi(x);
  }
  return x;
}
 
LL solve(LL x) {
  if (x <= b) {
    return x * (x + 1) / 2;
  } else {
    return sum[min(400LL, x - b)] + (x > b + 400) * (x - b - 400);
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> t >> b;
  sum[0] = b * (b + 1) / 2;
  for (LL i = 1; i <= 400; i++) {
    sum[i] = sum[i - 1] + calc(b + i, max(b + i) - b - 1);
  }
  for (LL l, r; t; t--) {
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << '\n';
  }
  return 0;
}

日记和二叉搜索树

背包dp 树形dp

首先枚举任意一个数作为 LCA，那么所有的 $(u, v)$ 一定满足 $u$ 和 $v$ 在 LCA 的不同儿子的子树里。然后稍微推一下式子就可以得到 LCA 的值一定是介于两个子树的值域之间的，因为在子树值域中间不忧（可以推式子，最后会变成一个一次函数，不要像我一样考场上推错了）。

而子树大小之和是给定的，把子树大小分成两部分最大化乘积，可以做背包，找到离和 $/2$ 最近的方案。具体实现需要卡常。

#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 1e6 + 5;
 
int siz[kMaxN], fa[kMaxN], n;
long long ans;
vector<int> e[kMaxN], v, t;
 
void dfs(int x, int f) {
  siz[x] = 1;
  fa[x] = f;
  for (int i : e[x]) {
    if (i != f) {
      dfs(i, x);
      siz[x] += siz[i];
    }
  }
}
 
template <size_t mx>
void solve(const vector<int> &v, int sum) {
  if (mx < size_t(sum / 2 + 1)) {
    solve<min(2 * mx, (size_t)5e5)>(v, sum);
    return;
  }
  bitset<mx + 5> dp;
  dp.set(mx);
  for (int i : v) {
    dp |= dp >> i;
  }
  int p = dp._Find_next(mx - sum / 2 - 1);
  ans += 1LL * (mx - p) * (sum - (mx - p));
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i <= n; i++) {
    int sum = 0, mx = 0;
    v.clear(), t.clear();
    for (int j : e[i]) {
      if (j != fa[i]) {
        v.emplace_back(siz[j]);
        mx = max(mx, siz[j]);
        sum += siz[j];
      }
    }
    if (v.size() <= 1) {
      continue;
    }
    if (v.size() == 2) {
      ans += 1LL * v[0] * v[1];
      continue;
    }
    if (v.size() == 3) {
      ans += max(1LL * v[0] * (v[1] + v[2]), max(1LL * v[1] * (v[0] + v[2]), 1LL * v[2] * (v[0] + v[1])));
      continue;
    }
    if (mx >= sum / 2) {
      ans += 1LL * mx * (sum - mx);
      continue;
    }
    sort(v.begin(), v.end());
    v.emplace_back(-1);
    int cnt = 1;
    for (int i = 1; i < v.size(); i++) {
      if (v[i] != v[i - 1]) {
        int x = v[i - 1], j = 1;
        for (; j < cnt; j *= 2) {
          t.emplace_back(x * j);
          cnt -= j;
        }
        t.emplace_back(x * cnt);
        cnt = 1;
      } else {
        cnt++;
      }
    }
    solve<8>(t, sum);
  }
  cout << ans << '\n';
  return 0;
}

日记和编辑器

平衡树

直接写的 STL 暴力。成功获得 $64$ 分。

正解是文艺平衡树，先简单解决前四问，然后最后一问要科技（大概是动态维护 fail 指针)。

总结

总分： $72 + 80 + 96 + 64 = 312$ 。

Haokee Note

Explorer

2025.9.30 模拟赛

日记和最短路

日记和欧拉函数

日记和二叉搜索树

日记和编辑器

总结

Graph View

Table of Contents