二次元修炼日记！

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

前言

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

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

好吧，也许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	B
2026.01.25	R1076	div3	2193	5	2619	1464	√	√	√	H	√	√	B
2026.01.29	R1077	div1/2	2188	4	1344	1723	√	√	√	√
2026.02.08	R1078	div2	2194	4	2090	1582	√	√	√	√	B
2026.02.11	R1079	div1/2	2197	4	1643	1650	√	√	√	√	B	B
2026.02.15	R1080	div.3	2195	6	401	2075	√	√	√	√	√	√	B
2026.02.21	R1081	div.2	2192	4	1281	1735	√	√	√	√	B

Codeforces Round #1072(Div.3)

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

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

C

题目大意：有一堆大小为 $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

题目大意：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

题目大意：如果一个数组至少有两个元素，且其中任意相邻元素至少相差 $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

题目大意：给一棵顶点编号为 $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

题目大意：给定编号为 $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

题目大意：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

题目大意：给定一个长度为 $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

题目大意：给定一个长度为 $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

题目大意：给定 $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

题目大意：在一条数轴上有 $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

题目大意：现在给定 $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

题目大意：给定 $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 Round #1075(Div.2)

掉大分，但是这场也挺edu的。

C1

题目大意：给定 $n$ ，求一个长度为 $n$ 的排列 $p$ ，使得对于每个 $i(2 \leq i \leq n-1)$ 都存在一个 $j(i \leq j \leq n),p_i=p_j \bigoplus i$ 。

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

思路：第一反应，猜测这个影响所有数的的数是 $1$ 或者 $n$ ，然后打表发现是行的，直接冲。

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


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    a[n - 1] = 1;
    map<int, int> ma;
    for (int i = 2; i <= n - 1; i++) ma[1 ^ i]++;
    int idx = 1;
    for (int i = 2; i <= n; i++) {
        if (!ma.count(i)) {
            idx = i;
            break;
        }
    }
    a[0] = idx;
    for (int i = 1; i < n - 1; i++) {
        a[i] = 1 ^ (i + 1);
    }
    for (int p : a) cout << p << ' ';
    cout << endl;
    return;
}

C2

题目大意：跟上题一样，但是 $1 \leq i \leq n-1$ ，如果不行就输出-1。

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

思路：赛时没有开出来，肯定跟上题有关系，但不知道是什么关系。

首先，打表发现 $n=2^x$ 的时候是不行的，为什么？

若 $n=2^x$ 位于 $0 \sim n-2$ 的位置，则必然存在它后面有一个数能成立，而由原来的公式是不可行的。

那么，当 $n$ 在 $n-1$ 的位置呢？此时考虑 $n-2$ 位置的数，必然是 $n \bigoplus (n-1) = p_{n-2}$ ，这显然也不对。

然后，再看可行的构造，由 $C1$ 题打表后发现可以交换 $a_1$ 跟 $a_{lowbit(n)}$ 位置的数，为什么？（一个启示：位运算题lowbit是很重要的）

由于有 $p_1 =n,p_{lowbit(n)}=p_k \bigoplus lowbit(n),$ 而 $p_{lowbit(n)}=lowbit(n) \bigoplus 1=lowbit(n)+1$ 因此往前交换后会发现， $p_1=lowbit(n)+1= lowbit(n) \bigoplus 1,p_{lowbit(n)}=n = (n \bigoplus lowbit(n)) \bigoplus lowbit(n)$ ，前者自然没啥问题，后者由于 $n-lowbit(n)=(n-lowbit(n)+1) \bigoplus 1$ ，因此也在它后面。

这时候会问，如果 $n$ 是奇数呢？奇数情况完全不需要交换，用C1构造的数列就能成立。

 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


void solve() {
    int n;
    cin >> n;
    int tem = popcount((unsigned)n);
    if (tem == 1) {
        cout << -1 << endl;
        return;
    }
    vector<int> a(n + 1);
    map<int, int> ma;
    a[n] = 1;
    ma[1]++;
    for (int i = 2; i <= n - 1; i++) {
        a[i] = (i ^ 1);
        ma[i ^ 1]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!ma.count(i)) {
            a[1] = i;
            break;
        }
    }
    swap(a[1], a[lowbit(n)]);
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    cout << endl;
    return;
}

D1

题目大意：给定一个字符串 $s$ ，在D1中它只是0-1字符串， $s[i]=0$ 代表在数组 $0 \sim n-1$ 的排列中不会出现子数组的MEX值为 $i$ ，反之则出现子数组的MEX值为 $i$ ，又给定一个数 $c$ ，求这样子数组不被 $c$ 整除的最小值，并模 $10^9+7$ ，若不存在则输出-1。

数据范围： $3 \leq n \leq 2 \cdot 10^5,1 \leq c \leq 10^9$

思路：组合数学题，而且这题的 $c$ 用处不大，因此原题中能构造的排列数是定值。

首先，如果字符串的首位和末位是0，那么肯定是不行的，因此输出-1。

随后考虑插空法，这是一个很常见的方法，也就是从MEX的角度考虑逐步拓展，从 $2 \sim n-1$ ，此时存在连续子数组能够表示 $0 \sim i-1$ 了，如果不能表示MEX为 $i$ 的话，就把 $i$ 插进这个子数组中，反之插到它的两侧。

于是，这样计数即可，需要注意的是 $c$ 可以每次直接除一下公因数，判断最后是否为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


const int MOD = 1e9 + 7;
void solve() {
    int n, c;
    cin >> n >> c;
    string s;
    cin >> s;
    if (s[0] == '0' || s[n - 1] == '0') {
        cout << -1 << endl;
        return;
    }
    ll res = 1;
    map<int, int> ma;
    for (int i = 1; i <= n - 1; i++) {
        if (s[i] == '1') {
            res = res * 2;
            res %= MOD;
            c /= __gcd(c, 2);
        } else {
            res = res * i;
            res %= MOD;
            c /= __gcd(c, i);
        }
    }
    cout << (c == 1 ? -1 : res) << endl;
    return;
}

D2

题目大意：跟上题一样，但是字符串中存在?，表示不知道取0还是取1。

数据范围：跟上题一样。

思路：其实很简单，首先先把所有不是?的对应元素乘出来（最后一格跟第一格由于有默认元素了，也能算），然后考虑对应?的元素，考虑贪心。

首先，如果用1是偶数的话，那么肯定不如取2，再考虑奇数，此时从高位倒着遍历到低位，如果此时剩下的 $c$ 没有奇数因子，那么肯定此时能给的2都给高位，如果有奇数因子，那么可以全部取 $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


constexpr int MOD = 1e9 + 7;
void solve() {
    int n, c;
    cin >> n >> c;
    string s;
    cin >> s;
    if (s[0] == '0' || s[n - 1] == '0') {
        cout << -1 << endl;
        return;
    }
    ll ans = 2;
    c /= __gcd(c, 2);
    vi res;
    rep(i, 1, n - 2) {
        if (s[i] == '0') {
            ans = ans * i % MOD;
            c /= __gcd(c, i);
        } else if (s[i] == '1') {
            ans = ans * 2 % MOD;
            c /= __gcd(c, 2);
        } else
            res.push_back(i);
    }
    frep(i, sz(res) - 1, 0) {
        if (res[i] % 2 == 0) {
            ans = ans * 2 % MOD;
            c /= __gcd(c, 2);
        }
    }
    frep(i, sz(res) - 1, 0) {
        if (res[i] == 1 || res[i] % 2 == 0) continue;
        if (c <= 2) {
            ans = ans * res[i] % MOD;
            c /= __gcd(c, res[i]);
        } else {
            ans = ans * 2 % MOD;
            c /= __gcd(c, 2);
        }
    }
    cout << ((c == 1) ? -1 : ans) << endl;
    return;
}

这里给出一道类题：CF1699C 。

Codeforces Round #1076(Div.3)

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

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

E

题目大意：黑板上写有 $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

题目大意：需要从 $(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

题目大意：交互题，给定一棵 $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;
}

Codeforces Round #1077(Div.2)

大豆和包子等等一车人出的场，总之题目是有点阴间的，特别是D2B。

还是上了点分，这没的说。

B

题目大意：有 $n$ 个座位，学生不能相邻坐，现在给定一个字符串 $s$ ，$s[i]=1$ 表示已经被占用了，问这一排不可能再有其他座位时，最少的学生总数。

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

思路：首先考虑一条空白的，那么配置形式肯定是 $01001001 \ldots$ 这样的，现在只需要处理边界就可以了，一种简单的方式是在两侧加上 $01$ ，这样可以避免讨论。

 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


void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int las = -1;
    int tem = 0;
    int ans = 0;
    for (int i = 0; i <= n - 1; i++) {
        if (s[i] == '1') {
            if (i == 0) {
                las = i;
                ans++;
                continue;
            }
            if (s[i - 1] == '0') {
                if (las == -1) {
                    if (tem == 1)
                        ans += 0;
                    else if (tem <= 3)
                        ans++;
                    else if ((tem - 1) % 3 == 0)
                        ans += (tem - 1) / 3;
                    else
                        ans += (tem - 1) / 3 + 1;
                } else {
                    if (tem <= 2)
                        ans += 0;
                    else if (tem <= 4)
                        ans++;
                    else if ((tem - 2) % 3 == 0)
                        ans += (tem - 2) / 3;
                    else
                        ans += (tem - 2) / 3 + 1;
                }
            }
            las = i;
            tem = 0;
            ans++;
        } else
            tem++;
    }
    if (las == -1) {
        if (tem <= 2)
            ans++;
        else if (tem % 3 == 0)
            ans += tem / 3;
        else
            ans += tem / 3 + 1;
    } else {
        if (tem <= 1)
            ans += 0;
        else if (tem <= 3)
            ans++;
        else if ((tem - 1) % 3 == 0)
            ans += (tem - 1) / 3;
        else
            ans += (tem - 1) / 3 + 1;
    }
    cout << ans << endl;
    return;
}

C

题目大意：给定一个数组 $a$ ，对于整数 $k$ ，当且仅当执行以下任意次数的操作，可以将 $a$ 排序后，才称它为小猪数组，操作为交换 $a_i,a_j,|a_i-a_j| \geq k$ ，请确定最大的小猪整数，若不存在则输出-1。

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

思路：考虑冒泡排序中，所有没有被正确排序的整数，都构成一个置换环，这个环内要求都能相互交换。

同时，在这个环之外，还能引入其他的整数进来形成新环，因此考虑引进最大的整数和最小的整数作为媒介（或者它们本来就在里面），进行交换，而最大的整数和最小的整数保持不动，于是得到答案。

本题更显然的做法是手玩。

 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


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    auto b = a;
    ranges::sort(b);
    bool flag = true;
    map<int, set<int>> ma;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] <= a[i + 1]) continue;
        flag = false;
        break;
    }
    if (flag) {
        cout << -1 << endl;
        return;
    }
    int maxx = *max_element(a.begin(), a.end());
    int mixx = *min_element(a.begin(), a.end());
    int ans = INT_MAX;
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] != b[i]) {
            int tem2 = max(maxx - a[i], a[i] - mixx);
            ans = min(ans, tem2);
        }
    }
    cout << ans << endl;
    return;
}

D

题目大意：给定整数 $x,y$ 要求求出 $p,q$ ，其中 $p&q=0,$ 且 $|x-p|+|y-q|$ 最小。

数据范围： $0 \leq x,y < 2^{30}$

思路：这道题的正解其实是贪心，也就是一个数跟原来的相等。

赛时的做法是，进行数位DP，既然 $p&q=0$ ，那么它们每个位的组成必然只有 $(0,0),(1,0),(0,1)$ 两种，同时可以观察到 $p$ 跟 $x$ ，$q$ 跟 $y$ 的关系只由高位决定，因此可以算出它们的差，并用记忆化搜索取最优，状态设计就设计为当前数大于/小于/等于 $x,y$ 。

至于还原路径，可以通过每次记录的最优状态，重新跑一遍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
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


