二次元修炼日记！

🔒 本文已加密，请输入密码

前言

这里是一个二次元的堕落之路啦，虽然窝觉得也没人能看到这里~

看番的口味从奇幻到党争到百合再到萌豚，说明越来越躺平摆烂了，事情实在太多，有时候腾出点时间写写博客就是莫大的消遣了。

好吧，也许ICS的笔记应该排除在外，不过谁会拒绝可爱的二次元纸片人呢哈哈哈，光是看着就很治愈耶~

那么进入正题，为什么要开始写这一篇长期更新的博文？

众所周知，Codeforces的题目，思维要求非常灵活，并且目前我所在的分段，刚好就是拼Div2前几道题的思维与手速。

因此，进行复盘是非常必要的，包括我之前板刷的时候，不时会发现自己赛时会做但是第二次不会的情况。

希望在未来一年里Rating能有所进步，加油加油！

By Elainafan，2025.11.29，写于发烧之时

看番日记

Date	Round	div	id	sol	rk	perf	A	B	C	D	E	F	G
2025.10.12	R1058	div2	2160	3	vp	vp	√	√	√
2025.10.19	R1060	div2	2154	3	3145	1536	√	√	√
2025.10.25	R1061	div2	2156	2	9898	1033	√	√	B
2025.10.28	R1062	div4	2167	5	vp	vp	√	√	√	√			√
2025.11.10	R1063	div2	2163	2	2470	1582	√		√
2025.11.14	Edu184	edu	2169	3	4838	1333	H	√	√	√
2025.11.20	R1065	div3	2171	5	2504	1474	√	√	√	√	√		B
2025.11.28	Edu185	edu	2170	3	1885	1658	√	√	√
2025.11.29	R1067	div2	2158	3	2812	1490	√	√	√
2025.12.03	R1064	div1/2	2166	3	vp	1483	√	√	√
2025.12.05	R1068	div2	2173	3	2748	1532	√	√	√
2025.12.06	R1069	div1/2	2175	3	934	1728	√	√	√	B
2025.12.11	R1070	div2	2176	3	2051	1611	√	√	√	B
2025.12.17	GR30	div1+2	2164	3	vp	1521	√	√	√
2025.12.19	GR31	div1+2	2180	3	1870	1800	√	√	√	B
2025.12.23	R1071	div3	2179	5	1266	1758	√	√	√	√	√	B
2025.12.29	Edu186	edu	2182	3	5418	1256	√	√	√	B	B
2026.01.07	Gb 2025	div1+2	2178	4	vp	1642	√	√	√	√	B
2026.01.07	Hello 2026	div1+2	2183	4	1989	1786	√	√	√	√
2026.01.12	R1072	div3	2184	6	822	1921	√	√	√	√	√	√	B
2026.01.17	R1073	div1/2	2191	4	4312	1330	√	√	√	√	B
2026.01.18	R1074	div4	2185	7	679	1997	√	√	√	√	√	√	√
2026.01.23	R1075	div1/2	2189	3	3891	1429	√	√	√	B	B
2026.01.25	R1076	div3	2193	5	2619	1464	√	√	√	H	√	√	B

Codeforces Round #1072(Div.3)

第一次在d3做出六道题，事实上G理论也能出，只是AB花太多时间了，唉唉我的AK。

也是第一次写这样的博文，瞎写的，多多见谅~

C Huge Pile

题目大意：有一堆大小为 $n$ 的苹果，每次可以对一堆苹果进行操作，将其分为大小为 $\lfloor \frac{n}{2} \rfloor$ 和 $\lceil \frac{n}{2} \rceil$ 的两堆，问能否得到大小为 $k$ 的一堆，若能请给出最少操作次数。

数据范围： $1 \leq n,k \leq 10^9$

思路：就是裸的DFS啊，这个时间复杂度绝对不会爆的，放心放心~

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


void solve() {
    ll n, k;
    cin >> n >> k;
    if (n < k) {
        cout << -1 << endl;
        return;
    }
    int ans = INT_MAX;
    map<ll, int> ma;
    auto dfs = [&](this auto&& dfs, ll x, int t) {
        if (ma.count(x)) return;
        if (x < k) return;
        ma[x]++;
        if (x == k) {
            ans = min(ans, t);
            return;
        }
        if (x % 2 == 0)
            dfs(x / 2, t + 1);
        else {
            dfs(x / 2, t + 1);
            dfs(x / 2 + 1, t + 1);
        }
        return;
    };
    dfs(n, 0);
    if (ans == INT_MAX)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return;
}

