Featured image of post Codeforces Round #1007(Div.2)

Codeforces Round #1007(Div.2)

B

题目大意：若一个长度为 $n$ 的排列 $p$ $^{\text{∗}}$ 满足：对于每个下标 $i$（$1 \le i \le n$），前 $i$ 个元素的和 $p_1 + p_2 + \ldots + p_i$ 不是完全平方数 $^{\text{†}}$，则称该排列为完美排列。需要构造完美排列。给定正整数 $n$，找出一个长度为 $n$ 的完美排列，若不存在则输出 $-1$。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 5 \cdot 10^5$，$\sum n \le 10^6$。

思路：

 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() {
    ll n;
    cin >> n;
    ll tem = n * (n + 1) / 2;
    ll tem2 = (ll)sqrt(tem);
    if (tem2 * tem2 == tem) {
        cout << -1 << endl;
        return;
    }
    vl res(n);
    rep(i, 0, n - 1) res[i] = i + 1;
    tem2 = 0;
    rep(i, 0, n - 2) {
        tem2 += res[i];
        ll tem3 = (ll)sqrt(tem2);
        if (tem3 * tem3 == tem2) {
            tem2 = tem2 - res[i] + res[i + 1];
            swap(res[i], res[i + 1]);
        }
    }
    rep(i, 0, n - 1) cout << res[i] << ' ';
    cout << endl;
    return;
}

C

题目大意：在一个意大利村庄中，一只饥饿的老鼠从给定树 $^{\text{∗}}$ 的顶点 $\textrm{st}$ 出发，该树包含 $n$ 个顶点。给定一个长度为 $n$ 的排列 $p$ $^{\text{†}}$，共有 $n$ 个步骤。在第 $i$ 步时： - 一块诱人的帕尔马干酪出现在顶点 $p_i$。若老鼠当前位于顶点 $p_i$，它将停留并享用；否则，它将沿简单路径向 $p_i$ 移动一条边。需要找到这样的排列，使得经过所有 $n$ 步后，老鼠必定到达陷阱所在的顶点 $\textrm{en}$。注意：老鼠必须在完成所有 $n$ 步后到达 $\textrm{en}$，但在过程中可能提前经过 $\textrm{en}$。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 10^5$，$1 \le \textrm{st}, \textrm{en} \le n$，$1 \le u, v \le n$，$\sum n \le 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

void solve() {
    ll n, st, en, x, y;
    cin >> n >> st >> en;
    st--, en--;
    vvi ma(n);
    rep(i, 0, n - 2) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    vi dis(n, -1);
    dis[en] = 0;
    queue<int> q;
    q.push(en);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        for (int& p : ma[node]) {
            if (dis[p] == -1) {
                dis[p] = dis[node] + 1;
                q.push(p);
            }
        }
    }
    vector<pii> ma2;
    rep(i, 0, n - 1) ma2.emplace_back(dis[i], i + 1);
    sort(all(ma2), [&](const pii& x, const pii& y) { return x.first > y.first; });
    rep(i, 0, n - 1) cout << ma2[i].second << ' ';
    cout << endl;
    return;
}

D1

题目大意：这是该问题的简单版本。不同版本的区别在于此版本中 $l = r$。仅当您解决了该问题的所有版本时才能进行 hack。给定一个正整数 $n$ 和一个无限二进制序列 $a$ 的前 $n$ 项，该序列定义如下： - 对于 $m > n$，$a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_{\lfloor \frac{m}{2} \rfloor}$ $^{\text{∗}}$。需要计算给定区间 $[l, r]$ 内元素的和：$a_l + a_{l + 1} + \ldots + a_r$。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le l = r \le 10^{18}$，$\sum n \le 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

void solve() {
    ll n, l, r;
    cin >> n >> l >> r;
    vl a(n + 2);
    rep(i, 1, n) cin >> a[i];
    vl pre(n + 2);
    rep(i, 1, n) pre[i] = pre[i - 1] ^ a[i];
    if (n % 2 == 0) {
        a[n + 1] = pre[n / 2];
        pre[n + 1] = pre[n] ^ a[n + 1];
        n++;
    }
    if (l <= n)
        cout << a[l] << endl;
    else {
        auto calc = [&](this auto&& calc, ll x) -> ll {
            if (x <= n) return pre[x];
            if (x % 2 == 1)
                return pre[n];
            else
                return pre[n] ^ calc(x / 2);
        };
        cout << calc(l / 2) << endl;
    }
    return;
}

