[WP] Codeforces Round 914 (Div. 2)

感觉这几天挺忙的，同时遇到了一点事情有点 emo，于是乎开了一场 cf，希望能通过 coding 舒缓一下痛苦。看了眼发现是 div.2 的，于是开了个小号。

1
2
3
4
5
6
Account: CharmingLakesideJewel
Official Rank: 21
Performance: 2522
Rating Change: 0 → 845

Passed Tasks: A B C D1 D2

A Forked!

题意还是比较明确的。首先定义了“马”的行动方式为向一个方向移动 $a$ 格并向另一个方向移动 $b$ 格。给定两个点 $(x_K,y_K),(x_Q,y_Q)$，询问马在哪些点可以一步吃掉 $(x_K,y_K)$ 或 $(x_Q,y_Q)$。

python 再一次体现出来了其魅力，用 set 去维护真的太优美啦，可以轻易地解决重复的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T = int(input())
for i in range(T):
    a, b = map(int, input().split())
    xK, yK = map(int, input().split())
    xQ, yQ = map(int, input().split())
    ans = 0
    positions = set([
        (xK + a, yK + b), (xK + a, yK - b), (xK - a, yK + b), (xK - a, yK - b),
        (xK + b, yK + a), (xK + b, yK - a), (xK - b, yK + a), (xK - b, yK - a)
    ])
    for pos in positions:
        dif1, dif2 = pos[0] - xQ, pos[1] - yQ
        if {abs(dif1), abs(dif2)} == {a, b}:
            ans += 1
    print(ans)

B Collecting Game

题意：对于一个数组中的所有元素，依次选择其作为起始能力值，可以无数次地吞掉元素值小于自己的数组元素（并将吞掉的元素累加到自身的能力值），问最多能吞掉多少个元素。

题意很明确，其实把数组排序一下之后就是一个纯粹的模拟。这是因为，以小的元素作为起始能吞掉的，以大的元素作为起始也必定能吞掉，因此可以直接从小到大模拟，后一步可以利用前一步的结果。

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
// only core code
const int N = 2e5 + 7;
int T, n, ans[N];
vector<pair<int, int> > a;

signed main() {
    kin >> T;
    while (T--) {
        kin >> n;
        a.clear();
        for (int i = 1; i <= n; ++i) a.push_back(make_pair(kin.get<int>(), i));
        sort(a.begin(), a.end());
        int64 sum = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            while ((cur < n && a[cur].first <= sum) || i >= cur) {
                sum += a[cur++].first;
            }
            ans[a[i].second] = cur - 1;
        }
        for (int i = 1; i <= n; ++i) kout << ans[i] << ' ';
        kout << '\n';
    }
    return 0;
}

C Array Game

题意：给定一个数组 $a$, 每次可以选择两个不同的元素（值可以相等），将其差的绝对值加入到数组末尾，问 $k(k\ge 1)$ 次操作后数组中最小的数最小可以是多少。$n\le 2\cdot 10^3$。

首先，易知 $k\ge 3$ 时解决方案是平凡的：直接先将 $|a_1-a_2|$ 加入两次，然后把加入的这两个数的差值（也就是 0）加入进去，最小值即为 0。

除此之外，$k=1$ 时，最小值也是易求的，只需要将所有数排序之后对所有的相邻两个数求差，最小值即为答案（同时要与原数组的最小值取 min）