D Unfair Game

题目大意：Alice跟Bob玩游戏，Alice每次可以进行两种操作中的其中一种，即将当前数减一或者将当前数除以2（必须是偶数时才能进行），当Alice将这个数变为0时，她就获胜了。给出 $n=2^d$ ，Bob需要求出 $1 \sim n$ 中，作为初始值无法使Alice在 $k$ 个回合内获胜的个数。

数据范围： $1 \leq n,k \leq 10^9$

思路：考虑最高位为第 $i$ 位时，在 $1 \sim (i-1)$ 位共有 $j$ 位为0，则低位共有 $i-1-j$ 个1，每个1提供2步的容错，每个0跟最高位1提供1步的容错，因此一共需要 $2*(i-1-j)+j+1=2*i-j-1$ 步，考虑当其 $>k$ 时的组合数即可，注意组合数初始化的方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


ll cn[32][32];
void init() {
    for (int i = 0; i <= 31; i++) {
        cn[i][0] = cn[i][i] = 1;
        for (int j = 1; j < i; j++) {
            cn[i][j] = cn[i - 1][j - 1] + cn[i - 1][j];
        }
    }
}
void solve() {
    int n, k;
    cin >> n >> k;
    int tem = __lg(n);
    tem++;
    ll ans = 0;
    for (int i = 1; i <= tem - 1; i++) {
        if (2 * i - 1 <= k) continue;
        for (int j = 0; j <= i - 1; j++) {
            if (2 * i - j - 1 > k) ans += cn[i - 1][j];
        }
    }
    if (tem > k) ans++;
    cout << ans << endl;
    return;
}

E Exquisite Array

题目大意：如果一个数组至少有两个元素，且其中任意相邻元素至少相差 $k$ ，称其为 $k-$ 数组。给定一个 $1 \sim n$ 的排列，请求出从 $k \in {1 \sim n-1}$ 的 $k-$ 子数组个数。

数据范围： $2 \leq n \leq 10^5$

思路：首先预处理出所有相邻元素之间的差值。考虑贡献法，先用单调栈处理出某个差值作为子数组最小值对应的贡献，倒着遍历 $n-1 \sim 1$ ，如果当前差值刚好等于 $i$ ，则考虑其作为子数组最小元素的贡献，并累加到总值中即可，注意相邻差值若相等，两侧预处理时一侧有等号一侧没有等号，算是比较板的题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    vector<int> res(n - 1);
    vector<int> diff(n - 1);
    for (int i = 0; i < n - 1; i++) diff[i] = abs(a[i + 1] - a[i]);
    vector<int> r(n - 1, n - 1);
    vector<int> l(n - 1, -1);
    stack<int> s;
    vector<vector<int>> ma(n);
    for (int i = 0; i < n - 1; i++) ma[diff[i]].push_back(i);
    for (int i = n - 2; i >= 0; i--) {
        while (!s.empty() && diff[s.top()] >= diff[i]) s.pop();
        if (!s.empty()) r[i] = s.top();
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 0; i <= n - 2; i++) {
        while (!s.empty() && diff[s.top()] > diff[i]) s.pop();
        if (!s.empty()) l[i] = s.top();
        s.push(i);
    }
    vector<ll> ans(n);
    ll cnt = 0;
    for (int i = n - 1; i >= 1; i--) {
        for (int p : ma[i]) {
            cnt += 1LL * (r[p] - p) * (p - l[p]);
        }
        ans[i] = cnt;
    }
    for (int i = 1; i <= n - 1; i++) cout << ans[i] << ' ';
    cout << endl;
    return;
}

注：本题似乎还存在并查集+链表的做法，放一个朋友的提交链接在这里Kita3’s submission 。

F Cherry Tree

题目大意：给一棵顶点编号为 $1 \sim n$ 的有根树，树根默认为1。每个叶子都有一颗樱桃，每次操作可以选择某个节点使以其为根的子树的所有叶子的樱桃掉落，若某个叶子的樱桃已经掉落则不能被摇动第二次，问是否能使摇动次数为3的倍数？

数据范围： $2 \leq n \leq 2 \cdot 10^5$

思路：一眼树上状态机，如果难点可以出树上背包？可以作为思考题。首先，需要知道的是对于某个非根节点，摇动它能节省的次数就是（以它为根子树的叶子数-1），然后就可以对每个节点维护，以其为根的子树中是否存在节省操作数模3的余数为1或为2的状态，逐步回传即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


