Logo lxn 的博客

博客

20261114-noip- 模拟赛题解

avatar lxn 2026-11-21 11:32:51

T1 - string

首先要让 $t$ 跟 $s$ 前面相同的部分尽可能多。

如果 $s$ 倒数第 $k$ 位是 1,可以让 $t$ 的最后 $k$ 位和 $s$ 都不一样。这样满足条件。

如果不是的话,为了前面相同部分尽量多,要修改的 1 就是倒数第 $k$ 位之前的第一个了。剩下的位其实就可以任意填了,先把所有零变成一,再尽量少的把一变成零就好了。

T2 - maimai

题目里的一次次出行其实就是进行了一种链剖分。dfs 一下,先算出来所有子树的信息,现在只要决定当前点归属子树里的哪条链就好了。因为要最大化最小值又最小化最大值,所以选最短的那条链一定正确。

T3 - bug

对于 bug 所在的行,写出 dp 方程:

$$ f_i = \min_{0 \le j < i} f_j + (i - j)^4 + a_i $$

观察到可以一直选一个,这样的话 $f_i \le n^2$。所以当 $(i - j)^4 \ge n^2$ 时就不用枚举了,只用枚举 $j$ 的一个后缀即可。最多就是 $O(\sqrt{n})$ 个。写成 std 的样子复杂度也是对的。

T4 - canteen

考虑预处理出每个点最近的电动车距离 $d_i$,这个可以 bfs 也可以两遍 dfs 算子树里的和子树外的。

接下来就只用考虑路径上的了,如果在 $p$ 位置出走寻找电动车,答案就是

$$ 2dis(x, p) + 3d_p + dis(p, y) $$

这个东西可以直接数据结构维护了。

刚开始写的是树剖加线段树,不过后来发现可以树上倍增。找到 lca 之后对两边分别求就好了,维护的就是一个 $3d_i + deep_i$ 之类的最小值。

20261114-ds题解

题目 核心结论 复杂度
不同位置(string) 第一处不同位置取“最靠右且仍能凑够 $k$ 位不同”的 1,之后尽量放 1,不足时把最靠右的 1 改成 0 $O(n)$
唉舞萌痴(maimai) 答案等于“按每个点选最短儿子链”把树剖成的若干条链长度的极差 $O(n)$
代码调试(bug) 区间 DP:$dp_i=\min_{j $O(37m)=O(m)$
向食堂奔去(canteen) $\text{ans}=\min\big(2d(x,y),\ D+\min_{v\in\text{path}}(d(x,v)+3\,nb(v))\big)$,$nb$ 为到最近电动车的距离 $O((n+q)\log n)$

四个标准程序见 source/ds/(string.cpp、maimai.cpp、bug.cpp、canteen.cpp),原来的两份错解保留为 source/ds/string_wa.cpp、source/ds/canteen_wa.cpp 供对照。下面逐题说明。


不同位置(string)

题意

给定长度为 $n$ 的 01 串 $s$($s_1=$1)与 $k$,求字典序最大的长度为 $n$ 的 01 串 $t$,满足 $t\le s$ 且 $s,t$ 的不同位数 $\ge k$;无解输出 -1。

分析

第一步:确定第一处不同位置

$k=0$ 时显然取 $t=s$。

$k>0$ 时 $t\neq s$。设 $p$ 是 $s,t$ 的第一处不同位置($1$ 下标)。由 $t\le s$ 且 $t\neq s$ 知 $$s_1=t_1,\ s_2=t_2,\ \dots,\ s_{p-1}=t_{p-1},\qquad s_p=\texttt{1},\ t_p=\texttt{0}.$$ 也就是说,**$p$ 必须满足 $s_p=$1**。

再看不同位数:位置 $1\sim p-1$ 全部相同,位置 $p\sim n$ 一共 $n-p+1$ 位,最多全部不同,所以 $$\text{不同位数}\le n-p+1.$$ 于是 $p$ 可行当且仅当 $$s_p=\texttt{1}\quad\text{且}\quad n-p+1\ge k.$$

记可行位置集合 $P=\{p:s_p=\texttt{1},\ n-p+1\ge k\}$。由于 $s_1=$1 且 $k\le n$,有 $1\in P$,故 $P$ 非空。

$p$ 越大,答案的字典序越大。 因为若 $p_11($p_1\in P$);而第一处不同位置为 $p_1$ 的串在第 $p_1$ 位是 0。两者在第 $p_1$ 位一为 1 一为 0,故前者更大。

因此取 $$p^*=\max P,$$ 即**从右往左找到第一个满足 $n-p+1\ge k$ 的 1**。

第二步:固定 $p^*$ 后构造字典序最大的 $t$

固定第一处不同位置为 $p$ 后,为了字典序最大,显然希望后面每一位尽量是 1。

先令 $$t=s_1s_2\cdots s_{p-1}\,\texttt{0}\,\underbrace{\texttt{11}\cdots\texttt{1}}_{n-p\ \text{个}},$$ 此时不同位数为 $$d=1+\#\{j>p:s_j=\texttt{0}\}.$$ 若 $d\ge k$,这就是答案。

若 $d1 的位置(把 $t_j$ 从 1 改成 0,恰好新增 $1$ 位不同)。为了让 $t$ 尽量大,被改成 0 的位置越靠右越好,所以把后缀中最靠右的 $r$ 个 1 改成 0。

这样做的可行性:后缀中 1 的个数为 $(n-p+1)-1-\#\{s_j=0\}$,于是 $$d+\#\{j>p:s_j=\texttt{1}\}=n-p+1\ge k,$$ 即需要的 $r$ 个 1 一定存在。

复杂度

每个位置只被扫常数次,$O(n)$ 时间、$O(n)$ 空间。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    long long k;
    if (!(cin >> s)) return 0;
    cin >> k;
    int n = (int)s.size();

    if (k == 0) {                       // t = s
        cout << s << '\n';
        return 0;
    }

    // 最靠右、且 n-p+1 >= k 的 '1'(代码中 p 是 0 下标)
    int p = -1;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '1' && (long long)(n - i) >= k) { p = i; break; }
    }
    if (p < 0) {                        // 数据保证不会发生
        cout << -1 << '\n';
        return 0;
    }

    string t = s;
    t[p] = '0';
    for (int j = p + 1; j < n; ++j) t[j] = '1';

    long long dif = 1;
    for (int j = p + 1; j < n; ++j)
        if (s[j] == '0') ++dif;

    if (dif < k) {                      // 把最靠右的一些 '1' 改成 '0'
        long long need = k - dif;
        for (int j = n - 1; j > p && need > 0; --j) {
            if (s[j] == '1') { t[j] = '0'; --need; }
        }
    }
    cout << t << '\n';
    return 0;
}