D2

题目大意：这是该问题的困难版本。不同版本的区别在于此版本中 $l \leq r$。仅当您解决了该问题的所有版本时才能进行 hack。给定一个正整数 $n$ 和一个无限二进制序列 $a$ 的前 $n$ 项，该序列定义如下： - 对于 $m > n$，$a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_{\lfloor \frac{m}{2} \rfloor}$ $^{\text{∗}}$。需要计算给定区间 $[l, r]$ 内元素的和：$a_l + a_{l + 1} + \ldots + a_r$。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le l \leq r \le 10^{18}$，$\sum n \le 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

void solve() {
    ll n, l, r;
    cin >> n >> l >> r;
    vl a(n + 2);
    rep(i, 1, n) cin >> a[i];
    vl pre(n + 2);
    vl pre2(n + 2);
    vl pre3(n + 2);
    rep(i, 1, n) {
        pre[i] = pre[i - 1] ^ a[i];
        pre2[i] = pre2[i - 1] + a[i];
        pre3[i] = pre3[i - 1] + pre[i];
    }
    if (n % 2 == 0) {
        a[n + 1] = pre[n / 2];
        pre[n + 1] = pre[n] ^ a[n + 1];
        pre2[n + 1] = pre2[n] + a[n + 1];
        pre3[n + 1] = pre3[n] + pre[n + 1];
        n++;
    }
    auto calc3 = [&](this auto&& calc3, ll x) -> ll {
        if (x <= n) return pre[x];
        if (x % 2 == 1)
            return pre[n];
        else
            return pre[n] ^ calc3(x / 2);
    };
    auto calc2 = [&](this auto&& calc2, ll x) -> ll {
        if (x <= n) return pre3[x];
        if (pre[n] == 0)
            return pre3[n] + calc2(x / 2) - calc2(n / 2);
        else
            return pre3[n] + (x / 2 - n / 2 - calc2(x / 2) + calc2(n / 2)) + (x - n) / 2;
    };
    auto calc = [&](this auto&& cacl, ll x) -> ll {
        if (x <= n) return pre2[x];
        return pre2[n] + 2 * (calc2(x / 2) - calc2(n / 2)) - (x % 2 == 0 ? 1 : 0) * calc3(x / 2);
    };
    cout << calc(r) - calc(l - 1) << endl;
    return;
}

E

题目大意：给定一棵包含 $n$ 个顶点的树 $^{\text{∗}}$。每个顶点 $i$（$1 \le i \le n$）会以 $\frac{p_i}{q_i}$ 的概率掉落。求最终形成的森林 $^{\text{‡}}$ 中不同顶点构成叶子节点 $^{\text{§}}$ 的无序对 $^{\text{†}}$ 数量的期望值，结果对 $998\,244\,353$ 取模。注意：当顶点 $v$ 掉落时，其自身及所有相连的边将被移除，但相邻顶点的掉落状态不受 $v$ 的影响。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 10^5$，$1 \le p_i < q_i < 998\,244\,353$，$1 \le u, v \le n$，$\sum n \le 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

constexpr ll MOD = 998244353;
constexpr ll INV2 = 499122177;
ll mul(ll x, ll y) { return x * y % MOD; }
ll norm(ll x) { return (x % MOD + MOD) % MOD; }
ll qpow(ll x, ll y) {
    ll z = 1;
    while (y > 0) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}  // 求x**y%MOD

// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p