void solve() {
    int n;
    cin >> n;
    int x, y;
    vector<vector<int>> ma(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    int ans = 0;
    for (int i = 0; i <= n - 1; i++) {
        if (ma[i].size() == 1 && i != 0) ans++;
    }
    if (ans % 3 == 0) {
        cout << "YES" << endl;
        return;
    }
    int r = ans % 3;
    bool flag = false;
    vector<int> mt(n);
    auto dfs = [&](this auto&& dfs, int x, int pa) -> int {
        if (ma[x].size() == 1 && pa != -1) return 1;
        int cnt = 0;
        int cnt1 = 0, cnt2 = 0;
        for (int p : ma[x]) {
            if (p == pa) continue;
            cnt += dfs(p, x);
        }
        mt[x] = cnt;
        if ((cnt + 2) % 3 == r) flag = true;
        return cnt;
    };
    auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> pair<bool, bool> {
        if (ma[x].size() == 1 && pa != -1) return {false, false};
        bool pd1 = false, pd2 = false;
        for (int p : ma[x]) {
            if (p == pa) continue;
            auto tem = dfs2(p, x);
            if (pd1 == true && tem.first) pd2 = true;
            if (pd2 == true && tem.second) pd1 = true;
            pd1 = pd1 | tem.first;
            pd2 = pd2 | tem.second;
        }
        if (r == 1 && pd1) flag = true;
        if (r == 2 && pd2) flag = true;
        if (mt[x] % 3 == 2) pd1 = true;
        if (mt[x] % 3 == 0) pd2 = true;
        return {pd1, pd2};
    };
    dfs(0, -1);
    dfs2(0, -1);
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return;
}

G Nastiness of Segments

题目大意：给定编号为 $1 \sim n$ 的 $n$ 个元素 $a_1,a_2,\ldots,a_n$ ，定义 $[l,r](1 \leq l \leq r \leq n)$ 的恶心度为满足 $\mathrm{min}(a_l,a_{l+1},\ldots,a_{l+d})=d, 0 \leq d \leq r-l$ 的 $d$ 的个数。

现在给定 $q$ 个查询，分别为操作1和操作2，操作1把 $a[idx]$ 改为 $x$ ，操作2查询 $[l,r]$ 的恶心度。

数据范围： $1 \leq n,q \leq 2 \cdot 10^5, 1 \leq a_i \leq 2 \cdot 10^5, 1 \leq x \leq 2 \cdot 10^5$

思路：首先，注意到 $\mathrm{min}(a_l,\ldots,a_{l+d})$ 为单调递减函数，而 $d$ 为严格单调递增函数，因此它们的交点至多只有一个。

一种显然的思路是，用线段树动态维护区间最小值，同时在 $[l,r]$ 上二分，线段树的查询复杂度为 $O(logn)$ ，因此总的时间复杂度为 $O(q logn logn)$

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114


template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return min(a, b); }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    } 

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }  // 传入一个数组维护

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); } // 查询[ql,qr]中第一个满足条件的下标

    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); } // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
    int n, q, op, x, y;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    SegmentTree tree(a);
    auto check = [&](this auto&& check, int l, int mid) -> bool {
        int tem = tree.query(l, mid);
        if (tem <= mid - l) return true;
        return false;
    };
    for (int i = 1; i <= q; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            tree.update(x - 1, y);
        } else {
            cin >> x >> y;
            int sl = --x, sr = --y;
            int l = sl, r = sr, mid;
            while (l + 1 < r) {
                mid = (l + r) / 2;
                if (check(sl, mid))
                    r = mid;
                else
                    l = mid;
            }
            if (tree.query(sl, r) == r - sl)
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }
    }
    return;
}

但是，这种做法并不是最优的，是否能直接进行线段树二分，把复杂度降到 $O(qlogn)$ ？这里先瞎放张图。

当然，上面是普通的线段树二分流程，而这题固定了左端点，就要考虑怎么求右端点了。

回想起线段树有个性质，即某个节点的左子树必然先于其右子树被遍历到，因此，到遍历到某个 $[l,r]$ ，则 $[1,l]$ 必然都被遍历过，因此若遍历到被 $[ql,qr]$ 完全包裹的区间 $[l,r]$ ，则代表之前所有的 $[ql,l)$ 都被遍历过了，而且都是以完全包裹的形式，因此可以使用一个全局变量（或者直接在查找时传引用），当完全包裹并且不行的时候就进行更新（因为如果行那么直接接着二分，直到不行被更新或者得到一个点）。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106