比较难处理的是 $k=2$ 的情况。首先答案肯定不大于 $k=1$ 时的答案，因此在复用 $k=1$ 情况的代码之后我们只需要考虑加入的第二个数为数组最小值的情况。考虑我们要加入两个数，其实可以枚举加入的第一个数是几（通过枚举由哪两个元素作差）记为 $s$，然后去求此时的第二个数的最小值。事实上，如果我们已经知道了 $s$，并且对原数组排序过，那么可以容易地使用 lower_bound 求出 $s$ 附近的数的值，然后相减一下更新答案就可以了。时间复杂度 $O(n^2\log 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
// only core code
const int N = 2e3 + 7;
int T, n, k;
int64 a[N];

signed main() {
    kin >> T;
    while (T--) {
        kin >> n >> k;
        for (int i = 1; i <= n; ++i) kin >> a[i];
        sort(a + 1, a + n + 1);
        if (k >= 3) {
            kout << "0\n";
        } else if (k == 1) {
            int64 minimum = a[1];
            for (int i = 1; i < n; ++i) minimum = min(minimum, a[i + 1] - a[i]);
            kout << minimum << '\n';
        } else {
            // most difficult part
            int64 minimum = a[1];
            for (int i = 1; i < n; ++i) minimum = min(minimum, a[i + 1] - a[i]);
            for (int i = 1; i <= n; ++i) {
                for (int j = i + 1; j <= n; ++j) {
                    int64 current = a[j] - a[i];
                    int i = lower_bound(a + 1, a + n + 1, current) - a;
                    if (i <= n) minimum = min(minimum, a[i] - current);
                    if (i > 1) minimum = min(minimum, current - a[i - 1]);
                }
            }
            kout << minimum << '\n';
        }
    }
    return 0;
}

D Set To Max

分为 D1 (Easy Version) 和 D2 (Hard Version)

说实话感觉此题拆分的意义不大，想出做法之后时间复杂度的优化难度是较低的。

题意：给定一个长度为 $n$ 的数组 $a$，每次可以选择一个区间 $[l,r]$，将区间内的所有数变为 $\max\limits_{l\le x\le r}a_x$。问若干次操作后是否能将 $a$ 变为目标数组 $b$

考虑对于一个数 $ai$，如果要变成一个 $b_i$ 且 $b_i \not = a_i$，那么必定在附近存在一个 $a_s=b_i$。
对于 $a_s$ 如果其要将值“传递”给 $a_i$，那么必定有：$a_i\sim a_s$ 之间的所有数都小于等于 $b_i$，以及 $b_i\sim b_s$ 之间的所有数都大于等于 $b_i$。此时就可以认为 $a_i$ 可以变成 $b_i$。
考虑到 $i\sim s$ 的区间肯定是区间长度越小越容易满足，那么我们只需要找到 $a_i$ 左侧和右侧最近的 $a{lef}=a_{rig}=b_i$（找不到的情况跳过即可），然后去判断这两个条件是否成立。判断这两个条件是否满足使用 ST 表即可。

关于为什么满足了以上条件就一定有解：对于所有的 $a_i\not = b_i$，按照 $b_i$ 从小到大的顺序，依次将 $a_s$ 的值传递给 $a_i$。可以发现此过程没有让任何 $a_i$ 变得比 $b_i$ 大（破坏条件），且 $a_s$ 的值在传递时显然没有被改变过，且对于每一个 $a_i$，其都会被传递到一个 $b_i$。因此最终一定能将 $a$ 变为 $b$。

时间复杂度 $O(n\log 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
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
// only core code
const int N = 2e5 + 7;

namespace STmax {
    int st[N][20], lg[N];
    void init(int n, int *a) {
        for (int i = 1; i <= n; ++i) st[i][0] = a[i];
        for (int step = 1; (1 << step) <= n; ++step) {
            for (int i = 1; i + (1 << step) - 1 <= n; ++i) {
                st[i][step] = max(st[i][step - 1], st[i + (1 << (step - 1))][step - 1]);
            }
        }
        lg[1] = 0;
        for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    }
    int query(int l, int r) {
        int k = lg[r - l + 1];
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
}

namespace STmin {
    int st[N][20], lg[N];
    void init(int n, int *a) {
        for (int i = 1; i <= n; ++i) st[i][0] = a[i];
        for (int step = 1; (1 << step) <= n; ++step) {
            for (int i = 1; i + (1 << step) - 1 <= n; ++i) {
                st[i][step] = min(st[i][step - 1], st[i + (1 << (step - 1))][step - 1]);
            }
        }
        lg[1] = 0;
        for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    }
    int query(int l, int r) {
        int k = lg[r - l + 1];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
}

int T, n;
int a[N], b[N];
bool archievable[N];
int closet[N];

signed main() {
    kin >> T;
    while (T--) {
        kin >> n;
        for (int i = 1; i <= n; ++i) kin >> a[i];
        for (int i = 1; i <= n; ++i) kin >> b[i];
        STmax::init(n, a);
        STmin::init(n, b);
        for (int i = 1; i <= n; ++i) {
            archievable[i] = false;
            closet[i] = 0;
        }
        for (int i = 1; i <= n; ++i) {
            closet[a[i]] = i;
            if (closet[b[i]]) {
                if (STmax::query(closet[b[i]], i) <= b[i] && 
                    STmin::query(closet[b[i]], i) >= b[i]) {
                    archievable[i] = true;
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            closet[i] = 0;
        }
        for (int i = n; i >= 1; --i) {
            closet[a[i]] = i;
            if (closet[b[i]]) {
                if (STmax::query(i, closet[b[i]]) <= b[i] && 
                    STmin::query(i, closet[b[i]]) >= b[i]) {
                    archievable[i] = true;
                }
            }
        }
        bool flag = true;
        for (int i = 1; i <= n; ++i) {
            if (!archievable[i]) {
                flag = false;
                break;
            }
        }
        if (flag) kout << "YES\n";
        else kout << "NO\n";
    }
    return 0;
}

所以 D2 的难度只在 ST 表吗

后记

codeforces.profile: CharmingLakesideJewel

id释义为：迷人的湖畔珠宝（没错就是字面义，且很 Chinglish）

结果当然是一如既往的菜，不过靠着倒序开题还是狠狠吃了一波分，顺便拿了D的一血，确实爽。

跟我想象的完全一致，比赛开始后 40min 切完能切的就开始坐牢，眼睁睁看着 Official Rank 从 3 掉到了 21，还挺无力的哈哈哈哈。老年退役选手确实是顶多做不需要难的算法的思维题了，难的算法忘得一干二净。

已经退化成 fw 手速选手了。

高光时刻 D 0:11 first blood

关于代码模板：C++ 的代码都略去了代码模板，只保留了核心代码。代码模板即通常的快读快输，kin, kout 可以理解为 cin, cout 的快读快输版本