void solve() {
    int x, y;
    cin >> x >> y;
    if ((x & y) == 0) {
        cout << x << ' ' << y << endl;
        return;
    }
    if (x == 1) {
        cout << 0 << ' ' << y << endl;
        return;
    }
    if (y == 1) {
        cout << x << ' ' << 0 << endl;
        return;
    }
    vector<array<array<int, 3>, 3>> vis(31);  // 0一样大，1比x大，2比x小
    vector<array<array<int, 3>, 3>> ma(31);
    vector<pair<int, int>> tem = {{0, 0}, {1, 0}, {0, 1}};
    for (int i = 0; i <= 30; i++) {
        for (int j = 0; j <= 2; j++) {
            for (int v = 0; v <= 2; v++) {
                vis[i][j][v] = false;
                ma[i][j][v] = INT_MAX;
            }
        }
    }
    vector<array<array<pair<int, int>, 3>, 3>> pa(31);
    auto dfs = [&](this auto&& dfs, int t, int tx, int ty) -> int {
        if (t < 0) return 0;
        if (vis[t][tx][ty]) return ma[t][tx][ty];
        ll res = LLONG_MAX;
        int mask = (1 << t);
        for (auto& [a, b] : tem) {
            int ttx = tx, tty = ty;
            int xt = (x >> t) & 1, yt = (y >> t) & 1;
            ll temp = 0;
            if (tx == 0) {
                if (xt < a) {
                    temp += 1LL * mask;
                    ttx = 2;
                } else if (xt > a) {
                    temp += 1LL * mask;
                    ttx = 1;
                } else
                    ttx = 0;
            } else if (tx == 1)
                temp += 1LL * (xt - a) * mask;
            else if (tx == 2)
                temp += 1LL * (a - xt) * mask;
            if (ty == 0) {
                if (yt < b) {
                    temp += 1LL * mask;
                    tty = 2;
                } else if (yt > b) {
                    temp += 1LL * mask;
                    tty = 1;
                } else
                    tty = 0;
            } else if (ty == 1)
                temp += 1LL * (yt - b) * mask;
            else if (ty == 2)
                temp += 1LL * (b - yt) * mask;
            temp += dfs(t - 1, ttx, tty);
            if (temp < res) {
                res = temp;
                pa[t][tx][ty] = {a, b};
            }
        }
        vis[t][tx][ty] = true;
        ma[t][tx][ty] = res;
        return res;
    };
    dfs(30, 0, 0);
    int fx = 0, fy = 0;
    int tx = 0, ty = 0;
    for (int i = 30; i >= 0; i--) {
        auto& [a, b] = pa[i][tx][ty];
        if (a) fx += (1 << i);
        if (b) fy += (1 << i);
        int xt = (x >> i) & 1, yt = (y >> i) & 1;
        if (tx == 0) {
            if (a > xt)
                tx = 2;
            else if (a < xt)
                tx = 1;
        }
        if (ty == 0) {
            if (b > yt)
                ty = 2;
            else if (b < yt)
                ty = 1;
        }
    }
    cout << fx << ' ' << fy << endl;
    return;
}

Codeforces Round #1078(Div.2)

最trivial的一集，都是比较简单的题目，但是代码编写很烦人。

B

题目大意：有 $n$ 家银行，每次转出只能转出 $x$ 元，同时转入到对方银行 $y$ 元，最后将所有钱汇聚到某家银行，它的最大值是多少？

数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq y \leq x \leq 10^9$ 。

思路：手玩样例可知，最后其他银行把钱全部转到某家银行即可，那么可流动资金是知道的，因此可以直接扣掉转入银行的流动资金，遍历 $O(n)$ 取最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    rep(i, 0, n - 1) ans += 1LL * (a[i] / x) * y;
    ll res = LLONG_MIN;
    rep(i, 0, n - 1) { res = max(res, a[i] + ans - 1LL * (a[i] / x) * y); }
    cout << res << endl;
    return;
}

C

题目大意：给定 $k$ 个纸条，每个长度为 $n$ ，要求构造一个新的字符串 $s$ ，且 $s_j \in {ma[i][j],0 \leq i \leq k-1,0 \leq j \leq n-1 }$ ，使得 $s$ 的最小正周期最小。

数据范围： $2 \leq n,k \leq 50000,4 \leq n \cdot k \leq 10^5$

思路：看到最小正周期，很trivial的一个思路就是枚举它的最小正周期，时间复杂度为 $O(\sqrt{n})$ 。

然后再跑一遍 $O(n)$ 的遍历，由于状态只有 $26$ ，因此可以考虑使用状压求集合交，类似一个分组循环的形式，时间复杂度为 $O(n \sqrt{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


void solve() {
    int n, k;
    cin >> n >> k;
    vector<string> ma(k);
    rep(i, 0, k - 1) cin >> ma[i];
    vi ma2(n);
    rep(i, 0, k - 1) { rep(j, 0, n - 1) ma2[j] |= (1 << (ma[i][j] - 'a')); }
    string ans = "";
    vector<int> d;
    auto init = [&](int x) -> void {
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                d.push_back(i);
                d.push_back(n / i);
            }
        }
        return;
    };
    init(n);
    ranges::sort(d);
    int m = sz(d);
    int res = 0;
    rep(i, 0, m - 1) {
        int val = d[i];
        bool flag = true;
        for (int j = 0; j <= val - 1; j++) {
            int tem = INT_MAX;
            for (int v = j; v <= n - 1; v += val) {
                tem &= ma2[v];
            }
            if (tem == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int j = 0; j <= val - 1; j++) {
                int tem = INT_MAX;
                for (int v = j; v <= n - 1; v += val) {
                    tem &= ma2[v];
                }
                rep(v, 0, 25) {
                    if ((tem >> v) & 1) {
                        ans += (char)('a' + v);
                        break;
                    }
                }
            }
            int res = n / d[i];
            string tem2 = ans;
            rep(i, 1, res - 1) ans += tem2;
            break;
        }
    }
    cout << ans << endl;
    return;
}

D

题目大意：在一个 $n \times m$ 的0-1网格上，请从左上到右下划一刀，刀口只能向右或者向下，请使得切割后两部分的1数量乘积最大，并输出刀口。

数据范围： $1 \leq n,m \leq 3 \cdot 10^5,2 \leq n \cdot m \leq 3 \cdot 10^5$ 。

思路：首先第一反应肯定是两部分都切到总数的 $\frac{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


void solve() {
    int n, m;
    cin >> n >> m;
    vvi ma(n, vi(m));
    int tot = 0;
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            cin >> ma[i][j];
            if (ma[i][j] == 1) tot++;
        }
    }
    cout << 1LL * (tot / 2) * (tot - tot / 2) << endl;
    vi dp(m);
    int tem = 0;
    int idx = 0;
    rep(j, 0, m - 1) {
        if (tem == tot / 2) {
            dp[j] = n;
            continue;
        }
        frep(i, n - 1, 0) {
            tem += ma[i][j];
            dp[j] = i;
            if (tem == tot / 2) break;
        }
    }
    string ans = "";
    rep(i, 0, m - 1) {
        if (i > 0) {
            rep(j, 1, dp[i] - dp[i - 1]) { ans += 'D'; }
        } else {
            rep(j, 1, dp[i]) { ans += 'D'; }
        }
        ans += 'R';
    }
    rep(i, 1, n - dp[m - 1]) { ans += 'D'; }
    cout << ans << endl;
    return;
}

E

题目大意：在一个 $n \times m$ 的网格上，Bob可以将某个格子的数取相反数，问Alice从左上角到右下角的路径，至少的路径总和是多少，其中Alice会在Bob操作后按照最优情况行动。

数据范围： $1 \leq n,m \leq 10^6,1 \leq n \cdot m \leq 10^6, -10^9 \leq a_{i,j} \leq 10^9$

思路：肯定是网格图DP，再往下看，不难发现Bob如果要反转一个格子，那么肯定是翻转最优路径上的格子。

于是出现两种情况，一种是直接按照原来路径踩着翻转的格子过去，一种是绕过去。

前者的计算不难，绕过去怎么计算？假设翻转的格子是 $(x,y)$ ，则绕过去的格子必然经过 $(a,b),$ 其中 $a>x,b<y$ 或者 $a<x,b>y$ ，然后就变为前后缀分解问题了，可以使用二维前缀最大值将查询复杂度降为 $O(1)$ ，总时间复杂度为 $O(n \cdot 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
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


void solve() {
    int n, m;
    cin >> n >> m;
    vvl ma(n, vl(m));
    rep(i, 0, n - 1) { rep(j, 0, m - 1) cin >> ma[i][j]; }
    vvl dp(n, vl(m, LLONG_MIN / 2));
    dp[0][0] = ma[0][0];
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (i == 0 && j == 0) continue;
            int ax = i - 1, ay = j;
            int bx = i, by = j - 1;
            if (ax >= 0 && ax <= n - 1 && ay >= 0 && ay <= m - 1) {
                dp[i][j] = max(dp[i][j], dp[ax][ay] + 1LL * ma[i][j]);
            }
            if (bx >= 0 && bx <= n - 1 && by >= 0 && by <= m - 1) {
                dp[i][j] = max(dp[i][j], dp[bx][by] + 1LL * ma[i][j]);
            }
        }
    }
    ll ans = dp[n - 1][m - 1];
    vvl fdp(n, vl(m, LLONG_MIN / 2));
    fdp[n - 1][m - 1] = ma[n - 1][m - 1];
    frep(i, n - 1, 0) {
        frep(j, m - 1, 0) {
            if (i == n - 1 && j == m - 1) continue;
            int ax = i + 1, ay = j;
            int bx = i, by = j + 1;
            if (ax >= 0 && ax <= n - 1 && ay >= 0 && ay <= m - 1) {
                fdp[i][j] = max(fdp[i][j], fdp[ax][ay] + ma[i][j]);
            }
            if (bx >= 0 && bx <= n - 1 && by >= 0 && by <= m - 1) {
                fdp[i][j] = max(fdp[i][j], fdp[bx][by] + ma[i][j]);
            }
        }
    }
    vvl pre1(n, vl(m, LLONG_MIN / 2));
    vvl pre2(n, vl(m, LLONG_MIN / 2));
    frep(i, n - 1, 0) {
        rep(j, 0, m - 1) {
            if (i != n - 1) pre1[i][j] = max(pre1[i][j], pre1[i + 1][j]);
            if (j != 0) pre1[i][j] = max(pre1[i][j], pre1[i][j - 1]);
            pre1[i][j] = max(pre1[i][j], dp[i][j] + fdp[i][j] - ma[i][j]);
        }
    }
    rep(i, 0, n - 1) {
        frep(j, m - 1, 0) {
            if (i != 0) pre2[i][j] = max(pre2[i][j], pre2[i - 1][j]);
            if (j != m - 1) pre2[i][j] = max(pre2[i][j], pre2[i][j + 1]);
            pre2[i][j] = max(pre2[i][j], dp[i][j] + fdp[i][j] - ma[i][j]);
        }
    }
    int x = n - 1, y = m - 1;
    vector<pii> path;
    path.emplace_back(x, y);
    while (!(x == 0 && y == 0)) {
        if (x == 0 && y != 0)
            y--;
        else if (x != 0 && y == 0)
            x--;
        else {
            if (dp[x - 1][y] > dp[x][y - 1])
                x--;
            else
                y--;
        }
        path.emplace_back(x, y);
    }
    rep(i, 0, sz(path) - 1) {
        auto& [x, y] = path[i];
        ll res = LLONG_MIN;
        res = max(res, dp[n - 1][m - 1] - 2 * ma[x][y]);
        if (x != n - 1 && y != 0) res = max(res, pre1[x + 1][y - 1]);
        if (x != 0 && y != m - 1) res = max(res, pre2[x - 1][y + 1]);
        ans = min(ans, res);
    }
    cout << ans << endl;
    return;
}

Codeforces Round #1079(Div.2)

最近的场好像风格奇怪了起来，感觉大部分都挺trivial的~

这个E1跟E2也不难，其实看着挺显然的，就是考验代码调试能力。

D刚好当天上午学了根号分治，晚上就考到了，我不好说，总之这把虽然很唐但是回蓝啦。

B

题目大意：给定一个长度为 $n$ 的排列 $p$ 和长度为 $n$ 的数组 $a$ ，可以对 $p$ 进行任意次以下操作： $p_i=p_{i+1}$ 或者 $p_{i+1}=p_i$ ，是否能把 $p$ 转变为 $a$ ？

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

思路：手玩样例，不难发现如果能转变需要两个条件，一是需要 $a$ 中每个数的出现都要连续，二是相对 $p$ 中原来元素的出现顺序， $a$ 中的出现不能交错，也就是 $a$ 去重后是 $p$ 的子序列。

 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