void solve() {
    ll n, x, y;
    cin >> n;
    vvi ma(n);
    vector<pll> co(n);
    vl live(n), dead(n);
    vl invd(n), sum(n);
    rep(i, 0, n - 1) cin >> co[i].first >> co[i].second;
    rep(i, 0, n - 1) {
        dead[i] = mul(co[i].first, qpow(co[i].second, MOD - 2));
        live[i] = norm(1 - dead[i]);
        invd[i] = mul(co[i].second, qpow(co[i].first, MOD - 2));
        sum[i] += mul(live[i], invd[i]);
    }
    vector<pll> edges;
    rep(i, 0, n - 2) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
        edges.emplace_back(x - 1, y - 1);
    }
    vl leaf(n), sumn(n), mult(n, 1);
    rep(i, 0, n - 1) {
        for (int& p : ma[i]) {
            mult[i] = mul(mult[i], dead[p]);
            sumn[i] = norm(sumn[i] + sum[p]);
        }
        leaf[i] = mul(mul(live[i], mult[i]), sumn[i]);
    }
    auto calc = [&](int x, int y) -> ll { return mul(mul(live[x], mult[x]), invd[y]); };
    auto calc2 = [&](int x, int y) -> ll { return mul(calc(x, y), norm(sumn[x] - sum[y])); };
    ll tot = 0, tot2 = 0;
    rep(i, 0, n - 1) {
        tot = norm(tot + leaf[i]);
        tot2 = norm(tot2 + mul(leaf[i], leaf[i]));
    }
    ll ans = mul(norm(mul(tot, tot) - tot2), INV2);
    for (auto& [x, y] : edges) {
        ans = norm(ans + mul(calc(x, y), calc(y, x)) - mul(leaf[x], leaf[y]));
    }
    rep(i, 0, n - 1) {
        ll totcalc = 0, totcalc_2 = 0;
        ll totcalc2 = 0, totcalc2_2 = 0;
        ll totleaf = 0, totleaf_2 = 0;
        for (int& p : ma[i]) {
            totcalc = norm(totcalc + calc(p, i));
            totcalc_2 = norm(totcalc_2 + mul(calc(p, i), calc(p, i)));
            totcalc2 = norm(totcalc2 + calc2(p, i));
            totcalc2_2 = norm(totcalc2_2 + mul(calc2(p, i), calc2(p, i)));
            totleaf = norm(totleaf + leaf[p]);
            totleaf_2 = norm(totleaf_2 + mul(leaf[p], leaf[p]));
        }
        ans = norm(ans + mul(live[i], mul(norm(norm(mul(totcalc, totcalc) - totcalc_2)), INV2)) +
                   mul(dead[i], mul(norm(norm(mul(totcalc2, totcalc2) - totcalc2_2)), INV2)) -
                   mul(norm(norm(mul(totleaf, totleaf) - totleaf_2)), INV2));
    }
    cout << ans << endl;
    return;
}

F

题目大意：称数组 $b$ 为 $p$-towering，当且仅当存在一个中心下标 $i$，使得所有下标 $j$ 都满足 $b_j \ge p-|i-j|$。给定数组 $a$，最多删除 $k$ 个元素，求剩余数组能构成的最大 $p$。

数据范围：$1 \le t \le 10^4$，$0 \le k < n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$，$\sum n \le 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
 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

struct Tag {
    ll add = 0;  // 懒标记初始值

    Tag(ll add = 0) : add(add) {}

    bool empty() const { return add == 0; }

    void apply(const Tag& t) { add += t.add; }  // 合并懒标记：先已有操作，再做t
};

struct Info {
    ll sum = LLONG_MAX / 3;

    Info(ll sum = LLONG_MAX / 3) : sum(sum) {}

    void apply(const Tag& t, int l, int r) { sum += t.add; }  // 把懒标记作用到当前节点
};

Info operator+(const Info& a, const Info& b) { return {min(a.sum, b.sum)}; }  // 合并两个Info

bool operator<(const Info& a, const Info& b) { return a.sum < b.sum; }  // 线段树二分用，不需要时可删