部分分

  • 测试点 $1$:$k=0$,输出 $s$。
  • 测试点 $2$:$k=n$,此时必须每一位都不同,唯一候选是按位取反,直接输出。
  • 测试点 $3\sim4$:$s$ 的倒数第 $k$ 位为 1,即 $p=n-k+1$ 一定可行,因此第一处不同位置就是它;用上面的构造即可(注意仍要处理“需要补足不同位数”的情况)。
  • 测试点 $5\sim7$:$n\le10$,枚举所有 $2^n$ 个 $t$,取满足条件者中字典序最大的,$O(2^nn)$。
  • 测试点 $8$:$n\le1000$,枚举第一处不同位置 $p$,按上面的方法 $O(n)$ 构造候选,共 $O(n^2)$。
  • 测试点 $9\sim10$:正解 $O(n)$。

唉舞萌痴(maimai)

题意

以 $1$ 为根的树。每次从根出发走到一个未访问过的叶子,把路径上首次经过的点计数,直到所有叶子都被访问。求各次计数极差的最小值。

分析

第一步:把“访问顺序”翻译成“链分解”

设共有 $L$ 个叶子,把各次出行按顺序编号 $1,2,\dots,L$。对每个非根点 $u$,它第一次被访问,是在“子树 $u$ 中最早被选为终点的那个叶子”对应的那次出行。因此:

每个非根点 $u$ 被“分配”给它子树中最早被访问的叶子 $\mathrm{first}(u)$;一次出行的计数 = 分配给该叶子的点数。

于是问题变成:给每个内部点 $u$ 指定一个“优先儿子” $pref(u)$(即包含 $u$ 子树中最早被访问的叶子的那个儿子),则所有点按优先关系被拆成若干条链:链的顶端要么是 $1$ 的儿子,要么是某个内部点的“非优先儿子”。一次出行的计数,恰好是它所对应链的长度。

反过来,任意指定“每个内部点选一个优先儿子”都能被实现:从根开始 DFS,每次先走优先儿子,按 DFS 序访问叶子即可。

于是问题等价于:

每个内部点选择一个优先儿子,把树拆成若干条链,使得链长度的极差最小。其中链长定义为 $len(u)$:叶子为 $1$,否则 $len(u)=1+len(pref(u))$。

第二步:贪心策略

显然应当让每个点优先走向链最短的儿子:取 $$pref(u)=\arg\min_{v\in son(u)} len(v),\qquad len(u)=1+\min_{v\in son(u)} len(v).$$ 自底向上即可求出所有 $len$,再收集所有链顶的 $len$ 得到链长集合 $S$,答案 $=\max S-\min S$。

链顶为:根的所有儿子(根不参与任何链),以及每个非根内部点的所有非优先儿子。

第三步:证明贪心最优(交换论证)

设某个方案中,内部点 $u$ 优先选择了 $a$,而存在另一个儿子 $b$ 满足 $len(b)

把 $u$ 的优先儿子改为 $b$。记 $d=len(a)-len(b)>0$。

  • 包含 $u$ 的那条链的长度减少 $d$(该链长度 $L\ge len(u)=1+len(a)>len(a)$);
  • 原来 $b$ 是链顶,链长 $len(b)$ 消失;$a$ 变成新的链顶,链长 $len(a)$ 出现。

因此链长集合的变化是: $$\{L,\ len(b)\}\ \longrightarrow\ \{L-d,\ len(a)\}.$$

  • 最大值不增大:$L-d
  • 最小值不减小:$len(a)>len(b)$,且 $L-d\ge len(u)-d=1+len(b)>len(b)$。原来若有比 $len(b)$ 更小的元素,它不受影响;否则 $len(b)$ 是唯一最小值,交换后最小值变大。

所以极差不会变大,且所有 $len$ 之和严格减少。不断交换,最终每个点都优先选择 $len$ 最小的儿子,即贪心方案;故贪心最优。

复杂度

自底向上一次即可,$O(n)$ 时间、$O(n)$ 空间。输入保证 $p_i\le i$,所以儿子编号一定大于父亲,倒序处理就是自底向上。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("maimai.in", "r", stdin);
    freopen("maimai.out", "w", stdout);
    int n;
    if (scanf("%d", &n) != 1) return 0;
    if (n == 1) { printf("0\n"); return 0; }

    vector<vector<int>> g(n + 1);
    for (int i = 2; i <= n; ++i) {
        int p; scanf("%d", &p);
        g[p].push_back(i);
    }

    vector<int> len(n + 1, 0);
    vector<int> chain;
    chain.reserve(n);

    for (int u = n; u >= 2; --u) {          // p_i<=i,倒序即自底向上
        if (g[u].empty()) {
            len[u] = 1;
        } else {
            int mv = g[u][0];
            for (int v : g[u]) if (len[v] < len[mv]) mv = v;
            len[u] = len[mv] + 1;
            for (int v : g[u]) if (v != mv) chain.push_back(len[v]);
        }
    }
    for (int v : g[1]) chain.push_back(len[v]);   // 根的儿子都是链顶

    int mn = chain[0], mx = chain[0];
    for (int x : chain) { mn = min(mn, x); mx = max(mx, x); }
    printf("%d\n", mx - mn);
    return 0;
}

部分分

  • 测试点 $1\sim3$:$n\le10$,枚举所有叶子访问顺序,$O(n!\cdot n)$ 暴力。
  • 测试点 $4\sim6$:叶子数 $<10$,叶子顺序只有不到 $10!$ 种,枚举即可。
  • 测试点 $7\sim8$:只有 $1$ 号点度数可能大于 $2$,树是若干条从 $1$ 出发的链,每条链的贡献就是链长,答案 $=\max$ 链长 $-\min$ 链长。
  • 测试点 $9\sim16$:较小规模,可以暴力/枚举验证结论。
  • 测试点 $17\sim20$:上面的 $O(n)$ 做法。

代码调试(bug)

题意

$n$ 行代码,$m$ 个 bug 在 $a_1

分析

第一步:操作的形状

一次操作修复的是“当前仍存在的、位置 $\le i$ 的所有 bug”。因此任一时刻已修复的 bug 一定是排序后的一个前缀:第一次操作修掉前 $k_1$ 个,第二次再往后修一段,……

又因为修掉“第 $j+1\sim i$ 个 bug”时,运行位置取 $a_i$ 即可(再往右只会增加运行时间,往左则修不掉第 $i$ 个),所以可以把每个操作看成一个块:一次修掉连续一段 $a_{j+1},\dots,a_i$,代价为 $$a_i+(i-j)^4.$$