void solve() {
    int n;
    cin >> n;
    vi p(n);
    vi a(n);
    rep(i, 0, n - 1) cin >> p[i];
    rep(i, 0, n - 1) cin >> a[i];
    vector<pair<int, int>> pos(n + 1, {INT_MAX, INT_MIN});
    vi cnt(n + 1);
    map<int, int> ma;
    rep(i, 0, n - 1) {
        pos[a[i]].first = min(pos[a[i]].first, i);
        pos[a[i]].second = max(pos[a[i]].second, i);
        cnt[a[i]]++;
        ma[p[i]] = i;
    }
    rep(i, 1, n) {
        if (pos[i] == make_pair(INT_MAX, INT_MIN)) continue;
        if (pos[i].second - pos[i].first + 1 != cnt[i]) {
            cout << "No" << endl;
            return;
        }
    }
    int l = 0;
    int r = 0;
    auto a2 = a;
    a2.erase(unique(all(a2)), a2.end());
    int m = sz(a2);
    rep(i, 0, m - 1) {
        if (ma[a2[i]] < l) {
            cout << "No" << endl;
            return;
        }
        l = max(l, ma[a2[i]]);
    }
    cout << "Yes" << endl;
    return;
}

C

题目大意：Alice和Bob在玩游戏，一开始给定两个数 $p$ 和 $q$ ，每次当 $p>0$ 可以将 $p$ 减一，当 $q>1$ 可以将 $q$ 减一。当 $p=0$ 且 $q=1$ 时，游戏结束。如果在任意时候 $\frac{p}{q}=\frac{2}{3}$ ，则Bob获胜，反之Alice获胜，请求出胜者。

数据范围： $1 \leq p,q \leq 10^18$

思路：手玩样例，发现当 $p-2x=q-3x$ 时，Bob可以操纵获得胜利，反之Alice获得胜利。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void solve() {
    ll p, q;
    cin >> p >> q;
    ll tot = p * 3;
    ll tot2 = p + q - 1LL;
    ll x = q - p;
    if ((tot % 2 == 0 && tot / 2 == q)  || (x > 0 && 1LL * 3 * x < q && 1LL * 2 * x < p)) {
        cout << "Bob" << endl;
        return;
    }
    cout << "Alice" << endl;
    return;
}

D

题目大意：给定数组 $a$ ，请求出 $a_i \cdot a_j=j-i$ 的下标对 $(i,j)$ 数量。

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

思路：这道题，由于左边的乘法式子并没有什么好的性质，因此考虑如何降低复杂度。

我的第一思路是，通过式子进行放缩然后求解，发现会被 $1,n,\ldots,1\ldots,1$ 卡掉。

然后，就开始瞪，发现可以用调和级数来枚举，但是还是被 $1,\ldots,1$ 卡掉。

刚好早上刚学过根号分治，于是就往这方面想了，这也是启发一个思路，就是根号复杂度是一个很好的复杂度（这句话不能给伊人看到，毕竟我还是黑子）。

可以看出当 $a_i$ 较大的时候，使用调和级数枚举右维护左，一次操作的复杂度为 $O(\frac{n}{a_i})$ 。

然后，当 $a_i$ 较小的时候，完全可以直接枚举一遍，操作复杂度为 $O(n)$ 。

设分界点为 $B$ ，有总操作复杂度为 $O(nB+(n-B) \cdot \frac{n}{B})$ 显然当 $B=\sqrt{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


void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    int B = sqrt(n);
    rep(i, 1, B - 1) {
        rep(j, 0, n - 1) {
            ll tem = 1LL * j + 1LL * i * a[j];
            if (tem < 0 || tem >= n) continue;
            if (a[tem] == i) ans++;
        }
    }
    rep(i, 0, n - 1) {
        ll tem = a[i];
        if (a[i] < B) continue;
        while (tem <= i) {
            ll tem2 = 1LL * i - tem;
            if (tem2 < 0) break;
            if (a[tem2] == tem / (1LL * a[i])) ans++;
            tem += 1LL * a[i];
        }
    }
    cout << ans << endl;
    return;
}

E1

题目大意：交互题，给定一个有向无环图，有 $n$ 个顶点和 $m$ 条边（这里 $m$ 是未知数），每次通过查询 $x$ 来找出按字典序排序的所有路径中的第 $x$ 条路径，请在 $32 \cdot (n+m)$ 次查询内找出这个图中所有的边。

数据范围： $n \leq 15$ 。

思路：首先考虑有向无环图的性质，根据前置知识知道它可以被拓扑排序，且拓扑序就是按照DFS/BFS进行的排序，因此按照字典序排序，就是a/a->b/a->b->c/b这样排的。

看到32其实会很自然地想到二分，这里可以直接按照路径的前两个点（一条新边）进行二分查找。

 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


void solve() {
    int n;
    cin >> n;
    vector<pii> res;
    rep(i, 0, n - 1) {
        int las = -1;
        while (true) {
            int l = 1, r = (1 << 30), mid;
            int ans = r;
            while (l <= r) {
                mid = (l + r) / 2;
                vi tem = ask(mid);
                if (tem.empty())
                    r = mid - 1;
                else if (sz(tem) == 1 && tem[0] > i + 1)
                    r = mid - 1;
                else if (sz(tem) == 1 && tem[0] <= i + 1)
                    l = mid + 1;
                else if (sz(tem) >= 2) {
                    if (tem[0] < i + 1)
                        l = mid + 1;
                    else if (tem[0] > i + 1)
                        r = mid - 1;
                    else if (tem[0] == i + 1) {
                        if (tem[1] > las) {
                            r = mid - 1;
                            ans = mid;
                        } else
                            l = mid + 1;
                    }
                }
            }
            vi tem = ask(ans);
            if (sz(tem) <= 1) break;
            res.emplace_back(tem[0], tem[1]);
            las = tem[1];
        }
    }
    report(res);
    return;
}

E2

题目大意：跟上题一样，查询次数变为 $n+m$ 次，且 $n \leq 30$ 。

数据范围： $n \leq 30$ 。

思路：这里的查询次数变少了，因此肯定需要新的性质来做。

回想起，有向无环图可以在拓扑序上做DP，同时列举一下这里的字典序顺序可以发现，有很多需要跳过的部分，也就是遇到某个已经访问过点时需要跳过它的子树部分。

并且观察到，字典序相邻的两条路径，要么前者是后者的前缀（刚好增加一个顶点），要么删除一个顶点后缀，添加一个新的顶点后缀。

还没完，如果每次访问到一个已经访问的节点（指路径的最后一个顶点），直接跳过它的子树部分，那么每次访问，要么拓展一条新的边，要么跳到一个单顶点的路径，因此一共 $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
25
26
27
28
29


void solve() {
    int n;
    cin >> n;
    vector<pii> res;
    vector<bool> pd(n, false);
    vl dp(n, 1);
    vi tem;
    ll cnt = 1;
    rep(i, 0, n - 1) {
        cnt += 1LL * dp[i];
        pd[i] = true;
        while (true) {
            tem = ask(cnt);
            if (sz(tem) <= 1) {
                break;
            }
            rep(j, 0, sz(tem) - 2) dp[tem[j] - 1] += dp[tem.back() - 1];
            res.emplace_back(tem[sz(tem) - 2], tem[sz(tem) - 1]);
            if (pd[tem.back() - 1]) {
                cnt += dp[tem.back() - 1];
                continue;
            }
            pd[tem.back() - 1] = true;
            cnt++;
        }
    }
    report(res);
    return;
}

Codeforces Round #1080(Div.3)

这次除了H构造，确实都很trivial啊，G的思路不难但是写得少~

为什么AB会WA呢，还是不够稳。

D

题目大意：现在有隐藏序列 $a_1,a_2,\ldots,a_n$ ，保证 $|a_i| \leq 1000$ ，现在给定 $p_1,p_2,\ldots,p_n,p_i=\sum\limits_{i=1}^{n}a_i \cdot |i-x|$ ，要求还原原来的 $a_i$ 。

数据范围： $2 \leq n \leq 3 \cdot 10^5, -10^{14} \leq p_i \leq 10^{14}$

思路：把式子写出来，然后拆项加和差分啥的，简单的数学直觉，有群友跑去高斯消元还做不出来，我不好评价。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


void solve() {
    int n;
    cin >> n;
    vl f(n);
    vl a(n);
    rep(i, 0, n - 1) cin >> f[i];
    ll tot = (f[0] + f[n - 1]) / (n - 1);
    ll tem = 0;
    rep(i, 0, n - 2) {
        a[i] = (tot - (f[i] - f[i + 1] + 2LL * tem)) / 2;
        tem += a[i];
    }
    a[n - 1] = tot;
    rep(i, 0, n - 2) a[n - 1] -= a[i];
    rep(i, 0, n - 1) cout << a[i] << ' ';
    cout << endl;
    return;
}

E

题目大意：有 $n+1$ 个顶点的二叉树，每个顶点上最多可以写一个字母，所有顶点上最初啥都不写，根为0，0直接跟1连着，除0外不存在只有一个子节点的节点，现在Bob发明了白痴优先搜索，规则如下，经验证可以让他最终走到0，请给出每个节点走到0的步数，并模 $10^9+7$ 。

规则：如果当前节点是叶子，那么移动到父节点，否则，若顶点为空，则写入 $L$ ，并移动到左顶点，若为 $L$ ，则覆盖为 $R$ ，并移动到右顶点，若为 $R$ 则删掉并移动到父节点。

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

思路：手玩一下样例，发现由于走到父节点后父节点还会再下来走一次，而且题目的形式非常像换根，因此考虑自上而下换根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


const int MOD = 1e9 + 7;
void solve() {
    int n;
    cin >> n;
    vector<pii> ma(n + 1);
    rep(i, 1, n) cin >> ma[i].first >> ma[i].second;
    vector<pll> siz(n + 1);
    vl res(n + 1);
    auto dfs = [&](this auto&& dfs, int x) -> int {
        if (ma[x].first != 0) siz[x].first = dfs(ma[x].first);
        if (ma[x].second != 0) siz[x].second = dfs(ma[x].second);
        return siz[x].first + siz[x].second + 1;
    };
    dfs(1);
    res[1] = (2LL * siz[1].first + 2LL * siz[1].second + 1) % MOD;
    auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
        if (x != 1) {
            res[x] = (res[pa] + 2LL * siz[x].first + 2LL * siz[x].second + 1) % MOD;
        }
        if (ma[x].first) dfs2(ma[x].first, x);
        if (ma[x].second) dfs2(ma[x].second, x);
        return;
    };
    dfs2(1, -1);
    rep(i, 1, n) cout << res[i] << ' ';
    cout << endl;
    return;
}

F

题目大意：给定 $n$ 个二次函数，其中 $f_i=a_i x^2+b_i x + c_i$ ，如果两个函数没有交点，那么称他们为独立函数，如果某个集合中函数两两独立，那么称为独立集，请求出最大独立集大小。

数据范围： $1 \leq n \leq 3000, -10^6 \leq a_i,b_i,c_i \leq 10^6$

思路：考虑不交的函数有什么性质，判别式不为0？（或者注意二次项系数一样时的情况），由零点存在性原理，是恒大于或者恒小于，那么这里就存在偏序关系了，包含某个点的最大集合，就是拓扑排序中最长链的长度（因为显然地，这里存在一个有向无环图），按照拓扑序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
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