template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return min(a, b); }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T& val) const {
        if (r < ql || l > qr) return -1;
        if (ql <= l && r <= qr && min(tree[node], val) > r - ql) {
            val = min(tree[node], val);
            return -1;
        }
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }  // 传入一个数组维护

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    int find_first(int ql, int qr, T& val) const { return find_first(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中第一个满足条件的下标

    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
    int n, q, op, x, y;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    SegmentTree tree(a);
    for (int i = 1; i <= q; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            tree.update(x - 1, y);
        } else {
            cin >> x >> y;
            int sl = --x, sr = --y;
            int cur = INT_MAX;
            int tem = tree.find_first(sl, sr, cur);
            if (tem != -1 && tree.query(sl, tem) == tem - sl)
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }
    }
    return;
}

最后是灵神的点评：

Codeforces Round #1073(Div.2)

最近脑子不是很好使，掉大分。

C Sorting Game

题目大意：Alice和Bob在二进制字符串上博弈，Alice先手，双方轮流。

每个回合，选择一个非递增序列并将其排序，这个非递增序列必须同时包含0和1，最终无法下的人输棋。请确定胜者，若Alice获胜，则输出第一步。

数据范围： $1 \leq n \leq 2 \cdot 10^5$

思路：非常搞笑的是，这道题只有两种情况，即Alice一开始就下不了导致Bob赢棋，或者Alice一步赢下Bob。第一种情况就是整个字符串一开始就有序，第二种情况是Alice第一步将整个字符串中，最开始不应该属于自己位置的1，跟不应该属于自己位置的0对换。最近我确实就是缺少这种一眼看出只有两个答案的思维。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt0 = 0, cnt1 = 0;
    vector<int> res;
    for (int i = 0; i <= n - 1; i++) {
        if (s[i] == '0') {
            cnt0++;
        } else if (s[i] == '1')
            cnt1++;
    }
    vector<int> res1;
    for (int i = 0; i <= cnt0 - 1; i++) {
        if (s[i] == '1') res1.push_back(i + 1);
    }
    for (int i = cnt0; i <= n - 1; i++) {
        if (s[i] == '0') res.push_back(i + 1);
    }
    if (cnt1 == 0 || cnt0 == 0 || res1.size() == 0) {
        cout << "Bob" << endl;
        return;
    }
    cout << "Alice" << endl;
    cout << 2 * res1.size() << endl;
    for (int p : res1) cout << p << ' ';
    for (int p : res) cout << p << ' ';
    cout << endl;
    return;
}

D1 Sub-RBS(Easy)

题目大意：给定一个长度为 $n$ 的正则括号序列 $s$ ，请求出它的最长优子序列的长度。

优的定义为：必须为正则括号序列，被优的序列为其前缀或第一个不相等的位置，优子序列为(而被优子序列为)。

数据范围： $2 \leq n \leq 2 \cdot 10^5$