第二步:DP

设 $dp_i$ 表示修掉前 $i$ 个 bug 的最小总时间,则 $$dp_0=0,\qquad dp_i=\min_{0\le j

第三步:块长上界(关键优化)

结论:最优方案中每块大小不超过 $37$(当 $n\le2\times10^5$ 时)。

证明:设某个最优方案中有一块大小 $x\ge38$,它修的是第 $j+1\sim i$ 个 bug。把这一块从末尾拆成两块:

  • 第 $j+1\sim i-1$ 个(大小 $x-1$),运行到 $a_{i-1}$;
  • 第 $i$ 个(大小 $1$),运行到 $a_i$。

原代价为 $a_i+x^4$,新代价为 $$\big(a_{i-1}+(x-1)^4\big)+\big(a_i+1\big).$$ 新方案更优当且仅当 $$a_{i-1}+1

于是每个 $dp_i$ 只需枚举最近的 $37$ 个 $j$: $$dp_i=\min_{i-37\le j

注意用 long long(答案可达 $10^{10}$ 量级);同时由于块长 $\le37$,$x^4$ 不会溢出。下标从 $0$ 开始的写法里转移范围是 $j\in[\max(0,i-37),i-1]$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("bug.in", "r", stdin);
    freopen("bug.out", "w", stdout);
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<long long> a(m + 1);
    for (int i = 1; i <= m; ++i) scanf("%lld", &a[i]);

    const long long INF = (long long)4e18;
    vector<long long> dp(m + 1, INF);
    dp[0] = 0;
    const int LIM = 37;

    for (int i = 1; i <= m; ++i) {
        long long best = INF;
        for (int j = i - 1; j >= 0 && i - j <= LIM; --j) {
            long long x = i - j;
            long long cost = dp[j] + a[i] + x * x * x * x;
            if (cost < best) best = cost;
        }
        dp[i] = best;
    }
    printf("%lld\n", dp[m]);
    return 0;
}

部分分

  • 测试点 $1\sim2$:$n\le15$,直接状压/暴搜或 $O(m^2)$ DP。
  • 测试点 $3\sim4$:$m\le15$,$O(m^2)$ DP。
  • 测试点 $5\sim6$:$m\le2000$,$O(m^2)$ DP 即可(约 $4\times10^6$)。
  • 测试点 $7$:$n=m$,即 $a_i=i$,用块长上界后同样是 $O(m)$。
  • 测试点 $8\sim10$:块长上界 + $O(37m)$ DP。

向食堂奔去(canteen)

题意

树上 $m$ 个点有电动车。步行每边耗时 $2$;在某个有电动车的点可以花 $0$ 时间上车,之后每边耗时 $1$,一路骑到食堂。也可以全程步行。多组询问 $(x,y)$,求最短时间。

分析

第一步:写出答案

记 $d(u,v)$ 为树上距离,$B$ 为电动车点集,$D=d(x,y)$。

  • 全程步行:$2D$。
  • 在 $b\in B$ 上车:先步行 $x\to b$,再骑行 $b\to y$,耗时 $2d(x,b)+d(b,y)$。

故 $$\text{ans}=\min\Big(2D,\ \min_{b\in B}\big(2d(x,b)+d(b,y)\big)\Big).$$ ($b=x$ 且 $x$ 有车的情形、$x=y$ 的情形都被包含。)

第二步:把“枚举车”化为“路径上的最小值”

对每个 $b$,设 $p$ 是 $b$ 到路径 $x\to y$ 的投影点(即 $b$ 与路径的交点),$h=d(p,b)$。则 $$d(x,b)=d(x,p)+h,\qquad d(b,y)=d(p,y)+h,$$ 于是 $$2d(x,b)+d(b,y)=2d(x,p)+2h+d(p,y)+h=D+d(x,p)+3h. \tag{1}$$

另一方面,令 $$nb(v)=\min_{b\in B}d(v,b)$$ 为到最近电动车的距离。对路径上任意 $v$ 与任意 $b$,有 $d(v,b)=d(v,p_b)+h_b$,故 $$d(x,v)+3d(v,b)=d(x,v)+3d(v,p_b)+3h_b\ \ge\ d(x,p_b)+3h_b,$$ 等号在 $v=p_b$ 时取到(这里用到 $d(x,v)+3d(v,p)\ge d(x,p)$)。于是 $$\min_{v\in\text{path}(x,y)}\big(d(x,v)+3nb(v)\big)=\min_{b\in B}\big(d(x,p_b)+3h_b\big). \tag{2}$$

由 $(1)(2)$ 得 $$\boxed{\ \min_{b\in B}\big(2d(x,b)+d(b,y)\big)=D+\min_{v\in\text{path}(x,y)}\big(d(x,v)+3nb(v)\big).\ }$$

于是 $\text{ans}=\min\big(2D,\ D+\min\limits_{v\in\text{path}}(d(x,v)+3nb(v))\big)$。

第三步:$nb$ 与路径最小值

  • $nb(v)$:把所有电动车点入队做多源 BFS,$O(n)$。
  • 询问:设 $l=\mathrm{lca}(x,y)$,把路径拆成 $x\to l$ 与 $l\to y$ 两段。

    • $v$ 在 $x\to l$ 上:$d(x,v)=dep_x-dep_v$,故 $$d(x,v)+3nb(v)=dep_x+\big(3nb(v)-dep_v\big).$$
    • $v$ 在 $l\to y$ 上:$d(x,v)=dep_x+dep_v-2dep_l$,故 $$d(x,v)+3nb(v)=\big(dep_x-2dep_l\big)+\big(3nb(v)+dep_v\big).$$

    因此只需在树上维护两个值 $$A(v)=3nb(v)-dep_v,\qquad B(v)=3nb(v)+dep_v,$$ 并支持“查询某点到其祖先这一段上的最小值”。

    用倍增同时维护祖先表和“向上 $2^j$ 个点的 $A/B$ 最小值”:

    • up[j][v] = up[j-1][ up[j-1][v] ]
    • mnA[j][v] = min(mnA[j-1][v], mnA[j-1][ up[j-1][v] ]),mnB 同理。

    询问时一边跳一边取 min,LCA 也可以用同一套表求出,单次询问 $O(\log n)$。

复杂度

$O(n)$ 建 $nb$,$O(n\log n)$ 建倍增表,$O(q\log n)$ 询问;空间 $O(n\log n)$。$n=5\times10^5$ 时倍增表约 $20\times5\times10^5\times3$ 个 int,约 $120$ MB,在 $512$ MB 限制内。

参考代码

/*
本来的距离 depx+depy-dep_lca(x,y),现在要加上找电动车的时间

// 向食堂奔去(canteen)—— 标准解法
//
// 记 d(u,v) 为树上距离,B 为有电动车的点集。小圈要么全程步行(耗时 2*d(x,y)),
// 要么步行到某个电动车点 b 后一路骑到食堂(耗时 2*d(x,b)+d(b,y)),故
//     ans = min( 2*d(x,y),  min_{b in B} ( 2*d(x,b) + d(b,y) ) ).
//
// 记 nb(v) = min_{b in B} d(v,b)(多源 BFS 求出)。对任一 b,设 p 为 b 到
// 路径 (x,y) 的投影点,则 d(x,b)=d(x,p)+h,d(b,y)=d(y,p)+h(h=d(p,b)),于是
//   2*d(x,b)+d(b,y) = D + d(x,p) + 3h,  D = d(x,y).
// 反过来对路径上任一点 v,
//   min_b [ d(x,v)+3*d(v,b) ] = d(x,p_b)+3*d(p_b,b) ,
// 故  min_b (2d(x,b)+d(b,y)) = D + min_{v in path(x,y)} ( d(x,v) + 3*nb(v) ).
//
// 以 1 为根,令 l = lca(x,y),把路径拆成两段,各自化为一维的“祖先链最小值”:
//   v 在 x->l 段: d(x,v)+3nb(v) = dep[x] + ( -dep[v]+3nb[v] )
//   v 在 l->y 段: d(x,v)+3nb(v) = dep[x]-2dep[l] + ( dep[v]+3nb[v] )
// 用倍增同时维护祖先、两套链上最小值,单次询问 O(log n)。
// 复杂度:O((n+q) log n),空间 O(n log n)。
*/
//https://qoj.ac/submission/3390131
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 501000;
int n, m, Q, d[N], dep[N], f[20][N], disl[20][N], disr[20][N];
vector<int> e[N];

int lca(int x, int y) {//普通倍增求LCA
    if (dep[x] < dep[y]) 
        swap(x, y);
    for (int i = 19; i >= 0; i--) 
        if (dep[f[i][x]] >= dep[y]) 
            x = f[i][x];
    if (x == y) 
        return x;
    for (int i = 19; i >= 0; i--) 
        if (f[i][x] != f[i][y]) {
            x = f[i][x];
            y = f[i][y];
        }
    return f[0][x];
}

int getl(int x, int y) {//从x到lca这段骑上车了
    int res = d[x] * 3 - dep[x];
    for (int i = 19; i >= 0; i--) 
        if (dep[f[i][x]] >= dep[y]) {
            res = min(res, disl[i][x]);
            x = f[i][x];
        }
    return res;
}
int getr(int x, int y) {//从lca开始先找车再去食堂
    int res = d[x] * 3 + dep[x];
    for (int i = 19; i >= 0; i--) 
        if (dep[f[i][x]] >= dep[y]) {
            res = min(res, disr[i][x]);
            x = f[i][x];
        }
    return res;
}

char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57){
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
       return x*f;
}