void solve() {
    int n, a, b, c;
    cin >> n;
    vector<tuple<ll, ll, ll>> ma(n);
    rep(i, 0, n - 1) {
        cin >> a >> b >> c;
        ma[i] = make_tuple(a, b, c);
    }
    vi res(n);
    vvi ma2(n);
    vvi ma3(n);
    vi deg(n);
    vi deg2(n);
    rep(i, 0, n - 1) {
        rep(j, i + 1, n - 1) {
            ll a1 = get<0>(ma[i]), a2 = get<0>(ma[j]);
            ll b1 = get<1>(ma[i]), b2 = get<1>(ma[j]);
            ll c1 = get<2>(ma[i]), c2 = get<2>(ma[j]);
            if (a1 != a2 && (b1 - b2) * (b1 - b2) - 4 * (a1 - a2) * (c1 - c2) < 0) {
                if (a1 > a2) {
                    ma2[i].push_back(j);
                    ma3[j].push_back(i);
                    deg[j]++;
                    deg2[i]++;
                } else {
                    ma2[j].push_back(i);
                    ma3[i].push_back(j);
                    deg[i]++;
                    deg2[j]++;
                }

            } else if (a1 == a2 && b1 == b2 && c1 != c2) {
                if (c1 > c2) {
                    ma2[i].push_back(j);
                    ma3[j].push_back(i);
                    deg[j]++;
                    deg2[i]++;
                } else {
                    ma2[j].push_back(i);
                    ma3[i].push_back(j);
                    deg[i]++;
                    deg2[j]++;
                }
            }
        }
    }
    vi dp(n);
    vi fdp(n);
    auto bfs = [&](this auto&& bfs, vvi& ma, vi& deg, vi& dp) -> void {
        queue<int> q;
        rep(i, 0, n - 1) {
            if (deg[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            for (int& p : ma[node]) {
                dp[p] = max(dp[p], dp[node] + 1);
                if (--deg[p] == 0) {
                    q.push(p);
                }
            }
        }
    };
    bfs(ma2, deg, dp);
    bfs(ma3, deg2, fdp);
    rep(i, 0, n - 1) cout << dp[i] + fdp[i] + 1 << ' ';
    cout << endl;
}

G

题目大意：跟E题一样，但是此时给出 $q$ 个询问，每个询问需要回答最开始位置为 $x$ ，走了 $k$ 步后的位置。

数据范围： $1 \leq n \leq 3 \cdot 10^5+1, 1 \leq q \leq 4 \cdot 10^5, 1 \leq v_j \leq n, 0 \leq k_j \leq \mathrm{min}(10^9+7,T_{v_j})$

思路：既然是数数题，那么很显然地，需要使用树上倍增，赛时能一眼看破这个，但是不大会写，补的时候参照了一下前排大佬的代码。

同时，注意到这里遍历的顺序比较奇怪，也就是说刚好是欧拉序（欧拉序：每次到一个节点就记录它，子树走完再回来），如果跳到某个祖先还有剩下的步数，那么使用欧拉序求解。

最后，需要使用数数来计数向上跳的步数，这里注意到应该自下而上先统计一个节点走到它的父节点所需步数，再在倍增的时候直接跳，需要注意的是， $up$ 和 $st$ 两个数组的含义不同，写的时候需要辨别。

 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


const int MOD = 1e9 + 7;
const ll INF = (1LL << 50);
void solve() {
    int n, q, v, k;
    cin >> n >> q;
    vector<pii> ma(n + 1);
    vi pa(n + 1);
    vl dp(n + 1);
    vvi up(n + 1, vi(20));
    vvl st(n + 1, vl(20, INF));
    pa[1] = 0;
    rep(i, 1, n) {
        cin >> ma[i].first >> ma[i].second;
        if (ma[i].first != 0) pa[ma[i].first] = i;
        if (ma[i].second != 0) pa[ma[i].second] = i;
    }
    vi path;
    vector<pll> siz(n + 1);
    vi pos(n + 1);
    auto dfs = [&](this auto&& dfs, int x) -> int {
        pos[x] = sz(path);
        path.push_back(x);
        if (ma[x].first != 0) {
            siz[x].first = dfs(ma[x].first);
            dp[x] += dp[ma[x].first] + 1;
            path.push_back(x);
            siz[x].second = dfs(ma[x].second);
            dp[x] += dp[ma[x].second] + 1;
            path.push_back(x);
        }
        dp[x]++;
        return siz[x].first + siz[x].second + 1;
    };
    dfs(1);
    path.push_back(0);
    rep(i, 0, n) up[i][0] = pa[i], st[i][0] = dp[i];
    rep(j, 0, 18) {
        rep(i, 1, n) {
            int mid = up[i][j];
            if (mid) {
                up[i][j + 1] = up[mid][j];
                if (st[i][j] != INF && st[mid][j] != INF) st[i][j + 1] = st[mid][j] + st[i][j];
            }
        }
    }
    rep(i, 0, q - 1) {
        cin >> v >> k;
        frep(j, 19, 0) {
            if (up[v][j] && st[v][j] <= k) {
                k -= st[v][j];
                v = up[v][j];
            }
        }
        cout << path[pos[v] + k] << ' ';
    }
    cout << endl;
    return;
}

Codeforces Round #1081(Div.2)

很trivial的场~

C

题目大意：给定一个数组 $a$ ，每个 $a_i$ 会造成 $a_i$ 点伤害，敌人的生命值从 $h$ 开始，当生命值小于等于0时，敌人就会死亡。

这把枪每秒发射一颗子弹，发射完所有子弹后，必须重新装弹，重新装弹需要 $k$ 秒，接着按照顺序发射。

战斗开始前，最多可以交换一次 $a_i$ 和 $a_j$ ，请给出杀死敌人的最少秒数。

数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq h,k \leq 10^9, 1 \leq a_i \leq 10^9$

思路：首先对于整发弹夹，是没有影响的。

因此贪心的思路就是，怎么弄来让整个弹夹的前缀和最大。

一个贪心的想法是，把当前的元素和前缀最小值互换，以达到最大的效果。

 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, h, k;
    cin >> n >> h >> k;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll tot = 0;
    rep(i, 0, n - 1) tot += 1LL * a[i];
    int cnt = h / tot, r = h % tot;
    ll res;
    if (r == 0)
        res = 1LL * (cnt - 1) * k + 1LL * n * cnt;
    else
        res = 1LL * cnt * k + 1LL * n * cnt;
    if (r == 0) {
        cout << res << endl;
        return;
    }
    vi suf(n);
    suf[n - 1] = a[n - 1];
    frep(i, n - 2, 0) { suf[i] = max(suf[i + 1], a[i]); }
    ll tem = 0;
    ll mixx = LLONG_MAX;
    rep(i, 0, n - 1) {
        mixx = min(mixx, 1LL * a[i]);
        tem += 1LL * a[i];
        if (tem >= r) {
            cout << res + 1LL * i + 1LL << endl;
            return;
        }
        if (i < n - 1 && tem + 1LL * suf[i + 1] - mixx >= r) {
            cout << res + 1LL * i + 1LL << endl;
            return;
        }
    }
    return;
}

D

题目大意：给定一棵有根 $r$ 的树 $T$ ，每个节点都有一个值 $a_i$ ，这棵树的成本定义为 $\sum_{u \in T}(a_u \cdot d(r,u))$ 。

这里的总和是树 $T$ 所有节点 $u$ 的总和， $d(r,u)$ 表示节点 $r$ 到节点 $u$ 的最短路径的边数。

现在给你一棵由 $n$ 个节点组成的树，根节点为 $1$ 。每个节点都有一个值 $a_i$ ，对于从 $1$ 到 $n$ 的每个 $r$ ，请求出以顶点 $r$ 为根的子树中，执行最多一次操作后能得到的最大成本。

操作：选择任意节点 $u(u \not ={r})$ ，删除从 $u$ 到其父节点的边，然后添加一条从 $u$ 到任何仍可从 $r$ 到达的节点 $v$ 的边。

数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 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
47
48
49
50
51
52
53


void solve() {
    int n, x, y;
    cin >> n;
    vl a(n);
    vvi ma(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl res(n);
    rep(i, 1, n - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    vi dep(n);
    vi maxx(n);
    vl tem(n);
    vl tem2(n);
    vl tem3(n);
    vl cnt(n);
    auto dfs = [&](this auto&& dfs, int x, int pa, int d) -> void {
        dep[x] = d;
        maxx[x] = dep[x];
        tem2[x] = a[x];
        int idx = -1;
        ll d1 = d, d2 = d;
        for (int& p : ma[x]) {
            if (p == pa) continue;
            dfs(p, x, d + 1);
            tem2[x] += tem2[p];
            tem3[x] += tem3[p] + tem2[p];
            if (maxx[p] > d1) {
                d2 = d1;
                d1 = maxx[p];
                idx = p;
            } else if (maxx[p] > d2)
                d2 = maxx[p];
        }
        if (idx != -1) {
            cnt[x] = max(cnt[x], cnt[idx]);
            cnt[x] = max(cnt[x], tem2[idx] * (d2 - dep[idx] + 1));
        }
        for (int& p : ma[x]) {
            if (p == pa || p == idx) continue;
            cnt[x] = max(cnt[x], tem2[p] * (d1 - dep[p] + 1));
        }
        res[x] = tem3[x] + cnt[x];
        maxx[x] = d1;
        return;
    };
    dfs(0, -1, 0);
    rep(i, 0, n - 1) cout << res[i] << ' ';
    cout << endl;
    return;
}

E

题目大意：给定两个数组 $a$ 和 $b$ ，长度都是 $n$ ，可以进行任意次次数的以下操作：选择索引 $i$ ，将 $a_i$ 和 $b_i$ 互换，问是否能将 $a$ 转化为 $b$ 的重排。

数据范围： $1 \leq a \leq 10^6, 1 \leq a_i,b_i \leq n$

思路：这道题，其实是一个knowledge check，它的主要知识点是欧拉路径。

首先考虑，将每个数抽象为一个点， $a_i \rightarrow b_i$ 为从 $a_i$ 指向 $b_i,$ 编号为 $i$ 的一条有向边，从而可以观察到，每个节点的入度都应该等于出度，这就形成了欧拉回路。

随后，为了跑可以反转边的欧拉回路，我们完全可以采用一种方式，也就是存无向边，在无向基图中跑出一个欧拉回路，然后按照遍历的顺序进行定向，如果从 $x$ 到 $to$ 的一条边， $x$ 在 $a$ 中，那么就不需要反向，反之需要反向。

最后，由于这个值域比较大，因此考虑离散化，总的时间复杂度为 $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


void solve() {
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    vi sorted;
    rep(i, 0, n - 1) cin >> a[i], sorted.push_back(a[i]);
    rep(i, 0, n - 1) cin >> b[i], sorted.push_back(b[i]);
    ranges::sort(sorted);
    sorted.erase(unique(all(sorted)), sorted.end());
    int cnt = sz(sorted);
    vi tot(cnt);
    vi cnta(n), cntb(n);
    vi res;
    vector<vector<pii>> ma3(cnt);
    rep(i, 0, n - 1) {
        cnta[i] = ranges::lower_bound(sorted, a[i]) - sorted.begin();
        cntb[i] = ranges::lower_bound(sorted, b[i]) - sorted.begin();
        tot[cnta[i]]++, tot[cntb[i]]++;
        ma3[cnta[i]].emplace_back(cntb[i], i);
        ma3[cntb[i]].emplace_back(cnta[i], i);
    }
    rep(i, 0, cnt - 1) {
        if (tot[i] % 2) {
            cout << -1 << endl;
            return;
        }
    }
    vector<bool> vis(n, false);
    vi head(cnt);
    auto dfs = [&](this auto&& dfs, int x) -> void {
        for (int& i = head[x]; i < sz(ma3[x]);) {
            auto [to, id] = ma3[x][i++];
            if (vis[id]) continue;
            vis[id] = true;
            if (cnta[id] != x) res.push_back(id);
            dfs(to);
        }
    };
    rep(i, 0, cnt - 1) { dfs(i); }
    cout << sz(res) << endl;
    rep(i, 0, sz(res) - 1) cout << res[i] + 1 << ' ';
    cout << endl;
    return;
}

E类题

出处：CF2110E

题目描述：给定 $n$ 种不同的声音，每种声音的特点是音量和音高，一连串的声音被称为音乐，如果任何两个连续的声音仅在音量和音高上有所不同，那么音乐被认为是优美的，如果连着三个连续声音的音量或者音高都相同，那么音乐被认为是乏味的。

现在，给定 $n$ 种不同的声音，是否能构成优美而不乏味的声音？

数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq u_i,p_i \leq 10^9$ 。

思路：跟上题其实差不多，首先观察到相邻的两个点必然是只有声音或者音高相同，因此这里可以看出是一个二分图，并且两边的声音跟音高要分开看，将一个声音视为连接 $u_i$ 跟 $v_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
62
63
64
65
66


void solve() {
    int n;
    cin >> n;
    vector<pii> ma(n);
    rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
    vi sorteda;
    vi sortedb;
    rep(i, 0, n - 1) {
        sorteda.push_back(ma[i].first);
        sortedb.push_back(ma[i].second);
    }
    ranges::sort(sorteda);
    sorteda.erase(unique(all(sorteda)), sorteda.end());
    ranges::sort(sortedb);
    sortedb.erase(unique(all(sortedb)), sortedb.end());
    int m = sz(sorteda) + sz(sortedb);
    vi cnta(n);
    vi cntb(n);
    vi tot(m);
    vector<vector<pii>> ma2(m);
    rep(i, 0, n - 1) {
        cnta[i] = ranges::lower_bound(sorteda, ma[i].first) - sorteda.begin();
        cntb[i] = ranges::lower_bound(sortedb, ma[i].second) - sortedb.begin() + sz(sorteda);
        ma2[cnta[i]].emplace_back(cntb[i], i);
        ma2[cntb[i]].emplace_back(cnta[i], i);
        tot[cnta[i]]++, tot[cntb[i]]++;
    }
    int st = 0, cnt = 0;
    frep(i, m - 1, 0) {
        if (!ma2[i].empty()) {
            if (sz(ma2[i]) % 2) {
                st = i;
                cnt++;
            } else if (cnt == 0) {
                st = i;
            }
        }
    }
    if (cnt > 2) {
        cout << "NO" << endl;
        return;
    }
    vi head(m);
    vi res;
    vector<bool> vis(n, false);
    auto dfs = [&](this auto&& dfs, int x) -> void {
        for (int& i = head[x]; i < sz(ma2[x]);) {
            auto [to, id] = ma2[x][i++];
            if (vis[id]) continue;
            vis[id] = true;
            dfs(to);
            res.push_back(id);
        }
        return;
    };
    dfs(st);
    if (sz(res) != n) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    ranges::reverse(res);
    rep(i, 0, sz(res) - 1) cout << res[i] + 1 << ' ';
    cout << endl;
    return;
}

Educational Codeforces Round #187

这场也没打，但是C比较恶心，VP的时候没开出来，D很简单，E是火箭毛毛虫，需要一些ds功底，整体确实很Edu。

C

题目大意：给定一个 $m$ ，问是否能构造 $a_1,\ldots,a_n$ ，且每个 $a_i$ 都是 $m$ 子集，且 $\sum\limits_{i=1}^{n}a_i=s$ ，若能则求 $n$ 的最小值。

数据范围： $1 \leq s,m \leq 10^18$

思路：这个数据范围显然一眼二分，而且答案确实有单调性。

但是问题是，check函数怎么写？

很自然的思路是从高位向低位贪心，然后每次最多减掉 $mid$ 个当前位，证明思路是如果当前位少减了，那么后面的位需要堆更多才能做到，因此是不划算的。

 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


void solve() {
    ll s, m;
    cin >> s >> m;
    ll ans = -1;
    ll l = 1, r = s, mid;
    auto check = [&](this auto&& check, ll mid) -> bool {
        ll tem = s;
        frep(i, 60, 0) {
            if ((m >> i) & 1) {
                tem -= 1LL * (min(tem >> i, mid) << i);
            }
        }
        return tem == 0;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return;
}

D

题目大意：Alice和Bob正在玩一个游戏，给定一个 $n$ 个元素组成的数组 $a$ 和 $m$ 个元素组成的数组 $b$ 。

他们轮流进行游戏，Alice先下，轮到自己时，需要从 $a$ 中选择一个数字 $x$ ，从 $b$ 中选择一个数字 $y$ ，他们选择的规则不一样。

Alice选择 $x,y,x \mid y$ ，Bob选择 $x,y, x \nmid y$ ，随后删除 $y$ ，不删除 $x$ ，若谁无法下棋了，就输掉。

请判断，最后谁会赢？

数据范围： $1 \leq n,m \leq 10^6, 1 \leq a_i,b_i \leq n+m, 1 \leq sum(n) \leq 10^6,1 \leq sum(m) \leq 10^6$

思路：显然可以将 $b$ 中的数分为两部分，一部分是可以被所有 $a$ 整除的，一部分是可以被一部分 $a$ 整除的，一部分是完全无法被 $a$ 整除的，显然双方都在争抢中间那部分。

接着，就可以对 $a$ 去重，并且使用调和级数做一下就可以。

 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


void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n);
    vi b(m);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, m - 1) cin >> b[i];
    ranges::sort(a);
    a.erase(unique(all(a)), a.end());
    vi res(n + m + 1);
    rep(i, 0, sz(a) - 1) {
        for (int j = a[i]; j <= n + m; j += a[i]) {
            res[j]++;
        }
    }
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    rep(i, 0, m - 1) {
        if (res[b[i]] == 0)
            cnt1++;
        else if (res[b[i]] > 0 && res[b[i]] < sz(a))
            cnt2++;
        else if (res[b[i]] == sz(a))
            cnt3++;
    }
    if (cnt2 % 2 == 0) {
        if (cnt3 > cnt1)
            cout << "Alice" << endl;
        else
            cout << "Bob" << endl;
    } else {
        if (cnt3 >= cnt1)
            cout << "Alice" << endl;
        else
            cout << "Bob" << endl;
    }
    return;
}

E

题目大意：Alice和Bob在玩一副扑克牌，最初是空的，他们玩了 $m$ 轮，每轮的规则如下：

一张值为 $a_i$ 的牌被添加进牌组（保证之前没有为 $a_i$ 的），如果牌组中的牌少于3，则游戏结束。

否则，Alice从牌组中选择一张牌，Bob在知道Alice选了哪张牌的情况下选一张牌（不能选择同一张牌），再从剩下的牌中均匀随机选择一张牌，最终三张牌都放回牌组。

假设 $a$ 是Alice选出的牌， $b$ 是Bob选出的牌， $c$ 是随机抽出的牌，那么 Bob会收到以下规则的积分：

若 $|a-c| \leq |b-c|$ ，或者 $a < c < b $ 或者 $b < c < a$ ，则收到零分。

否则收到 $|b-c|$ 分。

Alice每轮的目标都是最小化Bob的期望得分，Bob是最大化期望得分，在最佳策略下，Bob每轮的期望得分是多少？如果是分数请乘 $998244353$ 的逆元。

数据范围： $3 \leq m \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^12$ 。

思路：显然的是，如果每轮都按递增顺序排列，Bob需要把牌取到Alice每次取的两侧来保证自己的期望最大。

也就是说，需要维护一个数据结构，保证它是递增的，同时要动态维护它的前缀和，想到动态我们通常会想到树状数组。

但是递增很难办啊，必须维护一个treap吗？有点麻烦了，其实在cf只要玩会树状数组和线段树就很强了，说明完全没有必要。

考虑某个元素的贡献，只需要计算比它小的元素的数量和前缀总和即可，那么完全可以考虑权值树状数组，并对原数组做一个离散化。

接着考虑Alice，显然每次查找是 $O(n)$ 的，非常慢，那么从贪心的角度考虑，贡献最小的地方一定是前缀贡献 $\leq $ 后缀贡献的最后一个地方，或者后缀贡献 $>$ 前缀贡献的第一个地方，而这两个函数都是单调的，因此可以使用二分查找出这个交点。

同时，每次离散化后的权值树状数组中，查找某个下标在离散化后数组的排名，根据树状数组二分，是 $O(\log n)$ 的，总体时间复杂度为 $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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134


template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
constexpr int MOD = 998244353;
int mul(int x, int y) { return x * 1LL * y % MOD; }
int qpow(int x, int y) {
    int z = 1;
    while (y > 0) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}  // 求x**y%MOD
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    auto sorted = a;
    ranges::sort(sorted);
    sorted.erase(unique(all(sorted)), sorted.end());
    int m = sz(sorted);
    Tree cnt(m);
    Tree fen(m);
    rep(i, 0, n - 1) {
        auto x = ranges::lower_bound(sorted, a[i]);
        int tem = x - sorted.begin();
        cnt.add(tem, 1);
        fen.add(tem, a[i]);
        if (i < 2) continue;
        int l = 2, r = i, mid, ans;
        auto calc = [&](int mid) -> pll {
            int c = cnt.lower_bound(mid);
            ll left_cost = 0, right_cost = 0;
            int c1 = cnt.lower_bound(mid - 1);
            int c2 = cnt.lower_bound(mid + 1);
            if (c1 > 0) {
                ll left_cnt = cnt.query(0, c1 - 1);
                ll left_sum = fen.query(0, c1 - 1);
                left_cost = left_cnt * sorted[c1] - left_sum;
            }
            if (c2 < m - 1) {
                ll right_cnt = cnt.query(c2 + 1, m - 1);
                ll right_sum = fen.query(c2 + 1, m - 1);
                right_cost = right_sum - right_cnt * sorted[c2];
            }
            return {left_cost, right_cost};
        };
        auto check = [&](int mid) -> bool {
            auto [a1, b1] = calc(mid);
            return a1 <= b1;
        };
        while (l <= r) {
            mid = (l + r) / 2;
            if (check(mid)) {
                ans = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        auto [l1, r1] = calc(max(1, ans));
        auto [l2, r2] = calc(min(ans + 1, i + 1));
        ll res = min(max(l1, r1), max(l2, r2));
        cout << res % MOD * qpow(i - 1, MOD - 2) % MOD << endl;
    }
    cout << endl;
    return;
}

Codeforces Round #1083(Div.2)

这场没打，后续补的时候发现题其实都很trivial~

C

题目大意：目前有 $n$ 篇博客，在第 $i$ 篇博客中提到的用户分别为 $a_{i,1},\ldots,a_{i,l_i}$ 。

现在要修改这 $n$ 篇博客的发布顺序，给定一个序列 $Q$ ，当某篇未发布的博客发布的时候，依次遍历它提到的用户，当遍历到用户 $x$ 时，若它不在 $Q$ 中，则提到 $Q$ 的最前面，反之则删除它本来在的地方并提到 $Q$ 的最前面。

现在，请你求出字典序最小的 $Q$ 。

数据范围： $1 \leq n \leq 3000, 1\leq l_i \leq 3000, 1 \leq sum(n) \leq 3000, 1 \leq \sum\limits_{i=1}^{n}l_i \leq 3000$ 。

思路：这个贪心其实蛮难的，首先容易注意到应该从各个博客的结尾出发倒序遍历，越小的记号越晚出现最好。

随后，考虑从前到后遍历，由于我们可以接受 $O(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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


void solve() {
    int n;
    cin >> n;
    vi l(n);
    vvi a(n);
    rep(i, 0, n - 1) {
        cin >> l[i];
        a[i].resize(l[i]);
        rep(j, 0, l[i] - 1) cin >> a[i][j];
    }
    vi res;
    set<int> s;
    deque<int> d;
    vector<bool> vis(n, false);
    rep(i, 0, n - 1) {
        vi tem;
        vi tem2;
        int idx = -1;
        rep(j, 0, n - 1) {
            if (vis[j]) continue;
            tem.clear();
            set<int> s1;
            frep(v, sz(a[j]) - 1, 0) {
                if (s.count(a[j][v]) || s1.count(a[j][v])) continue;
                tem.push_back(a[j][v]);
                s1.insert(a[j][v]);
            }
            if (tem.empty()) continue;
            if (tem2.empty() || tem < tem2) {
                tem2 = tem;
                idx = j;
            }
        }
        if (idx == -1) break;
        vis[idx] = true;
        rep(j, 0, sz(tem2) - 1) {
            if (!s.count(tem2[j])) {
                d.push_back(tem2[j]);
                s.insert(tem2[j]);
            }
        }
    }
    while (!d.empty()) {
        auto node = d.front();
        d.pop_front();
        res.push_back(node);
    }
    for (int& p : res) cout << p << ' ';
    cout << endl;
    return;
}

D

题目大意：给定一个长度为 $n$ 的排列 $a$ ，我们定义具有以下性质的数组 $b$ 为酷数组，如果不存在 $b_i=\mathrm{max}(b_{i-1},b_i,b_{i+1})$ 。

现在对于 $a$ ，如果存在 $a_i=\mathrm{max}(a_{i-1},a_i,a_{i+1})$ ，则可以删除 $a_{i-1}$ 或者 $a_{i+1}$ ，求要变为酷数组所需要的最少步数。

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

思路：下面我们先介绍一种叫做笛卡尔树的数据结构，它可以成为我们在完成单调栈题目时的轮椅。

这棵树的每个节点有两个属性，一个是它在原数组中的下标，一个是它的值。

同时，这棵树关于原数组的下标形成一棵BST，因此它的中序遍历结果就是原数组，且这棵树的每棵子树都关于值形成大根堆/小根堆，于是它的左子树就是往左边延伸小于/大于它的值，右边亦然。

是不是想到了接雨水、最大矩形等题目？是的，它对单调栈贡献法的题目有奇效，哈哈，非常神奇吧~

回到原题，这玩意到底有什么用？

首先观察到一个性质，就是最大的数一定要移到最左边或者最右边，于是对于笛卡尔树，就要舍弃当前节点的左子树或者右子树，以此类推，最后剩下的元素就是从根节点到叶子节点的节点数。

于是，要使剩下的节点数最大，那么就是树的深度，因此答案为 $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


// 笛卡尔树，默认为大根堆
template <class T, typename Compare = std::greater<T>>
struct CartesianTree {
    T inf = std::numeric_limits<T>::max();

    struct Node {
        int idx;               // 原数组下标
        T val;                 // 权值
        int par, siz;          // 父节点索引，子树大小
        std::array<T, 2> son;  // 左儿子，右儿子

        Node(int idx = 0, T val = 0, int par = 0, int siz = 0) : idx(idx), val(val), par(par), siz(siz), son{} {}
    };

    std::vector<Node> t;

    CartesianTree() { init(); }

    void init(Compare comp = Compare()) {
        t.assign(1, {0, 0, 0});
        t[0].son.fill(0);
        if (comp(-inf, inf))
            t[0].val = -inf;
        else
            t[0].val = inf;
    }  // 自动建立虚拟节点

    void add(int idx, T val, int par = 0) { t.emplace_back(idx, val, par); }  // 负责把元素加进末尾，需要使用1-based

    int work(Compare comp = Compare()) {
        for (int i = 1; i < t.size(); i++) {
            int k = i - 1;
            while (comp(t[i].val, t[k].val)) k = t[k].par;
            t[i].son[0] = t[k].son[1];
            t[k].son[1] = i;
            t[i].par = k;
            t[t[i].son[0]].par = i;
        }  // 遍历，砍树枝
        auto dfs = [&](auto&& dfs, int u) -> void {
            if (!u) return;
            t[u].siz = 1;
            dfs(dfs, ls(u));
            dfs(dfs, rs(u));
            t[u].siz += t[ls(u)].siz + t[rs(u)].siz;
        };  // 进行一个dfs
        dfs(dfs, t[0].son[1]);
        return t[0].son[1];
    }

    int depth() {
        int ans = 0;
        auto dfs = [&](auto&& dfs, int u, int d) -> void {
            if (!u) return;
            ans = max(ans, d);
            dfs(dfs, ls(u), d + 1);
            dfs(dfs, rs(u), d + 1);
            return;
        };
        dfs(dfs, t[0].son[1], 1);
        return ans;
    }

    int Left(int p) { return p - size(ls(p)); }  // 左边最远

    int Right(int p) { return p + size(rs(p)); }  // 右边最远

    int size(int p) { return t[p].siz; }

    int ls(int p) { return t[p].son[0]; }

    int rs(int p) { return t[p].son[1]; }

    int par(int p) { return t[p].par; }
};
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    CartesianTree<int> tree;
    int ans = 0;
    rep(i, 0, n - 1) { tree.add(i + 1, a[i]); }
    int root = tree.work();
    cout << n - tree.depth() << endl;
    return;
}

当然，此处还有一种参考朋友的做法，显而易见的是最后的数组必然形成先递减后递增的结构（如果只有递减或者只有递增，则视为退化后的）。

于是，可以进行前后缀分解，枚举当前谷底，并取最值。

但是，这里要注意的是，某一端的贡献必须使用单调栈来做而不是 LIS ，因为可以从题目读出，这里采用的是两个小数吃掉一个大数的机制。

Kita3’s submission

E

题目大意：给定一个大小为 $m$ 的数组 $a$ ，现在需要对它进行一次以下操作：

将它划分为若干个子段，然后每个子段分别反转。

现在给定一个数组 $T$ ，问能通过上述操作转变为 $T$ 的数组个数，并模998244353。

数据范围： $1 \leq n \leq 8000, 1 \leq T_i \leq 8000$ 。

思路：看到这个题目马上就想到可能是DP，哈哈哈。

随后，对于重复计数问题，最关键的就是要找到怎么样才是重复的，通过画图发现如果 $[l1,r1] \cup [r1+1,r2]$ 翻转后的效果与 $[l1,r2]$ 一样，则 $[l1,r2]$ 的 border 长度必然大于0。

于是，显然需要使用 KMP 算法在 $O(n^2)$ 复杂度下求出任意子串的border ，然后使用 $O(n^2)$ 的DP，如果当前子串的 border 长度大于0则不发生转移，结束了。

非常trivial的一道题，体感比D简单~

 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


const int MOD = 998244353;
vector<int> kmp(const vi& pattern) {
    int m = pattern.size();
    vector<int> pi(m);
    int cnt = 0;
    for (int i = 1; i < m; i++) {
        int b = pattern[i];
        while (cnt && pattern[cnt] != b) cnt = pi[cnt - 1];
        if (pattern[cnt] == b) cnt++;
        pi[i] = cnt;
    }
    return pi;
}
void solve() {
    int n;
    cin >> n;
    vi a(n);
    vvi border(n + 1);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) {
        vi tem(a.begin() + i, a.end());
        auto tem2 = kmp(tem);
        border[i + 1] = tem2;
    }
    vi dp(n + 1);
    dp[0] = 1;
    rep(i, 1, n) {
        rep(j, 0, i - 1) {
            if (border[j + 1][i - j - 1])
                continue;
            else {
                dp[i] += dp[j] % MOD;
                dp[i] %= MOD;
            }
        }
    }
    cout << dp[n] << endl;
    return;
}

Codeforces Round #1084(Div.3)

这场也没打，感觉D偏难了，其他的题都比较trivial~

C

题目大意：给定一个只包含小写英文字母的字符串，现在可以选择一对整数 $1 \leq i < j \leq n$ ，它们相等且都不是*，且它们之间的字符都是*，然后把它们都变为*。

如果无法变了，游戏结束，此时如果每个字符都是*，则输出YES,否则输出NO。

数据范围： $1 \leq n \leq 5000,1 \leq sum(n) \leq 5000$ 。

思路：看到这种类似邻项消除的题目，肯定要想着用栈做，然后最后只需要检查栈是否为空即可，不过这种题目容易忘记。

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


import sys

input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())