思路：需要最小化，那么当然是考虑跳过某个配对的括号序列，注意完全可以做到，对于(()()这样的序列，考虑是否只跳过一个)，注意到只需要后面少拿一个(，且只要能构成相应正则序列即可，如果后面都无法少拿一个(，那么显然就无法成立，答案为-1。而若能少拿，考虑将少拿的位置放在最前面，则考虑后面是否有至少2个(，因为如果少拿需要保证正则性会减掉一个。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int las = -1, tem = 1;
    int ans = INT_MAX;
    vector<int> res;
    for (int i = 1; i <= n - 1; i++) {
        if (s[i] == s[i - 1])
            tem++;
        else {
            res.push_back(tem);
            tem = 1;
        }
    }
    res.push_back(tem);
    int m = res.size();
    vector<int> maxx(m, 0);
    maxx[m - 2] = res[m - 2];
    for (int i = m - 4; i >= 0; i -= 2) {
        maxx[i] = maxx[i + 2] + res[i];
    }
    if (m > 2 && maxx[2] > 1)
        cout << n - 2 << endl;
    else
        cout << -1 << endl;
    return;
}

D2 Sub-RBS(Hard)

题目大意：给定一个长度为 $n$ 的括号序列 $s$ （不一定正则），请求出它的所有正则子序列的最长优子序列的长度和。

数据范围： $1 \leq n \leq 100$

思路：首先，需要发现一个思路，就是同D1中所讲，某个)之后必须要包含至少两个(，即形成)((结构，根据这个数据结构考虑使用动态规划计数，记录这个结构的形成程度（即0-3），而对于正则括号序列常见的表示形式是将其视为1和-1，即需要一个平衡度来记录，最终取平衡度为0的值，同时由于每次的条件为 $|n|-2$ ，因此可以记录总共的长度以及总共的个数，从而形成三维滚动（其实四维也可以）。说到底这题其实不难，就是考察基本功底了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


const int MOD = 998244353;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<array<array<ll, 2>, 4>> dp(n + 1);
    dp[0][0][0] = 1;
    for (auto c : s) {
        auto ndp = dp;
        for (int i = 0; i <= n; i++) {
            int tem = i + (c == ')' ? -1 : 1);
            if (tem < 0 || tem > n) continue;
            for (int j = 3; j >= 0; j--) {
                if (j < 3 && c == ")(("[j]) {
                    ndp[tem][j + 1][1] += dp[i][j][0] % MOD;
                    ndp[tem][j + 1][1] %= MOD;
                    ndp[tem][j + 1][1] += dp[i][j][1] % MOD;
                    ndp[tem][j + 1][1] %= MOD;
                    ndp[tem][j + 1][0] += dp[i][j][0] % MOD;
                    ndp[tem][j + 1][0] %= MOD;
                } else {
                    ndp[tem][j][1] += dp[i][j][0] % MOD;
                    ndp[tem][j][1] %= MOD;
                    ndp[tem][j][1] += dp[i][j][1] % MOD;
                    ndp[tem][j][1] %= MOD;
                    ndp[tem][j][0] += dp[i][j][0] % MOD;
                    ndp[tem][j][0] %= MOD;
                }
            }
        }
        dp = ndp;
    }
    cout << (dp[0][3][1] - 2 * dp[0][3][0] + 2 * MOD) % MOD << endl;
    return;
}

Codeforces Round #1074(Div.4)

D脑子抽了WA了五发，H不是我能做出来的，赛时出A-G差不多了，反正是Unr。

D OutOfMemoryError

题目大意：给定 $a_1,a_2,\ldots,a_n$ ，进行 $m$ 次操作，每次 $a_{b_i}+=c_i$ ，当任意元素大于 $h$ 时，所有元素重置回初始值，请求出最后的结果数。

数据范围： $1 \leq n,m \leq 2 \cdot 10^5,1 \leq h \leq 10^9$ ，其中 $n,m$ 的和不超过 $2 \cdot 10^5$ 。

思路：一开始想的就是模拟，但是没想到d4D就能上强度，直接吃了一发TLE，随后脑子有点蠢，一直想着二分最后一次重置或者倒序遍历，但是注意到重置只和顺序遍历有关，倒序或者二分会丢失这一信息，因此还是顺序遍历。

于是，顺序遍历怎么优化呢？由于每个数组的变化是稀疏的，因此完全可以用一个数组存储上次重置到这次的所有变化而不更新原数组，每次检测到重置则直接清空数组，最终用存储的变化更新原来数组就是最终结果，时间复杂度为 $O(N+M)$ 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


void solve() {
    int n, m, h;
    cin >> n >> m >> h;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    vector<int> b(m);
    vector<int> c(m);
    vector<int> diff(n);
    vector<int> re;
    for (int i = 0; i <= m - 1; i++) {
        cin >> b[i] >> c[i];
        diff[b[i] - 1] += c[i];
        re.push_back(i);
        if (diff[b[i] - 1] + a[b[i] - 1] > h) {
            for (int p : re) {
                diff[b[p] - 1] = 0;
            }
            re.clear();
        }
    }
    for (int i = 0; i <= n - 1; i++) cout << a[i] + diff[i] << ' ';
    cout << endl;
    return;
}

E The Robotic Rush

题目大意：在一条数轴上有 $n$ 个机器人和 $m$ 个障碍物，机器人走到障碍物上就会死。现在给定长度为 $k$ 的字符串，其为L则代表机器人全部往左走一步，反之全部往右走一步，问对于所有的 $i (1 \leq i \leq k)$ ，给出第 $i$ 步后活着的机器人数量。

数据范围： $1 \leq n,m,k \leq 2 \cdot 10^5$ ，它们的和不超过 $2 \cdot 10^5$

思路：注意到机器人如果死，必然是走到左右的障碍物死的，因此可以预处理轨迹的时间点，再预处理左右的距离，得到每个时间点死去的机器人数量，最后使用差分即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    vector<int> b(m);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    for (int i = 0; i <= m - 1; i++) cin >> b[i];
    ranges::sort(b);
    string s;
    cin >> s;
    vector<int> mo(k + 1);
    vector<int> l(n, INT_MIN);
    vector<int> r(n, INT_MAX);
    vector<int> die(k + 1, 0);
    map<int, int> ma;
    for (int i = 1; i <= k; i++) {
        if (s[i - 1] == 'L')
            mo[i] = mo[i - 1] - 1;
        else
            mo[i] = mo[i - 1] + 1;
        if (!ma.count(mo[i])) ma[mo[i]] = i;
    }
    for (int i = 0; i <= n - 1; i++) {
        auto x = ranges::lower_bound(b, a[i]);
        if (x == b.end()) {
            l[i] = *(--x) - a[i];
            if (ma.count(l[i])) die[ma[l[i]]]++;
        } else if (x == b.begin()) {
            r[i] = *x - a[i];
            if (ma.count(r[i])) die[ma[r[i]]]++;
        } else {
            r[i] = *x - a[i];
            l[i] = *(--x) - a[i];
            int tem = INT_MAX;
            if (ma.count(l[i])) tem = min(tem, ma[l[i]]);
            if (ma.count(r[i])) tem = min(tem, ma[r[i]]);
            if (tem != INT_MAX) die[tem]++;
        }
    }
    for (int i = 2; i <= k; i++) die[i] += die[i - 1];
    for (int i = 1; i <= k; i++) {
        cout << n - die[i] << ' ';
    }
    cout << endl;
    return;
}

F BattleCows

题目大意：现在给定 $2^n$ 头牛，它们有自己的技能等级 $a_i$ 并各自属于自己的一个栈，每个栈的总技能等级记为其中所有牛技能等级的异或和，现在会重复进行以下过程：奇数位置的栈与右边的栈进行战斗，技能等级较高的栈赢得比赛，若平局则奇数位置的赢得比赛。赢家会把自己的栈堆叠到输家上面，形成新的栈，如此直至最后只剩一个栈。

现有 $q$ 次查询，每次查询将牛 $b$ 的技能等级改变为 $c$ （注意是模拟改变，不是永久改变），问最终时有多少头牛在它上面。

数据范围： $1 \leq n \leq 18, 1 \leq q \leq 2 \cdot 10^5, 1 \leq a_i \leq 2^{30}, 1 \leq b \leq 2^n, 1 \leq c \leq 2^{30}$

思路：由于是动态查询和动态修改，很容易想到线段树。而整个过程就是类似二叉树自底向上的一个过程，只需要每次模拟需要查询的牛的所在位置，并用贡献法统计它周围栈比赛会跑到它上面的牛数量即可，经过估算发现复杂度为 $O(qn^2)$ ，显然是可以过的。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109


template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a ^ b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }  // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }  // 传入一个数组维护

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中第一个满足条件的下标

    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
    int n, q, b, c;
    cin >> n >> q;
    vector<int> a((1 << n));
    for (int i = 0; i <= (1 << n) - 1; i++) cin >> a[i];
    SegmentTree tree(a);
    for (int i = 1; i <= q; i++) {
        cin >> b >> c;
        b--;
        int tem = a[b];
        tree.update(b, c);
        int tem2 = b;
        int ans = 0;
        for (int j = 0; j <= n - 1; j++) {
            int tem3 = tem2 >> j;
            if (tem3 & 1) {
                int pre = tree.query(tem3 << j, (tem3 << j) + (1 << j) - 1);
                int pre2 = tree.query((tem3 - 1) << j, (tem3 << j) - 1);
                if (pre <= pre2) ans += (1 << j);
            } else {
                int pre = tree.query(tem3 << j, (tem3 << j) + (1 << j) - 1);
                int pre2 = tree.query((tem3 + 1) << j, ((tem3 + 1) << j) + (1 << j) - 1);
                if (pre < pre2) ans += (1 << j);
            }
        }
        tree.update(b, tem);
        cout << ans << endl;
    }
    return;
}

