edu 场神秘分类讨论，神秘推式子。

2075A - To Zero

一次偶数那之后都是偶数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int J;
    cin >> J;

    while (J--) {
        int n, k;
        cin >> n >> k;

        int res = 0;
        if (n & 1) {
            n = max(0, n - k);
            res++;
        }  
        k--;
        res += (n + k - 1) / k;
        cout << res << endl;
    }

    return 0;
}

2075B - Array Recoloring（分类讨论）

Hint 1 矛盾点在，最左右两边的数很可能最后取。什么时候只能最后取？什么时候无限制？

$k$ 比较大的时候一定能选到 $k+1$ 个较大值，先选边上的较大值，向两边选完边上其它所有数后，最后选中间的。具体来说是 $k>1$。

只有 $k=1$ 时，先选某个在中间的数，然后向两边扩散。

分 $k>1$ 和 $k=1$ 两种情况讨论。

时间复杂度 $\operatorname{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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int J;
    cin >> J;

    while (J--) {
        int n, k;
        cin >> n >> k;

        vector<int> a(n); 
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        if (k == 1) {
            cout << max({
                a[0] + *max_element(a.begin() + 1, a.end()),
                a[n - 1] + *max_element(a.begin(), a.end() - 1)
            }) << endl;
        } else {
            k++;
            sort(a.begin(), a.end(), greater<>());
            cout << accumulate(a.begin(), a.begin() + k, 0ll) << endl;
        }
    }

    return 0;
}

2075C - Two Colors（双指针 / 二分）

经典双指针 / 二分

Hint 1 再仔细读题，必须选两种颜色。因此 $a_{i}=n$ 是假的。

$a{i}$ 取不到 $n$（否则只有一种颜色），先将 $a{i}$ 与 $n-1$ 取较小值。

Hint 2 对于确定的 $a{i},a{j}$，贡献多少答案？

$a{i}+a{j}-n+1$。当然这个数必须是正的才有贡献，也即 $a{i}+a{j} \geqslant n$。

Hint 3 对于确定的 $a{i}$，如何对所有满足 $j>i$ 的 $a{i},a_{j}$ 求答案？

升序排序后，先找到满足 $a{i}+a{p} \geqslant n$ 最小的 $p$。那么答案是 $\sum{j \geqslant p} (a{i}+a{j}-n+1)=\mathrm{num}\cdot(a{i}+n-1)+\sum{j \geqslant p} a{j}$。

上面 $\sum{j \geqslant p} a{j}$ 是后缀和，可以预处理求得。

时间复杂度 $\operatorname{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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int J;
    cin >> J;

    while (J--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(m); 
        ll res = 0;
        for (int i = 0; i < m; i++) {
            cin >> a[i];
            if (a[i] == n) {
                a[i]--;
            }
        }
        sort(a.begin(), a.end());
        vector<ll> suf(m + 1);
        for (int i = m - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] + a[i];
        }
        for (int i = 0; i < m; i++) {
            // a[i] + x >= n  ->  x >= n - a[i]
            auto it = lower_bound(a.begin() + i + 1, a.end(), n - a[i]);
            if (it != a.end()) {
                int num = a.end() - it;
                ll now = suf[it - a.begin()] + 1ll * num * (a[i] - n + 1);
                now *= 2;
                res += now;
            }
        }
        cout << res << endl;
    }

    return 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
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int J;
    cin >> J;

    while (J--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(m); 
        ll res = 0;
        for (int i = 0; i < m; i++) {
            cin >> a[i];
            if (a[i] == n) {
                a[i]--;
            }
        }
        sort(a.begin(), a.end());

        ll suf = 0;
        for (int l = 0, r = m; l < m; l++) {
            // a[l] + a[r] >= n
            if (r <= l) {
                suf -= a[r++];
            }
            while (r - 1 > l && a[l] + a[r - 1] >= n) {
                suf += a[--r];
            }
            ll now = suf + 1ll * (m - r) * (a[l] - n + 1);
            now *= 2;
            res += now;
        }
        cout << res << endl;
    }

    return 0;
}

2075D - Equalization（背包 DP）

Hint 1 从二进制考虑，每次操作相当于什么？

从二进制考虑，每次操作相当于砍掉一个长度为 $k$ 的后缀。要求砍之后，$x,y$ 相同，也就是说要保留 $x,y$ 的前缀（这里的前缀指去除前导零后的前缀，不要求按位对齐）。

下设 $x,y$ 不算公共前缀的长度分别为 $a,b$。

Hint 2 如果对 $x$ 总共除掉 $2^{i}$，对 $y$ 总共除掉 $2^{j}$，$i,j$ 应满足什么条件？

首先 $i = a,j =b$ 是可以的。也可以多除一点，$i=a+1,j=b+1$ 也行，再多也可以，可以写成 $i=a+\Delta,j=b+\Delta$。

如果 $i,j$ 超过了 $x,y$ 二进制的长度，那么就没有 $+\Delta$ 的限制了。

