本场摘要

D 题没有涉及到什么前置知识，蛮适合作为某些笔试中的压轴题的，如果对滑动窗口类型的 DP 的了解变得生疏的话，这道题目还是有一定难度的。

E，F，G 难度相差不大，不过要在两小时内全部通过还是比较困难，自己做的时候wa了若干次——还是再接再厉吧。

传送门：

题目

代码仓库

C.

题目大意：

输入三个数字 A，B，X。求如下式子：

Min⁡{∣(A⊕x)−(B⊕x)∣},0⩽x⩽X\operatorname{Min}\{|(A \oplus x)-(B \oplus x)|\}, 0 \leqslant x \leqslant X

题解：

不妨设A>BA>B, 且将 A 和 B 都用二进制表示。

由于 A 和 B 都要和 X 进行异或操作，如果某一个位上 A 和 B 都为 1 或者 0 ，那么将 x 的对应位置为 0 即可。这样一来，异或操作的作用，可以理解成将一个数字中某个位置上的 1，移动到另一个数字中的对应位置中去。

所以期望最小的方案就是，A 的最高的 1 不动，然后尽可能地通过异或 x 将 A 中低位的 1 移动到 B 中去。

如果需要移动 A 中的 最高位的 1，那说明 X 大到足以将 A 的低位 1 全移动到 B 中，而这已经是是理论最优解了。所以没必要移动 A 的最高位 1。

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 998244353;
const int maxn = 2e5 + 5;
const double eps = 1e-10;
ll a, b, x;
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> a >> b >> x;
        if (a < b) std::swap(a, b);
        int flag = 1;
        for (int i = 63; i >= 0; --i) {
            ll del = 1ll << i;
            if ((a & del) && !(b & del)) {
                if (flag) {
                    flag = 0;
                    continue;
                }
                if (x < del) continue;
                x -= del;
                a ^= del;
                b ^= del;
            }
        }
        std::cout << a - b << '\n';
    }

    return 0;
}

D.

小清新DP，想了一中午没想出来。。。看了题解豁然开朗，十分具有练习价值

（本题目的代码的文件名字为“starD.cpp”，值得特别关注的题目都会这样命名）

题目大意：

给定一个大小为 n 的整数序列，选择 m 个位置的数字（其中 m 由读者自定），序列将被分割成m+1m + 1个区间，对这 m 个位置的数字求和，又对m+1m + 1个区间分别求和（如果区间为空，则和为 0 ），求这m+2m + 2个和的最大值的最小可能值。

题解：

分析问题，首先从简单情况入手。如果不需要考虑「对 m 个位置的数字求和」，那么直接进行简单的二分然后贪心即可。

如果加上「对 m 个位置的数字求和」呢？由于我们需要求的是最小值，所以问题的单调性依然没有改变，我们依然可以通过二分去得到答案，只是我们二分时判断当前备选值可行性的函数（即代码中的check()）需要发生变化。

这样一来，问题转化为：给定一个值 x ， 是否存在一种划分区间的方法，使得「每个区间和」与「选取的数字的和」均小于 x 。可以注意到这个问题是“滑动窗口”问题的一个变体。定义dp[i]dp[i]为“第 i 个位置被选为间隔时，选取的数字的总和的最小值”。转移状态的时候，需要保证两个间隔所夹的区间和小于 x 。最后判断的时候，只要找到一个位置 i 满足dp[i]<xdp[i] < x即可。同时注意不要忘记最后一个被划分的区间的和也要小于 x 。

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 998244353;
const int maxn = 2e5 + 5;
const double eps = 1e-10;
int n, a[maxn];
ll dp[maxn];
bool check(ll limit) {
    std::set<pli> s;
    s.insert({0, 0});
    for (int i = 1; i <= n; ++i) dp[i] = 0;
    ll segmentLength = 0;
    int head = 0;
    for (int i = 1; i <= n; ++i) {
        // dp[i] = min{dp[j]} + a[i], 其中 j < i
        dp[i] = s.begin()->first + a[i];
        s.insert({dp[i], i});
        segmentLength += a[i];
        while (segmentLength > limit) {
            segmentLength -= a[head];
            if (head) 
                s.erase({dp[head - 1], head - 1});
            ++head;
        }
    }
    ll sum = 0;
    for (int i = n; i >= 1; --i) {
        if (dp[i] <= limit) return true;
        sum += a[i];
        if (sum > limit) return false;
    }
    return false;
}
ll dichotomy() {
    ll l = 0, r = 1e18, res = 1e18;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
            res = std::min(res, mid);
        } else {
            l = mid + 1;
        }
    }
    return res;
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> n;
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
        }
        std::cout << dichotomy() << '\n';
        
    }

    return 0;
}
/*
0 1 2 3 4 5 6 7
    ^   ^ 
# 1 4 5 3 3 2 #

dp[0] = 0
dp[1] = dp[0] + 1 = 1
segment += 1

limit = 3 

a[1] < limit ->  dp[2] can get from dp[0]
dp[2] = min{dp[1], dp[0]} + a[2] = 4

segment += 4 -> segment = 5 > limit 
dp[3] = dp[2] + a[3] = 9

*/