G Mixing MEXes

题目大意：给定 $n$ 个数组 $a_1,a_2,\ldots,a_n$ ，每个数组的长度为 $l_1,l_2,\ldots,l_n$ ，现在只进行一次以下操作，即选择 $1 \leq i \leq n$ 与 $1 \leq j \leq l_i$ ，将 $a_{ij}$ 添加到 $a_k ( k\not ={i})$ 中，求对于所有有序对 $(i,j,k)$ ， $\sum\limits_{i=1}^{n} \mathrm{MEX}(a_i)$ 。

数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq l_i \leq 10^5, 0 \leq a_i \leq 10^6$ ， $l_i$ 之和不超过 $2 \cdot 10^5$ 。

思路：看到这里肯定考虑贡献法，首先判断取出的数会不会影响当前数组的MEX，即它是否在MEX的范围内，且是否有替代，同时考虑加入的数组中会不会影响该数组的MEX，注意加入的数不一定是让当前数组的MEX+1，完全可能是连接上两段不相干的数，因此需要预处理原始MEX和可能存在的缝合一次后的MEX，并计算贡献。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


void solve() {
    int n;
    cin >> n;
    vector<int> l(n);
    vector<vector<int>> a(n);
    for (int i = 0; i <= n - 1; i++) {
        cin >> l[i];
        a[i].resize(l[i]);
        for (int j = 0; j < l[i]; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> mex(n, 0);
    ll tot = 0;
    ll ans = 0;
    vector<map<int, int>> ma(n);
    map<int, int> ma2;
    for (int i = 0; i <= n - 1; i++) {
        int cnt = 0;
        for (int& p : a[i]) ma[i][p]++;
        while (ma[i].count(cnt)) cnt++;
        mex[i] = cnt;
        tot += 1LL * cnt;
        int cnt2 = cnt + 1;
        while (ma[i].count(cnt2)) cnt2++;
        ma2[cnt] += cnt2 - cnt;
    }
    for (int i = 0; i <= n - 1; i++) {
        for (int j = 0; j <= l[i] - 1; j++) {
            if (a[i][j] <= mex[i]) {
                int tem = ma2[a[i][j]];
                if (ma[i][a[i][j]] >= 2) {
                    ans += (n - 1) * tot + 1LL * tem;
                } else {
                    ans += (n - 1) * tot + 1LL * tem;
                    ans -= 1LL * (n - 1) * (mex[i] - a[i][j]);
                }
            } else {
                int tem = ma2[a[i][j]];
                ans += (n - 1) * tot + 1LL * tem;
            }
        }
    }
    cout << ans << endl;
    return;
}

Codeforces R1076(Div.3)

非常的生气啊，本来可以一把开六道题爽爽地回蓝的，结果前缀和数组忘记开long long了，还碰上weak pretest了，于是D被hack，以后写前缀和必须开ll！。

至少证明了我是有1600的水平的，呜呜呜~

E Product Queries

题目大意：黑板上写有 $n$ 个 $1 \sim n$ 的数，每次允许选用其中任意一个元素进行乘法，求对于 $i \in [1,n],$ 最终乘积为 $i$ 的最小元素数。

数据范围： $1 \leq n \leq 3 \cdot 10^5$

思路：这题可以看出是调和级数的模版题，可以使用bfs建图和dp求解，但是注意需要提前退出以及对 $a_i$ 去重。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    vector<int> b;
    for (int& p : a) {
        if (p != 1) b.push_back(p);
    }
    ranges::sort(b);
    b.erase(unique(b.begin(), b.end()), b.end());
    vector<int> dp(n + 1, -1);
    queue<int> q;
    for (int& p : b) {
        q.push(p);
        dp[p] = 1;
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int& p : b) {
            ll tem = 1LL * x * p;
            if (tem > n) break;
            if (dp[tem] == -1) {
                dp[tem] = dp[x] + 1;
                q.push(tem);
            }
        }
    }
    if (*min_element(a.begin(), a.end()) == 1)
        cout << 1 << ' ';
    else
        cout << -1 << ' ';
    for (int i = 2; i <= n; i++) {
        cout << dp[i] << ' ';
    }
    cout << endl;
    return;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> dp(n + 1, INT_MAX / 2);
    for (int i = 0; i <= n - 1; i++) {
        cin >> a[i];
        dp[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            dp[j] = min(dp[j], dp[i] + dp[j / i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dp[i] == INT_MAX / 2) dp[i] = -1;
        cout << dp[i] << ' ';
    }
    cout << endl;
    return;
}

F Pizza Delivery

题目大意：需要从 $(ax,ay)$ 开始送披萨到 $n$ 个地点，然后回到 $(bx,by)$ ，每次可以向上、向下、向右走一步，问最少需要走多少步。

数据范围： $1 \leq n \leq 2 \cdot 10^5$ ， $ax < x_i < bx, 1 \leq y_i \leq 10^9$

思路：这道题是非常典的典题，只需考虑对于相同的横坐标，最终停在最上面还是最下面，并进行状态机DP即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


void solve() {
    int n, ax, ay, bx, by;
    cin >> n >> ax >> ay >> bx >> by;
    vector<pair<int, int>> ma(n);
    for (int i = 0; i <= n - 1; i++) cin >> ma[i].first;
    for (int i = 0; i <= n - 1; i++) cin >> ma[i].second;
    ranges::sort(ma);
    map<int, vector<int>> s;
    map<int, vector<ll>> s2;
    s[ax].push_back(ay);
    s2[ax].push_back(0);
    s[bx].push_back(by);
    s2[bx].push_back(LLONG_MAX);
    for (auto& [x, y] : ma) {
        s[x].push_back(y);
        s2[x].push_back(LLONG_MAX);
    }
    for (auto it = s.begin(); it != s.end(); it++) {
        auto itt = it;
        itt++;
        if (itt == s.end()) break;
        int tem = it->second.size();
        int tem2 = itt->second.size();
        int x = it->first;
        int x2 = itt->first;
        ll d = x2 - x;
        ll d2 = 1LL * abs(itt->second[tem2 - 1] - itt->second[0]);
        s2[x2][0] = min(s2[x2][0], s2[x][0] + d + 1LL * abs(it->second[0] - itt->second[tem2 - 1]) + d2);
        s2[x2][0] = min(s2[x2][0], s2[x][tem - 1] + d + 1LL * abs(it->second[tem - 1] - itt->second[tem2 - 1]) + d2);
        s2[x2][tem2 - 1] = min(s2[x2][tem2 - 1], s2[x][0] + d + 1LL * abs(it->second[0] - itt->second[0]) + d2);
        s2[x2][tem2 - 1] = min(s2[x2][tem2 - 1], s2[x][tem - 1] + d + 1LL * abs(it->second[tem - 1] - itt->second[0]) + d2);
    }
    cout << s2[bx][0] << endl;
    return;
}

G Paths in a Tree

题目大意：交互题，给定一棵 $n$ 个点的树的结构，图中有 $u,v$ 两个可能相同的隐藏节点，每次查询 $(x,y)$ 将会返回 $(x,y)$ 之间的路径与 $(u,v)$ 之间的路径是否相交（0或1），要求在 $\lfloor \frac{n}{2} \rfloor +1$ 次查询内找到 $(u,v)$ 路径上的至少一个顶点。

数据范围： $2 \leq n \leq 2 \cdot 10^5$

思路：这道题先介绍一个知识点：DFS序，即DFS的遍历顺序。

这个知识点是干啥的呢？首先，在一棵树上，设 $x$ 的DFS序为 $dfn[x]$ ，以 $x$ 为根节点的子树大小为 $siz[x]$ ，则 $[dfn[x],dfn[x]+siz[x]-1]$ 则为$x$ 的整棵子树范围，可以用于判断子树，并结合数据结构对整棵子树进行操作。

同时，如果 $x+1=y$ ，那么要么 $x$ 是 $y$ 的父节点，要么 $y$ 是 $x$ 回溯后遍历的下一个节点，这也是这题我们要用到的关键。

首先看这题的数据范围，一个 $\lfloor \frac{n}{2} \rfloor$ 非常明显地表示是要通过两两配对进行查询。

那么，怎么两两配对呢？赛时我想的是不断查询叶子，但是这样其实是错的。

正解则是对DFS序相邻的两个节点进行查询，如果这两个节点位于路径上，那么若它们是相邻的，则查其中一个节点即可，若它们不相邻，则这两个点路径上的其他节点必然已经被查询过了，因此还是只查询这两个节点就可以。最后，当 $n$ 为奇数时，由于之前的所有节点都被查过了，因此最后一个节点必然为答案。

所以，DFS序在思考树上问题时，还是非常重要的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


void solve() {
    int n, op;
    cin >> n;
    vector<vector<int>> ma(n);
    vector<int> dfn(n);
    vector<int> fdfn(n);
    vector<int> siz(n);
    int cnt = 0;
    int x, y;
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    auto dfs = [&](this auto&& dfs, int x, int pa) -> int {
        dfn[x] = cnt;
        fdfn[cnt] = x;
        cnt++;
        int tem = 1;
        for (int& p : ma[x]) {
            if (p == pa) continue;
            tem += dfs(p, x);
        }
        siz[x] = tem;
        return tem;
    };
    dfs(0, -1);
    for (int i = 0; i < n - 1; i += 2) {
        ask(fdfn[i] + 1, fdfn[i + 1] + 1);
        cin >> op;
        if (op == 1) {
            ask(fdfn[i] + 1, fdfn[i] + 1);
            cin >> op;
            if (op == 1)
                report(fdfn[i] + 1);
            else
                report(fdfn[i + 1] + 1);
            return;
        }
    }
    report(fdfn[n - 1] + 1);
    return;
}