可以枚举满足上述条件的 $(i,j)$。至多枚举 $\operatorname{O}(\log^{2}V)$ 次。

Hint 3 最后一步，已经确定对 $x$ 总共除掉 $2^{i}$，对 $y$ 总共除掉 $2^{j}$，如何求最小代价？

不妨换个思路，直接求所有 $(i,j)$ 的答案 $dp_{i,j}$。

用类似背包的思路 DP，相当于是一个物品 $k$ 可以分给第一个背包也可以给第二个背包也可以不给，即更新 $dp{i+k,j}\leftarrow dp{i,j}$，以及 $dp{i,j+k}\leftarrow dp{i,j}$。（具体见代码）

预处理的时间复杂度 $\operatorname{O}(\log ^{3}V)$。

总时间复杂度 $\operatorname{O}(\log^{3}V+T\log^{2}V)$。

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
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull inf = 0x3f3f3f3f3f3f3f3f;

// 转二进制
string BIN(ull x) {
    string res;
    while (x) {
        res += (x & 1) + '0';
        x >>= 1;
    }
    return res;
}

template<typename T>
void chmin(T& x, const T& y) {
    if (x > y) x = y;
}

int main() {
    int J;
    cin >> J;

    vector dp(60, vector<ull>(60, inf));
    dp[0][0] = 0;
    for (int k = 0; k < 60; k++) {
        auto ndp = dp;
        for (int x = 0; x < 60; x++) {
            for (int y = 0; y < 60; y++) {
                if (x + k < 60) chmin(ndp[x + k][y], dp[x][y] + (1ull << k));
                if (y + k < 60) chmin(ndp[x][y + k], dp[x][y] + (1ull << k));
            }
        }
        dp = ndp;
    }

    while (J--) {
        ull X, Y;
        cin >> X >> Y;
        string x = BIN(X), y = BIN(Y);
        
        ull res = inf;
        for (int j = x.size(); j < 60; j++) {
            for (int k = y.size(); k < 60; k++) {
                chmin(res, dp[j][k]);
            }
        }
        while (!x.empty() && !y.empty() && x.back() == y.back()) {
            x.pop_back();
            y.pop_back();
        }
        for (int j = 0; x.size() + j < 60 && y.size() + j < 60; j++) {
            chmin(res, dp[x.size() + j][y.size() + j]);
        }
        cout << res << endl;
    }

    return 0;
}

Hint 1 $X{i,k}=X{j,k}$ 意味着什么？$a,b$ 分别可能有多少种取值？

$X{i,k}=X{j,k}\iff a{i}\oplus b{k}=a{j}\oplus b{k}\iff a{i}=a{j}$。也就是说，一旦两个元素相同，那么这两列的表头相同，这两列对应位置也就全部相同。（我赛时没想到）

若要求 $X$ 只有两种取值，那 本质不同的只有两行两列，也就是说 $a,b$ 分别最多有两种取值。

若有一者仅有一种取值，方案数很容易算，这里从略。下面只讨论 $a,b$ 都有两种取值的情形。不妨设前两行和前两列本质不同，并设 $a{1} < a{2},\ b{1} < b{2}$。

Hint 2 找到 $a{1},b{1},a{2},b{2}$ 的等价约束条件。

现在 $X{1,1} \neq X{1,2},X{1,1} \neq X{2,1}$，由要求只有两个不同的数，就必须 $X{1,2}=X{2,1}$，即 $a{1}\oplus b{1}\oplus a{2}\oplus b{2}=0$。另一方面，当 $a{1}\oplus b{1}\oplus a{2}\oplus b{2}=0$ 时，$X{1,2}=X{2,1},X{1,1}=X{2,2}$，满足只有两个不同的数的要求。

现在的问题是，求满足 $0 \leqslant a{1} < a{2} \leqslant A,\ 0 \leqslant b{1} < b{2} \leqslant B$，且 $a{1}\oplus a{2}= b{1}\oplus b{2}$ 的数量。

2075F - Beautiful Sequence Returns（单调栈 + 双指针 + 线段树 + 二分）

队友给的妙妙思路~

题意 称一个整数序列为美丽的，如果：

  • 每个元素左边有个元素比它小，且
  • 每个元素右边有个元素比它大。

给定一个数组，求最长美丽子序列长度。

Hint 1 如果确定子序列左右端点，最长美丽子序列长度是多少？

问题等价于左端点 $\ell$ 为唯一最小值，右端点 $r$ 为唯一最大值。那么如果确定子序列左右端点，只需计算区间 $\ell<i<r$ 中在 $a{l}<a{i}<a_{r}$ 范围内的下标 $i$ 数量 cnt，长度即为 cnt + 2。

Hint 2 需要枚举哪些左右端点？

只需选取 前缀最小值 为左端点， 后缀最大值 为右端点。因为如果 $\ell$ 左边还有比 $a_{\ell}$ 小的数，加上这个数一定更优，就不需要枚举这个 $\ell$ 了。