def solve():
    n = ii()
    s = input()
    st = []
    for i in range(n):
        st.append(s[i])
        if len(st) >= 2 and st[-1] == st[-2]:
            st.pop()
            st.pop()
    print("NO" if st else "YES")
    return


for _ in range(ii()):
    solve()

D

题目大意：给定 $n$ 的排列，现在数组中间有两个传送门，可以把左边传送门左边的数传到右边传送门的右边，或者把左边传送门右边的数传到右边传送门的左边，问最终能得到的最小字典序序列是什么。

数据范围： $1 \leq n \leq 2 \cdot 10^5, 0 \leq x < y \leq 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


void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    int mixx = INT_MAX;
    rep(i, x, y - 1) mixx = min(mixx, a[i]);
    int tem = 0;
    rep(i, x, y - 1) {
        if (a[i] == mixx) tem = i - x;
    }
    auto tem2 = a;
    int l = y - x;
    rep(i, x, y - 1) { a[x + (i - x - tem + l) % l] = tem2[i]; }
    bool flag = false;
    rep(i, 0, x - 1) {
        if (a[i] > a[x] && flag == false) {
            flag = true;
            rep(j, x, y - 1) cout << a[j] << ' ';
        }
        cout << a[i] << ' ';
    }
    rep(i, y, n - 1) {
        if (a[i] > a[x] && flag == false) {
            flag = true;
            rep(j, x, y - 1) cout << a[j] << ' ';
        }
        cout << a[i] << ' ';
    }
    if (!flag) {
        rep(i, x, y - 1) cout << a[i] << ' ';
    }
    cout << endl;
    return;
}