int main() {
//    freopen("canteen.in", "r", stdin);
//    freopen("canteen.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(d, 127, sizeof(d));
    queue<int> q;
    for (int i = 1; i <= m; i++) {
        int x = read();
        d[x] = 0;
        q.push(x);
    }
    while (!q.empty()) {//多源最短路,找到一个点距离最近的电动车
        int x = q.front();
        q.pop();
        for (auto y : e[x]) 
            if (d[y] > d[x] + 1) {
                d[y] = d[x] + 1;
                q.push(y);
            }
    }
    q.push(1);
    dep[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto y : e[x]) 
            if (!dep[y]) {
                dep[y] = dep[x] + 1;
                f[0][y] = x;//父节点
                disl[0][y] = d[x] * 3 - dep[x];//
                disr[0][y] = d[x] * 3 + dep[x];
                q.push(y);
            }
    }
    for (int i = 1; i < 20; i++) 
        for (int u = 1; u <= n; u++) {
            f[i][u] = f[i - 1][f[i - 1][u]];
            disl[i][u] = min(disl[i - 1][u], disl[i - 1][f[i - 1][u]]);
            disr[i][u] = min(disr[i - 1][u], disr[i - 1][f[i - 1][u]]);
        }
    Q = read();
    while (Q--) {
        int x = read(), y = read();
        int _lca = lca(x, y);
        int dist = dep[x] + dep[y] - dep[lca(x, y)] - dep[lca(x, y)];
        int l = dist + dep[x] + getl(x, _lca);//dist+dep[x]-dep[v]+3*v点找车  x到v的花费是2倍
        int r = (dist << 1) - dep[y] + getr(y, _lca);// 总的2被- y到v的花费是1倍。-(dep[y]-dep[v])+3*v点找车
//因此需要维护 路径上的    -dep[v]+3*h(v) 或者 dep[v]+3*h(v);    
printf("%d\n", min({l, r, dist << 1}));
    }
}