Hint 3 考虑双指针，枚举一个端点，动态求解另一个端点的最优答案。改变一者时，答案会有什么变化？

枚举右端点 $r$，「激活」合法（$\ell<i<r$ 且 $a{l}<a{i}<a_{r}$）的下标 $i$，把合法总数量记录在左端点 $\ell$ 上，也就是给每个左端点 $\ell$ 记录当前最长美丽子序列长度，如果多一个数合法就给每个 $\ell$ 都 +1，少一个合法就都 -1。

右端点从 $r$ 移动到 $r’<r$ 时，$r’<i<r$ 要全部取消激活。这里按下标枚举 $i$。

并且由于 $a{r’}>a{r}$，$1 \leqslant i<r’$ 中满足 $a{r} \leqslant a{i}<a_{r’}$ 的数要激活。这里按值枚举 $i$。

在整个过程中，每个数只会激活一次取消激活一次，复杂度已经达到线性。但问题在，把合法总数量记录在左端点 $\ell$ 上需要枚举很多 $\ell$，能否优化？

Hint 4 每次激活 $i$ 需要记录的左端点 $\ell$，有什么特点？如何快速找到？

每次激活 $i$ 需要记录的左端点 $\ell$ 其实是连续的区间 $[L,R)$。把合法总数量记录在左端点 $\ell$ 上，只需要做区间加。为求最优答案，只需要区间最大值。用线段树即可维护。

这个区间 $[L,R)$ 中的数 $j$ 满足 $a{j}<a{i}\land j<i$，也即 $L$ 对应于最小满足 $a{j}<a{i}$ 的 $j$，$R$ 对应于最小满足 $j \geqslant i$ 的 $j$。这两者都可以二分求得。

时间复杂度 $\operatorname{O}(n\log^{2}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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class Info, class Mark>
struct SegmentTree {
// 模板略
};
 
struct Mark {
    int add = 0;
    void apply(const Mark& o, int L, int R) & {  // 将标记 o 应用到当前节点[L,R)
        add += o.add;
    }
};

struct Info {
    int mx = 0;
    void apply(const Mark& o, int L, int R) & {   // 将标记 o 应用到当前节点[L,R)
        mx += o.add;
    }
    void apply(const Info& o) & {
        mx = max(mx, o.mx);
    }
    friend Info operator + (const Info& l, const Info& r) {
        return { max(l.mx, r.mx) };
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int J;
    cin >> J;

    while (J--) {
        int n;
        cin >> n;
        
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 离散化
        auto all = a;
        sort(all.begin(), all.end());
        all.erase(unique(all.begin(), all.end()), all.end());
        vector<vector<int>> adj(all.size());
        for (int i = 0; i < n; i++) {
            a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
            adj[a[i]].push_back(i);
        }

        // 特判长度为 1 的情况
        if (is_sorted(a.rbegin(), a.rend())) {
            cout << 1 << endl;
            continue;
        }

        vector<int> pre;  // 前缀最小值的下标
        for (int i = 0; i < n; i++) {
            if (pre.empty() || a[i] < a[pre.back()]) {
                pre.push_back(i);
            }
        }

        vector<int> suf;  // 后缀最大值的下标
        for (int i = n - 1; i >= 0; i--) {
            if (suf.empty() || a[i] > a[suf.back()]) {
                suf.push_back(i);
            }
        }
        
        int ans = 1;
        SegmentTree<Info, Mark> tree(0, n);
        auto add = [&](int i, int v) {
            /// 暴力的写法
            // for (int j = 0; j < pre.size(); j++) {
            //     if (a[pre[j]] < a[i] && pre[j] < i) {
            //         tree.apply(j, j + 1, Mark{ v });
            //     }
            // }
            /// 二分的写法
            // 在 pre 中找最小的 R 满足 pre[R]>=i
            int R = lower_bound(pre.begin(), pre.end(), i) - pre.begin();
            // 在 pre 中找最小的 L 满足 a[pre[L]]<a[i]
            int L = lower_bound(pre.begin(), pre.end(), a[i], 
                [&](int id, int val) {
                    return a[id] >= val; 
                }) - pre.begin();
            tree.apply(L, R, Mark{ v });
        };
        int lstr = n;
        a.push_back(0);  // a[n] = 0 防止越界
        for (auto r : suf) {
            for (int i = r + 1; i < lstr; i++) {  // r'<i<r 全部取消激活
                if (a[i] < a[lstr]) add(i, -1);
            }
            for (int v = a[lstr]; v < a[r]; v++) {  // i<r' 中满足 a_{r}<=a_{i}<a_{r'} 的数要激活
                for (auto i : adj[v]) {
                    if (i < r) add(i, 1);
                }
            }
            ans = max(ans, 2 + tree.query(0, n).mx);            
            lstr = r;
        }        
        cout << ans << endl;
    }

    return 0;
}