E.

题目大意：

交互题。给定一个大小为 n 的排列 A ，需要通过至多 40n40n 次询问来确定每个位置上的元素是什么，其中 n 满足 n<=2000n <= 2000。

题目中还有一个位置变量 x ，每次的询问的格式形如“? i”，其中 i 是一个小于 n 的整数。每次询问时，会将 A[i]A[i] 与 x 进行比较:

  • 如果满足 A[i]>xA[i] > x，则输出’>’，并进行 x:=x+1x := x + 1。
  • 如果满足 A[i]<xA[i] < x，则输出’<’，并进行 x:=x−1x := x - 1。
  • 如果满足 A[i]=xA[i] = x，则输出’=’.

题解：

注意 n 的取值范围，由于 log⁡22000=11\log _2 2000 = 11， 与 4040 为同一数量级，容易想到每个位置的数字是由二分确定的。二分在实践可以分为两种实现思路，一是选择一系列基准值，然后对每个位置上的数字进行二分查询；二是借用快速排序的思想，选定一个基准值后，将序列划分为大于基准值、小于基准值的两个子序列，然后递归下去，直至得到每个位置上的数字。

显然，第二种二分的思路操作上更加简洁可行。

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cassert>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int a[maxn], n;
int askWith(int pos) {
    std::cout << "? " << pos << std::endl;
    char ch[2];
    std::cin >> ch;
    if (ch[0] == '>')
        return 1;
    else if (ch[0] == '=')
        return 0;
    else
        return -1;
}
void output() {
    std::cout << "! ";
    for (int i = 1; i <= n; ++i)
        std::cout << a[i] << ' ';
    std::cout << std::endl;
}

int randomSelect(std::vector<int> vec) {
    return vec[rand() % vec.size()];
}
void setXEqualTo(int pos) {
    while (askWith(pos));
}
void solve(std::vector<int> vec, int min, int max) {
    if (min > max) return;
    int pos = randomSelect(vec);
    setXEqualTo(pos);
    std::vector<int> BiggerVec, SmallerVec;
    int cnt = 0;
    for (int it : vec) {
        if (it == pos)
            continue;
        if (askWith(it) == 1) {
            // 还原X的值
            askWith(pos);
            BiggerVec.push_back(it);
            ++cnt;
        } else {
            askWith(pos);
            SmallerVec.push_back(it);
        }
    }
    a[pos] = max - cnt;
    solve(SmallerVec, min, a[pos] - 1);
    solve(BiggerVec, a[pos] + 1, max);
}

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    srand(time(0));
    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> n;
        std::vector<int> vec;
        for (int i = 1; i <= n; ++i)
            vec.push_back(i);
        for (int i = 1; i <= n; ++i)
            a[i] = 0;
        solve(vec, 1, n);
        output();
    }

    return 0;
}
/*
2 4 1 5 3

x = 3

2 1 

x = 1
*/

F.

题目大意：

给定一颗大小为 n 的树，有一个物体从树的根开始移动，有两种移动方式：

  • 移动到一个树上的相邻节点，花费为 1
  • 从当前节点传送到根节点，无花费。但是这种操作仅能进行 k 次

问如果需要遍历树上的所有节点，所需的最小花费是多少。

题解：

通过简单的贪心可知，我们只有在到达根节点的时候才使用「传送」。除非使用传送，否则我们只有在遍历完一个子树的所有节点后才移动出该子树。

可以将产生花费的移动分为两类，即「遍历新节点」和「回溯」。每个节点都必须被遍历，所以第一类操作必然花费 n−1n - 1。