E

题目大意：给定一个 $n$ 个元素的数组 $a$ ，Alice和Bob在上面博弈。

Alice先开始，轮到每个玩家的时候，如果 $a$ 是非递减的，那么游戏结束，否则可以将某个 $x$ 拆成 $y,z,yz=x$ ，同时 $y$ 和 $z$ 需要位于 $x$ 的原来位置，但顺序可以自由分配，如果无法拆则游戏结束。

游戏结束的时候，如果 $a$ 是非递减的，那么Bob获胜，反之Alice获胜，现在需要你给出双方都以最优最优策略进行游戏的结果。

数据范围： $1 \leq n \leq 10^5,1 \leq a_i \leq 10^6$ 。

思路：首先考虑 Alice 只需要每次将一个数的最小素因子丢在后面，那么她就赢了。

因此，只需要计算一个数是否只是某个素因子的幂次，然后后续再比较即可。

 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


constexpr int MX = 1e6 + 1;
int lpf[MX];  // 存储每个数的最小素因子，复杂度O(NloglogN)
auto init = [] {
    for (int i = 2; i < MX; i++) {
        if (lpf[i] == 0) {
            for (int j = i; j < MX; j += i) {
                if (lpf[j] == 0) lpf[j] = i;
            }
        }
    }
    return 0;
}();
// 质因数分解，返回值为pair<素因子，素因子次幂>，复杂度O(logN)
vector<pair<int, int>> cnt(int x) {
    vector<pair<int, int>> res;
    while (x > 1) {
        int p = lpf[x];
        int e = 1;
        for (x /= p; x % p == 0; x /= p) {
            e++;
        }
        res.emplace_back(p, e);
    }
    return res;
}
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    bool flag = true;
    rep(i, 1, n - 1) {
        if (a[i] < a[i - 1]) {
            flag = false;
            break;
        }
    }
    if (flag) {
        cout << "Bob" << endl;
        return;
    }
    rep(i, 0, n - 1) {
        if (a[i] == 1) continue;
        auto tem = cnt(a[i]);
        if (sz(tem) >= 2) {
            cout << "Alice" << endl;
            return;
        }
        a[i] = tem[0].first;
    }
    flag = true;
    rep(i, 1, n - 1) {
        if (a[i] < a[i - 1]) {
            flag = false;
            break;
        }
    }
    if (flag)
        cout << "Bob" << endl;
    else
        cout << "Alice" << endl;
    return;
}

F

题目大意：现在有 $n$ 个粒子，每个粒子的能量为 $x$ ，压力为 $y$ ，这表示它最多与 $y$ 个粒子一起共存。

现在有一个商店，这个商店出售 $m$ 个粒子，每个粒子的能量和压力都给出，现在要求出对于每个商店的粒子，将它加入原来粒子群后，取出某些粒子（买来的粒子不一定要取出）所能获得的最大能量值。

数据范围： $1 \leq n,m \leq 2 \cdot 10^5, 1 \leq x \leq 10^9, 0 \leq y \leq n, 1 \leq sum(n+m) \leq 2 \cdot 10^5$ 。

思路：对于这种题有个套路，就是要先计算出总体的粒子的最大数，然后再考虑选入这个粒子后的最大数。

首先，很容易想到枚举集合中最小压力数，因此考虑倒序遍历。

然后，考虑选入当前商店粒子，设它的压力值为 $y$ ，则需要求出压力值大于等于 $y$ ，且集合数小于等于 $y$ 的合法集合最大值。

随后，只需要使用堆倒序遍历确定集合大小，并取前缀最大值使得可以进行 $O(1)$ 查询。

比较trivial，但是ds对我来说比较难想，就卡了一下后面取看题解了。

 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


void solve() {
    int n, m;
    cin >> n >> m;
    vector<pii> ma(n);
    vector<pii> ma2(m);
    rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
    rep(i, 0, m - 1) cin >> ma2[i].first >> ma2[i].second;
    vl suf(n + 2);
    priority_queue<ll, vector<ll>, greater<>> q;
    map<int, vector<int>> ma3;
    rep(i, 0, n - 1) ma3[ma[i].second].push_back(ma[i].first);
    ll tem = 0;
    ll ans = 0;
    frep(i, n, 0) {
        if (ma3.count(i)) {
            for (auto& p : ma3[i]) {
                q.push(p);
                tem += 1LL * p;
            }
        }
        while (sz(q) > i + 1) {
            auto node = q.top();
            q.pop();
            tem -= node;
        }
        suf[i + 1] = tem;
        if (sz(q) == i + 1) suf[i + 1] -= q.top();
        ans = max(ans, tem);
    }
    rep(i, 1, n + 1) suf[i] = max(suf[i - 1], suf[i]);
    rep(i, 0, m - 1) { cout << max(ans, 1LL * ma2[i].first + suf[ma2[i].second + 1]) << ' '; }
    cout << endl;
    return;
}

G

题目大意：现在给定一个 $x$ 和 $n$ 个计算操作，计算操作分为加减乘除四种，问按照任意次序执行这些操作后，得到的数的期望是多少，并模 $10^9+7$ 。