template <typename Info, typename Tag>
class LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;

    void apply(int node, int l, int r, const Tag& v) {
        info[node].apply(v, l, r);
        tag[node].apply(v);
    }

    void pushdown(int node, int l, int r) {
        if (tag[node].empty()) return;
        int m = (l + r) >> 1;
        apply(node << 1, l, m, tag[node]);
        apply(node << 1 | 1, m + 1, r, tag[node]);
        tag[node] = Tag();
    }  // 把当前节点的懒标记下传

    void maintain(int node) { info[node] = info[node << 1] + info[node << 1 | 1]; }

    void build(const vector<Info>& a, int node, int l, int r) {
        if (l == r) {
            info[node] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(a, node << 1, l, m);
        build(a, node << 1 | 1, m + 1, r);
        maintain(node);
    }  // 建树，复杂度O(n)

    void update(int node, int l, int r, int ql, int qr, const Tag& v) {
        if (ql <= l && r <= qr) {
            apply(node, l, r, v);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) update(node << 1, l, m, ql, qr, v);
        if (qr > m) update(node << 1 | 1, m + 1, r, ql, qr, v);
        maintain(node);
    }  // 区间更新[ql,qr]

    void assign(int node, int l, int r, int p, const Info& v) {
        if (l == r) {
            info[node] = v;
            tag[node] = Tag();
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (p <= m)
            assign(node << 1, l, m, p, v);
        else
            assign(node << 1 | 1, m + 1, r, p, v);
        maintain(node);
    }  // 单点赋值

    Info query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return info[node];
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (qr <= m) return query(node << 1, l, m, ql, qr);
        if (ql > m) return query(node << 1 | 1, m + 1, r, ql, qr);
        return query(node << 1, l, m, ql, qr) + query(node << 1 | 1, m + 1, r, ql, qr);
    }  // 区间查找

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

    template <typename F>
    int find_last(int node, int l, int r, int ql, int qr, F&& check) {
        if (r < ql || l > qr || !check(info[node])) return -1;
        if (l == r) return l;
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, check);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, check);
    }

public:
    LazySegmentTree(int n, Info init_val = Info()) : LazySegmentTree(vector<Info>(n, init_val)) {}
    // 维护下标为[0,n-1],初始值为init_val的区间，或者数组a
    LazySegmentTree(const vector<Info>& a) : n(sz(a)), info(2 << bit_width((unsigned)sz(a) - 1)), tag(2 << bit_width((unsigned)sz(a) - 1)) {
        build(a, 1, 0, n - 1);
    }
    // 更新[ql,qr]为f
    void update(int ql, int qr, const Tag& v) { update(1, 0, n - 1, ql, qr, v); }
    // 单点赋值a[p]=v
    void assign(int p, const Info& v) { assign(1, 0, n - 1, p, v); }
    // 区间查询[ql,qr]
    Info query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }

    template <typename F>
    int find_first(int ql, int qr, F&& check) {
        return find_first(1, 0, n - 1, ql, qr, check);
    }  // 查询[ql,qr]中第一个满足条件的下标

    template <typename F>
    int find_last(int ql, int qr, F&& check) {
        return find_last(1, 0, n - 1, ql, qr, check);
    }  // 查询[ql,qr]中最后一个满足条件的下标

    int find_first(int ql, int qr, const Info& val) {
        return find_first(ql, qr, [&](const Info& x) { return !(x < val); });
    }

    int find_last(int ql, int qr, const Info& val) {
        return find_last(ql, qr, [&](const Info& x) { return !(x < val); });
    }
};
// 注：懒标记线段树无论做什么都需要pushdown
// 此时其它与线段树二分同
void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll l = 0, r = *max_element(all(a)), mid, ans = 0;
    auto check = [&](ll mid) -> bool {
        vi pre(n), suf(n);
        vector<Info> init(n, LLONG_MAX / 3);
        LazySegmentTree<Info, Tag> seg(init);
        int cnt = 0;
        rep(i, 0, n - 1) {
            seg.assign(i, Info(mid - a[i]));
            while (seg.query(0, n - 1).sum <= 0) {
                int tem2 = seg.find_last(0, i, [&](const Info& x) { return x.sum <= 0; });
                cnt++;
                seg.assign(tem2, Info(LLONG_MAX / 3));
                if (tem2 > 0) seg.update(0, tem2 - 1, Tag(-1));
            }
            pre[i] = cnt;
        }
        LazySegmentTree<Info, Tag> seg2(init);
        cnt = 0;
        frep(i, n - 1, 0) {
            seg2.assign(i, Info(mid - a[i]));
            while (seg2.query(0, n - 1).sum <= 0) {
                int tem2 = seg2.find_first(i, n - 1, [&](const Info& x) { return x.sum <= 0; });
                cnt++;
                seg2.assign(tem2, Info(LLONG_MAX / 3));
                if (tem2 < n - 1) seg2.update(tem2 + 1, n - 1, Tag(-1));
            }
            suf[i] = cnt;
        }
        int maxx = 0;
        rep(i, 0, n - 1) {
            if (a[i] >= mid) maxx = max(maxx, pre[i] + suf[i] - 1);
        }
        return maxx >= n - k;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    cout << ans << endl;
    return;
}