「回溯」指向着祖先节点的方向移动。为了「回溯」的花费更少，肯定要将「传送」的机会用在“刀刃”上，即在尽可能深的位置上「传送」才到根节点。依照这种思路，对于每个子树，我们将其最深的叶子的回溯路径作为这个离开这个子树时的路径，保证尽可能使得长的路更长，短的路更短，这样使用「传送」才是“最赚的”。

相比于出题人的标程的写法，感觉我代码要简单很多。

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int k, n;
std::vector<int> distanceDiff;
std::vector<int> edge[maxn];
int depth[maxn], deepestLeaf[maxn];
ll total;
void dfs(int u) {
    deepestLeaf[u] = depth[u];
    std::vector<int> vec;
    for (auto v : edge[u]) {
        depth[v] = depth[u] + 1;
        dfs(v);
        deepestLeaf[u] = std::max(deepestLeaf[u], deepestLeaf[v]);
        vec.push_back(deepestLeaf[v]);
    }
    sort(all(vec));
    // vec.size()是无符号的，如果vec为空，减1会溢出
    for (int i = 0 ; i < (int)vec.size() - 1; ++i) {
        total += vec[i] - depth[u];
        distanceDiff.push_back(std::max(0, vec[i] - depth[u] * 2));
    }
}
bool cmp(int x, int y) {
    return x > y;
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    // std::cin >> T; 
    while (T--) {
        std::cin >> n >> k;
        for (int i = 2; i <= n; ++i) {
            int j;
            std::cin >> j;
            edge[j].push_back(i);
        }
        dfs(1);
        sort(distanceDiff.begin(), distanceDiff.end(), cmp);
        for (int i = 0; i < std::min(k, (int)distanceDiff.size()); ++i)
            total -= distanceDiff[i];
        std::cout << total + n - 1 << '\n';
    }

    return 0;
}

G.

题目大意：

给定一个整数 n ，需要构造一个整数序列，这个序列满足：假设原序列为 a[1],a[2],...,a[n]{a[1], a[2], ..., a[n]}，新序列 a[2],a[1]+a[3],a[2]+a[4],...,a[i−1]+a[i+1],...,a[n−2]+a[n],a[n−1]{a[2], a[1] + a[3], a[2] + a[4], ..., a[i - 1] + a[i + 1], ..., a[n - 2] + a[n], a[n - 1]}，则新序列为原序列的一个排列。

要求每个元素均不能为 0 ，但是可以为负数。

题解：

遇到这种题目直接打表。先限定每个元素的范围为 [−5,5][-5, 5] ，找出 n 为 1…8 的所有可能序列，发现 −4,−3,3,−1,1,4{-4, -3, 3, -1, 1, 4} 多次在不同地方重复地部分或全部出现。研究发现这一段数字每依次增加两个都会使得新序列依然满足条件。据此，我们可以分奇偶考虑，找到不同情况下“基准序列”，然后再扩展之。

我们可以找到 n=2n = 2 和 n=7n = 7 中末尾两位以 [−4,−3],[3,−1],[1,4][-4, -3], [3, -1], [1, 4] 这三种数组组合结尾的序列，以此为基础。如果有更大的 n ，对 n 按照奇偶进行讨论，然后从这两种基础序列扩展出来即可。

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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int n;
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    // std::cin >> T;
    while (T--) {
        std::cin >> n;
        std::vector<int> vec{-4, -3, 3, -1, 1, 4};
        if (n % 2) {
            if (n <= 5) {
                std::cout <<"NO\n";
            } else {
                std::cout <<"YES\n";
                std::cout << "3 2 -1 1 2 ";
                n -= 5;
                for (int i = 1; i <= n/6; ++i) {
                    for (auto it : vec)
                        std::cout << it << ' ';
                }
                for (int i = 1; i <= n % 6; ++i)
                    std::cout << vec[i - 1] << ' ';
                std::cout << '\n';
            }
        } else {
            std::cout <<"YES\n";
            for (int i = 1; i <= n/6; ++i) {
                for (auto it : vec)
                    std::cout << it << ' ';
            }
            for (int i = 1; i <= n % 6; ++i)
                std::cout << vec[i - 1] << ' ';
            std::cout << '\n';
        }
    }

    return 0;
}