数据范围： $1 \leq n \leq 3000, 1 \leq x \leq 10^9, 1 \leq sum(n^2) \leq 3000^2$ 。

思路：首先考虑把减法和除法分别变成加法和乘逆元，这是显然的。

随后，注意到一个加法的贡献只跟后面它乘的数有关系，考虑现在 $m$ 个乘数的排列，加法的数就是插空法。

现在，考虑插入一个加数，它的背后有 $x$ 个乘数的概率，计算方案数显然是 $\frac{x!(m-x)!}{(m+1)!}$ 。

由于对每个加数，它们的位置都可以互换，因此只需要把加数的总和丢进去。

接着，还需要计算在 $m$ 个乘数中取 $x$ 个乘数乘起来的期望，这个可以用子序列DP做出来。

最后，不要忘了 $x$ 也是有贡献的。

其实很trivial，感觉比D简单多了~

 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


constexpr int MOD = 1e9 + 7;
constexpr int MX = 3001;
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    int n;
    ll x;
    cin >> n >> x;
    map<char, vl> ma;
    string s;
    ll tot = 0;
    rep(i, 0, n - 1) {
        cin >> s;
        if (s[0] == '/') {
            s[0] = 'x';
            ma[s[0]].push_back(qpow(stoll(s.substr(1)), MOD - 2));
        } else if (s[0] == '-') {
            s[0] = '+';
            ma[s[0]].push_back(-stoll(s.substr(1)));
        } else
            ma[s[0]].push_back(stoll(s.substr(1)));
    }
    ll ans = 0;
    int m = sz(ma['x']);
    vvl dp(m + 1, vl(m + 1));
    dp[0][0] = 1;
    rep(i, 1, m) {
        dp[i] = dp[i - 1];
        rep(j, 1, m) {
            dp[i][j] += dp[i - 1][j - 1] * ma['x'][i - 1] % MOD;
            dp[i][j] %= MOD;
        }
    }
    rep(i, 0, sz(ma['+']) - 1) { tot = (tot + ma['+'][i] + MOD) % MOD; }
    vl pre(m + 1);
    pre[0] = 1;
    rep(i, 1, m) { pre[i] = (pre[i - 1] + dp[m][i]) % MOD; }
    ll tem = x * dp[m][m] % MOD;
    rep(i, 0, m) {
        ans += tot * F[m - i] % MOD * F[i] % MOD * INV_F[m + 1] % MOD * dp[m][i] % MOD;
        ans %= MOD;
    }
    ans = (ans + tem) % MOD;
    cout << ans << endl;
    return;
}

Codeforces Round #1086(Div.2)

很有意思的一场，上大分啦~

B

题目大意：有 $n$ 张牌放在一个队列中，每张牌的值为 $a_i$ ，在任何时刻，都只能打出队列中前 $k$ 位的牌，然后把同一张牌放回牌堆底部。

有一张起初位置位于 $p$ 的牌，打出就胜利，但是要求所有牌出牌的总花费不能超过 $m$ ，现在要问你这张牌最多能打出多少次？

数据范围： $1 \leq k,p \leq n \leq 5000, 1 \leq m \leq 5000,1 \leq a_i \leq m$

思路：容易知道如果前 $k$ 个中不含胜利牌，则每次从其中取出最小的，如果含胜利牌，那么肯定取出它，因此可以将它视为 $-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


void solve() {
    int n, k, p, m;
    cin >> n >> k >> p >> m;
    p--;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    int ans = 0;
    int tot = a[p];
    int tem = 0;
    a[p] = -1;
    deque<int> d;
    priority_queue<int, vector<int>, greater<>> q;
    rep(i, 0, k - 1) q.push(a[i]);
    rep(i, k, n - 1) d.push_back(a[i]);
    while (tem <= m) {
        auto node = q.top();
        q.pop();
        if (node == -1) {
            if (tem + tot > m) break;
            ans++;
            tem += tot;
            d.push_back(-1);
            auto tem2 = d.front();
            d.pop_front();
            q.push(tem2);
        } else {
            if (tem + node > m) break;
            tem += node;
            d.push_back(node);
            auto tem2 = d.front();
            d.pop_front();
            q.push(tem2);
        }
    }
    cout << ans << endl;
    return;
}

C

题目大意：给定 $n$ 个任务，起初你的体力为 $1$ ，对于每个任务，它的整数值为 $c_i$ ，难度为 $p_i$ ，如果你不完成它，那么什么都不会发生，如果完成它，可以拿到 $S \cdot c_i$ 分， $S$ 为当前体力，随后 $S$ 会变成 $S \cdot(1-\frac{p_i}{100})$ ，求能达到的最大得分。

数据范围： $1 \leq n \leq 10^5,1 \leq c_i \leq 100,0 \leq p_i \leq 100$ 。

思路：首先观察到，无论当前的 $S$ 如何，后续能获取的最大值是固定的，也就是 $S \cdot k$ ，这里 $k$ 是与 $S$ 无关的某个常数。

也就是说，完全可以假设 $dp[i]$ 为从这里开始的强度，然后倒着遍历，有 $dp[i]=max(dp[i+1],c[i]+(1-\frac{p[i]}{100})dp[i+1])$ 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void solve() {
    int n;
    cin >> n;
    vector<pii> ma(n);
    rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
    double ans = 0.0;
    frep(i, n - 1, 0) { ans = max(ans, (double)ma[i].first + (1.0 - (double)(ma[i].second) / 100.0) * ans); }
    cout << fixed << setprecision(10) << ans << endl;
    return;
}

D1

题目大意：给定一棵带有 $n$ 个节点的无向树，现在给每个边加了一个方向，给定所有元素之间能不能互相到达的矩阵，问是否能还原出加方向后树的结构？

数据范围： $2 \leq n\leq 500, 1 \leq sum(n^3) \leq 500^3$

思路：看到这个必然考虑弗洛伊德，这里有一个反向的思路，就是对于一个已经处理好弗洛伊德的矩阵，怎么把它还原回原来的矩阵，那么就是如果一个点是间接连上的，那么就把它还原。

接着，判断一下处理出来的基图是否是一棵树，并且边数跟连通性对不对即可，赛时确实有点蠢。

 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


void solve() {
    int n;
    cin >> n;
    vector<string> a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vvi ma(n, vi(n));
    rep(i, 0, n - 1) { rep(j, 0, n - 1) ma[i][j] = a[i][j] - '0'; }
    auto ma2 = ma;
    rep(i, 0, n - 1) {
        if (ma[i][i] == 0) {
            cout << "NO" << endl;
            return;
        }
    }
    rep(k, 0, n - 1) {
        rep(i, 0, n - 1) {
            rep(j, 0, n - 1) {
                if (ma[i][k] == 1 && ma[k][j] == 1) {
                    if (k == i || k == j) continue;
                    if (ma[i][j] == 0) {
                        cout << "NO" << endl;
                        return;
                    }
                    if (ma[i][j] == 1) ma2[i][j] = 0;
                }
            }
        }
    }
    vector<pii> res;
    vector<vector<bool>> vis(n, vector<bool>(n, false));
    rep(i, 0, n - 1) vis[i][i] = true;
    auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
        rep(i, 0, n - 1) {
            if (!ma2[x][i] || i == x) continue;
            if (vis[x][i]) continue;
            res.emplace_back(x + 1, i + 1);
            vis[x][i] = true;
            dfs2(i, x);
        }
        return;
    };
    rep(i, 0, n - 1) { dfs2(i, -1); }
    map<int, int> ma3;
    for (auto& p : res) {
        ma3[p.first]++;
        ma3[p.second]++;
    }
    if (sz(res) != n - 1 || sz(ma3) != n) {
        cout << "NO" << endl;
        return;
    }
    vvi ma4(n);
    for (auto& p : res) {
        ma4[p.first - 1].push_back(p.second - 1);
        ma4[p.second - 1].push_back(p.first - 1);
    }
    int ans = 0;
    vector<bool> vis2(n, false);
    auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
        vis2[x] = true;
        for (auto& p : ma4[x]) {
            if (p == pa || vis2[p]) continue;
            dfs(p, x);
        }
        return;
    };
    rep(i, 0, n - 1) {
        if (!vis2[i]) {
            ans++;
            dfs(i, -1);
        }
    }
    if (ans >= 2) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    for (auto& p : res) cout << p.first << ' ' << p.second << endl;
    return;
}

D2

题目大意与上题相同。

数据范围： $2 \leq n \leq 8000, 1 \leq sum(n^2) \leq 8000^2$ 。

思路：非常显然地，上题的做法过不去，且本题正解应该是 $O(n^2)$ 或者 $O(n^2 \log n)$ ，不过赛时竟然放 $O(\frac{n^3}{w})$ 复杂度的过去了，到底是何意味。

首先考虑 $O(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
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


void solve() {
    int n;
    cin >> n;
    vector<string> ma(n);
    rep(i, 0, n - 1) cin >> ma[i];
    rep(i, 0, n - 1) {
        if (ma[i][i] == '0') {
            cout << "NO" << '\n';
            return;
        }
    }
    rep(i, 0, n - 1) {
        rep(j, i + 1, n - 1) {
            if (ma[i][j] == '1' && ma[j][i] == '1') {
                cout << "NO" << '\n';
                return;
            }
        }
    }
    vi deg(n);
    vvi ma2(n);
    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) {
            if (i == j || ma[i][j] == '0') continue;
            ma2[i].push_back(j);
            deg[j]++;
        }
    }
    queue<int> q;
    rep(i, 0, n - 1) {
        if (!deg[i]) q.push(i);
    }
    vi tem;
    while (!q.empty()) {
        auto node = q.front();
        tem.push_back(node);
        q.pop();
        for (int& p : ma2[node]) {
            if (--deg[p] == 0) q.push(p);
        }
    }
    if (sz(tem) != n) {
        cout << "NO" << '\n';
        return;
    }
    vector<pii> res;
    rep(i, 0, n - 1) {
        int t = tem[i];
        rep(j, i + 1, n - 1) {
            int v = tem[j];
            if (ma[t][v] == '1') {
                res.emplace_back(t + 1, v + 1);
                if (sz(res) > n - 1) {
                    cout << "NO" << '\n';
                    return;
                }
                for (int& p : ma2[v]) {
                    if (ma[t][p] == '1') {
                        ma[t][p] = '0';
                    } else {
                        cout << "NO" << '\n';
                        return;
                    }
                }
            }
        }
    }
    if (sz(res) != n - 1) {
        cout << "NO" << '\n';
        return;
    }
    vector<bool> vis(n, false);
    int ans = 0;
    vvi ma3(n);
    for (auto& p : res) {
        ma3[p.first - 1].push_back(p.second - 1);
        ma3[p.second - 1].push_back(p.first - 1);
    }
    auto dfs = [&](this auto&& dfs, int x) -> void {
        vis[x] = true;
        for (auto& p : ma3[x]) {
            if (!vis[p]) dfs(p);
        }
    };
    rep(i, 0, n - 1) {
        if (!vis[i]) {
            ans++;
            dfs(i);
        }
    }
    if (ans >= 2) {
        cout << "NO" << '\n';
        return;
    }
    cout << "YES" << '\n';
    for (auto& p : res) cout << p.first << ' ' << p.second << '\n';
    return;
}

Educational Codeforces Round #188

这场是不是有点太简单~依旧上大分。

C

题目大意：Alice,Bob和Carol到泉水边取水。Alice每隔 $a$ 天去一次，Bob每隔 $b$ 天去一次，Carol每隔 $c$ 天去一次。

每天，去的人会平分 $6$ 升水，问他们在 $m$ 天内各收集了多少水？

数据范围： $1 \leq a,b,c \leq 10^6, 1 \leq m \leq 10^{17}$

思路：非常典的容斥。

 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


void solve() {
    ll a, b, c;
    ll m;
    cin >> a >> b >> c >> m;
    auto check = [&](ll x, ll y) {
        ll g = __gcd(x, y);
        if (x / g > (m + 1) / y) return m + 1;
        return (x / g) * y;
    };
    ll tem = check(a, b);
    ll tot = check(tem, c);
    ll re = m / tot;
    ll tem2 = check(a, c);
    ll tem3 = check(b, c);
    ll re1 = m / tem - re;
    ll re2 = m / tem2 - re;
    ll re3 = m / tem3 - re;
    ll res1 = m / a - (re1 + re2) - re;
    ll res2 = m / b - (re1 + re3) - re;
    ll res3 = m / c - (re2 + re3) - re;
    ll resa = 1LL * 6 * res1 + 1LL * 3 * (re1 + re2) + 1LL * 2 * re;
    ll resb = 1LL * 6 * res2 + 1LL * 3 * (re1 + re3) + 1LL * 2 * re;
    ll resc = 1LL * 6 * res3 + 1LL * 3 * (re2 + re3) + 1LL * 2 * re;
    cout << resa << ' ' << resb << ' ' << resc << endl;
    return;
}