完整可编译版本(含快速读入与输出)见 source/ds/canteen.cpp。

部分分

  • 测试点 $1\sim3$:$n,q\le100$,每次询问从 $x$ 做 BFS 求到所有点距离,再枚举电动车,$O(nm)$ 每次。
  • 测试点 $4\sim6$:$n,q\le2000$,两两距离可以 $O(n^2)$ 预处理(或每次询问 BFS),每次询问枚举 $m$ 辆车,$O(nq+qm)$。
  • 测试点 $7\sim8$:$m\le10$,用倍增求 $d(x,b),d(b,y)$,每次询问枚举至多 $10$ 辆车,$O(m\log n)$ 每次。
  • 测试点 $9\sim10$(链):链上路径就是一段区间,$nb$ 也是一维的,用线段树/ST 表维护 $d(x,v)+3nb(v)$ 的区间最小值即可。
  • 测试点 $16\sim17$:$O((n+q)\log n)$ 的正解,或 $O(n\sqrt n)$ 一类的做法。
  • 测试点 $18\sim20$:正解。

其余特殊测试点(随机树、随机电动车)只是用来区分不同复杂度的做法;正解与树的形态无关。


小结

题目 易错点
string 忘了“补足不同位数”时要把最靠右的 1 改成 0;输出 -1 的判断
maimai 需要把“访问顺序”与“链分解”对应起来,并用交换论证证明贪心
bug $x^4$ 可能溢出,需要 long long;用块长上界把 $O(m^2)$ 优化到 $O(m)$
canteen 别忘记“全程步行”这一选项;把“枚举车”化为“路径上的最小值”是突破口

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。

lxn Avatar
活跃度 近 53 周
查看全年