D

题目大意：给定一个 $n$ 个点和 $m$ 条边的无向图，顶点的编号为 $1$ 到 $n$ ，这张图没有自环和重边。

现在需要为每条边选择一个方向，确定边的方向后，我们称一条形如 $v_1 \rightarrow v_2 \leftarrow v_3 \rightarrow v_4 \ldots$ 的路径为交替路径。

如果原始图中以顶点 $v$ 为起点的所有路径（不一定是简单路径）在生成的有向图中都是交替出现的，那么称顶点 $v$ 为美丽顶点，现在请求出美丽顶点的最大数目。

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

思路：首先非常显然地，看到类似交替路径的字眼，就会想到二分图，然后由于这里可以不是简单路径，因此不难验证这边不存在奇环，也确实是二分图。

然后考虑染色（毕竟这个分段能出的只有染色），对于每个联通分量，首先染色判断它是不是二分图，如果是，则贡献为两种染色数量的最大值，如果不是则贡献为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


void solve() {
    int n, m, x, y;
    cin >> n >> m;
    vvi ma(n);
    rep(i, 0, m - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    vector<int> vis(n);
    int ans = 0, ans2 = 0;
    bool flag = true;
    auto dfs = [&](this auto&& dfs, int x, int c) -> void {
        vis[x] = c;
        if (c == 1)
            ans++;
        else
            ans2++;
        for (int& p : ma[x]) {
            if (!vis[p])
                dfs(p, 3 - c);
            else if (vis[p] == c) {
                flag = false;
            }
        }
        return;
    };
    int res = 0;
    rep(i, 0, n - 1) {
        if (vis[i]) continue;
        ans = 0, ans2 = 0;
        flag = true;
        dfs(i, 1);
        if (flag) res += max(ans, ans2);
    }
    cout << res << endl;
    return;
}

E

题目大意：对于正整数 $x$ ，字符串 $S(x)$ 是这么形成的：

首先把当前 $x$ 连接到字符串末尾。

随后，如果 $x \leq 9$ ，则退出，否则 $x=digit(x)$ ，这里 $digit(x)$ 是 $x$ 在十进制下数位和。

给定一个由数字组成的字符串 $S$ ，请重新排列该字符串中的字符，使其组成某个数字 $x$ 的 $S(x)$ ，题目保证有解。

数据范围： $1 \leq |S| \leq 10^5,1 \leq sum(|S|) \leq 10^5$

思路：一看下去其实有点无从下手的题，其实大多数时候都是在找性质。

首先观察到， $x_1+x_2+\ldots +x_k+x_k=digit(S)$ ，其中每个 $x_i$ 是第 $i$ 个数的数位和。

那么，这里可以考虑到 $digit(S) \leq 9 \cdot 10^5$ ，因此可以暴力枚举 $x_1$ ，有了 $x_1$ 之后，其实就得到了第二个数，然后就可以算出后面所有的数了，只需考虑所有的和是否等于 $digit(S)$ ，以及给出的所有数字是否刚好用完即可。

不过有点史，还是需要好好写一下。

  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


void solve() {
    string s;
    cin >> s;
    if (sz(s) == 1) {
        cout << s << endl;
        return;
    }
    vi cnt(10);
    rep(i, 0, sz(s) - 1) { cnt[s[i] - '0']++; }
    int ans = 0;
    rep(i, 0, 9) ans += cnt[i] * i;
    int maxx = 0;
    rep(i, 1, ans) {
        int sum = i;
        int tem = i;
        vi temp;
        temp.push_back(i);
        while (tem > 0) {
            if (0 <= tem && tem <= 9) {
                sum += tem;
                temp.push_back(i);
                break;
            }
            int tem2 = 0;
            int tem3 = tem;
            while (tem3 > 0) {
                tem2 += tem3 % 10;
                tem3 /= 10;
            }
            sum += tem2;
            temp.push_back(tem2);
            tem = tem2;
        }
        if (1 <= i && i <= 9) {
            if (sum != ans || !cnt[i]) continue;
        } else {
            if (sum != ans) continue;
        }
        int sum2 = i;
        vi cnt2(10);
        while (sum2 >= 10) {
            int tem2 = sum2;
            int tem3 = 0;
            while (tem2 > 0) {
                tem3 += tem2 % 10;
                cnt2[tem2 % 10]++;
                tem2 /= 10;
            }
            sum2 = tem3;
        }
        cnt2[sum2]++;
        int sum3 = 0;
        bool flag = true;
        frep(i, 9, 0) {
            if (cnt2[i] > cnt[i]) {
                flag = false;
                break;
            }
            sum3 += i * (cnt[i] - cnt2[i]);
        }
        if (sum3 != i || !flag) continue;
        maxx = i;
        break;
    }
    string res = "";
    int maxx2 = maxx;
    vi cnt2(10);
    while (maxx2 >= 10) {
        int tem2 = maxx2;
        int tem3 = 0;
        while (tem2 > 0) {
            tem3 += tem2 % 10;
            cnt2[tem2 % 10]++;
            tem2 /= 10;
        }
        maxx2 = tem3;
    }
    cnt2[maxx2]++;
    frep(i, 9, 0) { rep(j, 0, cnt[i] - cnt2[i] - 1) res.push_back('0' + i); }
    vector<string> tem2;
    tem2.push_back(res);
    while (maxx >= 10) {
        tem2.push_back(to_string(maxx));
        int tem = 0;
        while (maxx > 0) {
            tem += maxx % 10;
            maxx /= 10;
        }
        maxx = tem;
    }
    tem2.push_back(to_string(maxx));
    int tot = 0;
    for (auto& p : tem2) {
        rep(i, 0, sz(p) - 1) { tot += (p[i] == '0'); }
    }
    rep(i, 0, cnt[0] - tot - 1) res.push_back('0');
    rep(i, 1, sz(tem2) - 1) res += tem2[i];
    cout << res << endl;
    return;
}

F

题目大意：我们称分数 $\frac{x}{y}$ 的一次增长为以下两种情况之一：

要么把分子 $x$ 加一，要么当分母 $y > 1$ 时，将其减一。

定义 $MSF(b,k)$ 为给定一个整数数组 $b_1,b_2,\ldots,b_m$ 和一个整数 $k$ 时，构造数组 $\frac{1}{b_1},\ldots,\frac{1}{b_m}$ ，一共执行 $k$ 次增长操作（每次增长的对象可以不同）后，得到的分数和的最大值。

现在给定两个整数数组 $a_1,\ldots,a_n$ 和 $k_1,\ldots,k_m$ ，请对每个 $k_i$ 计算 $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}MSF(a[l \ldots r],k_i) \pmod{998244353}$ 。

数据范围： $1 \leq n,m \leq 5 \cdot 10^5,1 \leq a_i \leq 10^8,0 \leq k_1 \leq k_2 \leq k_m \leq 10^8$ 。

思路：非常迷的是这些 $k_i$ 为啥要排好序，明明可以用在线的说，神秘出题人。

首先，看到这种双求和，在我的分段第一反应一定是单调栈贡献法，此题在Round 1082的d2C2亦有记载。

总的原始和的求法就不讲了，你都做到这里了，没必要吧。

好的，现在我们来看一下，怎么来考虑贡献。

首先，对于 $\frac{a}{b},b > 1$ 时，单次加分子的贡献为 $\frac{1}{b}$ ，减分母的贡献为 $\frac{a}{b(b-1)}$ ，因此当单次加分子的贡献大于等于单次减分母的贡献时，有 $\frac{1}{b} \leq \frac{a}{b(b-1)}$ ，也就是 $b-1 \leq a$ ，而 $b=1$ 时最优策略也是加分子，因此单步的最大贡献必然是加分子。

考虑整个区间，由于显然无论加分子还是减分母，都在分母最小的元素上做文章是最优的，因此这里单调栈的轮廓就浮现出来了，考虑当前元素作为最小的范围。

随后，当 $k$ 很大的时候，又出现了一种策略，那就是首先把 $a_i$ 减到 $1$ ，然后再每次加分子，而当 $k$ 很小的时候直接加分子就可以。

不过，为什么没有别的策略？例如给分子加一些，分母减一些，这个用数学可以证明，此处不提了。

接着，考虑它们之间的分界点，一直加分子的贡献是 $\frac{k}{b}$ ，而先减到 $1$ 再加分子的贡献为 $k-(b-1)+1-\frac{1}{b}=k-b+2-\frac{1}{b}$ ，计算可以得出，一直加分子在 $k \geq b-1$ 的时候是最优的，也就是 $k > b$ 。

于是，由于这里具有单调性，完全可以对 $a$ 进行排序，然后每次查找对应的位置，再做一下前缀和跟后缀和，这里前缀和需要做的是 $\sum\limits_{j=1}^{i} c_j$ 跟 $\sum\limits_{j=1}^{i} -b+2-\frac{1}{b}$ ，后缀和需要做的是 $\sum\limits_{i=1}^{j}\frac{c_i}{b}$ ，这里的 $c_i$ 指的都是当前元素作为最小值的范围。

最后，注意一下C++需要按步取模，第一次交忘了一个取模就wa19了，有点难受，不过这题作为edu的F，最多就是个d2D的水平，不知道出题人在干什么。

 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


constexpr int MOD = 998244353;
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
void solve() {
    ll n, m, k;
    cin >> n >> m;
    vector<pii> a(n);
    rep(i, 0, n - 1) {
        cin >> a[i].second;
        a[i].first = 1;
    }
    vector<pll> b(n);
    ll tot = 0;
    vi r(n, n);
    vi l(n, -1);
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[s.top()].second > a[i].second) s.pop();
        if (!s.empty()) r[i] = s.top();
        s.push(i);
    }  // 求右边第一个小于的下标
    while (!s.empty()) s.pop();
    for (int i = 0; i <= n - 1; i++) {
        while (!s.empty() && a[s.top()].second >= a[i].second) s.pop();
        if (!s.empty()) l[i] = s.top();
        s.push(i);
    }  // 求左边第一个小于的下标
    rep(i, 0, n - 1) {
        b[i].first = a[i].second;
        b[i].second = 1LL * (r[i] - i) * (i - l[i]);
    }
    rep(i, 0, n - 1) {
        tot += 1LL * (i + 1) * (n - i) % MOD * qpow(a[i].second, MOD - 2) % MOD;
        tot %= MOD;
    }
    ranges::sort(b);
    vl pre1(n);
    vl suf1(n);
    vl pre2(n);
    pre1[0] = b[0].second % MOD;
    rep(i, 1, n - 1) { pre1[i] = (pre1[i - 1] + b[i].second % MOD) % MOD; }
    pre2[0] = b[0].second % MOD * (((2 - b[0].first % MOD - qpow(b[0].first, MOD - 2)) % MOD + MOD) % MOD) % MOD;
    rep(i, 1, n - 1) {
        ll tem = b[i].second % MOD * (((2 - b[i].first % MOD - qpow(b[i].first, MOD - 2)) % MOD + MOD) % MOD) % MOD;
        pre2[i] = (pre2[i - 1] + tem) % MOD;
    }
    suf1[n - 1] = b[n - 1].second % MOD * qpow(b[n - 1].first, MOD - 2) % MOD;
    frep(i, n - 2, 0) {
        ll tem = b[i].second % MOD * qpow(b[i].first, MOD - 2) % MOD;
        suf1[i] = (suf1[i + 1] + tem) % MOD;
    }
    rep(i, 0, m - 1) {
        cin >> k;
        auto x = ranges::upper_bound(b, make_pair(k, LLONG_MAX));
        int tem = x - b.begin();
        ll tem2, tem3;
        if (tem == 0)
            tem2 = 0;
        else
            tem2 = (k * pre1[tem - 1] % MOD + pre2[tem - 1]) % MOD;
        if (tem == n)
            tem3 = 0;
        else
            tem3 = k * suf1[tem] % MOD;
        cout << (tot + tem2 + tem3) % MOD << endl;
    }
    return;
}