小花生

study & life record.

第十三届蓝桥杯软件赛省赛C++ A组

发表于 分类于 ，

第十三届蓝桥杯软件赛省赛C++ A组 题解。

以下代码均通过测试，可放心食用。

本期知识点：离线处理，数学期望（推公式），二分答案，树状数组，计算几何，欧拉筛，带权并查集。

填空题

1. 裁纸刀（5分）

一通计算发现结果需要裁纸的次数为 m * n + 3，输出 443 即可。

2. 灭鼠先锋（5分）

对于只有一行 OOOO 的情况，手推搜索一下，不难发现先手的一定会最终填满本行。

也就是说，第二行先手的必负，因此将第一行先填满者胜。

  • 情况一，乔走至 XOXO，那么乔一定先填满
  • 情况二，乔走至 XXXX，那么乔一定先填满
  • 情况三，乔走至 OXXO，那么乔一定先填满
  • 情况四，一定是蓝先填满

故这四场结果为 LLLV 。

3. 求和（10分）

意义不明的题，会等差数列和开 long long 即可，输出 204634714038436 。

程序题

4. 选数异或（10分）

考虑离线处理。用 map 维护 <数， 下标> ，遍历至 a[i] 时先看 map 中是否有与其异或为 x 的数，如果有，更新最大可取的左端点。处理所有询问右端点为 i 的区间。

时间复杂度 $O(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
#include<bits/stdc++.h>
#define int long long 
using namespace std;

void solve(){
    int n, m, x; cin >> n >> m >> x;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<pair<int, int>>>q(1e5 + 1);
    //                 <l, idx>
    vector<int>res(m);
    for(int i = 0; i < m; i++){
        int l, r; cin >> l >> r;
        q[r].emplace_back(l, i);
    }

    unordered_map<int, int>mp;
    //         <num, max_idx>

    int l_max = -1;
    for(int i = 1; i <= n; i++){
        int aim = a[i] ^ x;
        if(mp[aim]) l_max = max(l_max, mp[aim]);
        mp[a[i]] = i;

        for(auto &[l, idx] : q[i]){
            if(l_max != -1 && l_max >= l) res[idx] = 1;
        }
    }
    for(auto &i : res){
        if(i) cout << "yes" << '\n';
        else cout << "no" << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

5. 爬树的甲壳虫（15分）

对这个问题，本人用了近一面的草稿纸，构建递推公式 -> 配置系数并累加 -> 解出一个长相些许狰狞的结果。大概长这样：（$p_i$ 表示爬向高度 $i$ 时，掉下树根的概率）
$$
\frac{\sum\limits_{i=0}^{n-1}\prod\limits_{k=1}^{i}(1-p_k)}{1-\sum\limits_{i=0}^{n-1}p_{i+1}\prod\limits_{k=1}^{i}(1-p_k)}
$$
这个 …… 一言难尽 …… 但也能通过。

于是本着专业事要交给专业人的理念，我请教了一位数学系朋友，他轻描淡写地丢给了我下面这一行方程，然后轻松又极具技巧性地速通了这个问题（一整个降维打击）。我们来看看这个思路：（$p_i$ 表示爬向高度 $i$ 时，成功向上爬的概率，$x$ 表示目标期望）
$$
(x+1)(1-p_1)+…+(x+n)p_1p_2…p_{n-1}(1-p_n)+np_1p_2…p_n=x
$$
于是解得：
$$
x=\frac{\sum\limits_{i=0}^{n-1}\prod\limits_{k=1}^{i}p_i}{\prod\limits_{i=1}^{n}p_i}
$$
ok，叹为观止。那这一行公式是什么意思呢：

将 目标期望 x 做了如下拆解：

  • 首次爬升失败发生在 第1次 爬升，对应的期望爬升次数为 $(x+1)(1-p_1)$
  • 首次爬升失败发生在 第2次 爬升，对应的期望爬升次数为 $(x+2)p_1(1-p_2)$
  • ……
  • 首次爬升失败发生在 第n次 爬升，对应的期望爬升次数为 $(x+n)p_1p_2…p_{n-1}(1-p_n)$
  • 没有爬升失败，对应的期望爬升次数为 $np_1p_2…p_n$

公式左侧即为这些拆解项之和，右侧为目标期望 x。

利用公式求解即可，时间复杂度 $O(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
#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int mod = 998244353;

int qmi(int a, int k){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}

int inv(int x){
    return qmi(x, mod - 2);
}

struct modint{
    int v;
    modint(int x = 0) : v((x % mod + mod) % mod) {}

    modint operator+(const modint &o){
        return modint(v + o.v);
    }
    modint operator-(const modint &o){
        return modint(v - o.v);
    }
    modint operator*(const modint &o){
        return modint(v * o.v);
    }
    modint operator/(const modint &o){
        return modint(v * inv(o.v));
    }
};
using Z = modint;

void solve(){
    int n; cin >> n;
    vector<Z>p(n + 1);
    for(int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        p[i] = Z(y - x) / Z(y);
    }
    
    vector<Z>pi(n + 1);
    pi[0] = Z(1);
    for(int i = 1; i <= n; i++){
        pi[i] = pi[i - 1] * p[i];
    }
    
    cout << (accumulate(pi.begin(), pi.begin() + n, Z(0)) / pi[n]).v;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

6. 青蛙过河（15分）

本题重点在于发现以下性质：
$2x$ 只青蛙能过河，等价于，对于每个长度为 $y$ 的区间，石头高度之和大于等于 $2x$。

充分性：已知 $2x$ 只青蛙能过河，那么每个长度为 $y$ 的区间，都会被踩到至少 $2x$ 次，充分性得证。

必要性：已知每个长度为 $y$ 的区间，石头高度之和大于等于 $2x$，那么考虑，让 $2x$ 只青蛙同时起跳，第一次全部跳到 [1, y] 区间内，分两种情况讨论：

  • a[1] <= a[y + 1]，那么 1 位置可以全部跳到 y + 1位置。
  • a[1] > a[y + 1]，那么 将 1 位置的尽可能跳到 y + 1 位置后，剩下的可以全部跳到 [2, y] 位置内（因为 a[2] + a[3] + ... + a[y + 1] <= 2x）

换言之，这 $2x$ 只青蛙可以全部从 [1, y] 转移到 [2, y + 1] 内。这样，继续转移下去，青蛙可以全部到 [n - y, n - 1] 内，并全部跳到对岸，必要性得证。

得出该性质后，只需二分 y，并维护前缀和来 check 即可。时间复杂度 $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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, x; cin >> n >> x;
    vector<int>a(n), pre(n);
    for(int i = 1; i < n; i++){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    
    auto check = [&](int y){
        for(int i = 1; i + y - 1 < n; i++){
            if(pre[i + y - 1] - pre[i - 1] < 2 * x){
                return 0;
            }
        }
        return 1;
    };

    // 二分, 左侧不满足, 右侧满足
    int l = 0, r = n;
    while(l + 1 != r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    };

    cout << r;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

7. 最长不下降子序列（20分）

首先用 L[i], R[i] 分别维护以 a[i] 为 结尾 / 开头 的最长不下降子序列长度。
此过程可以用 二分/树状数组 完成，本 code 中以二分实现。

接下来遍历，改变哪 k 个元素。当我们改变 [r - k, r - 1] 范围内的元素时，整个序列被分为了三段：

[1, r - k - 1] 与 [r - k, r - 1] 与 [r, n]，我们现在需要得到整个新序列的最长不下降子序列长度。

令修改的所有元素等于 a[r]（这点的可行性在后面给出证明）。这样，我们要在 [1, r - k - 1] 找出满足 a[u] <= a[r] 的 u 中最大的 L[u]，这个操作用树状数组维护前缀最大值完成。那么新序列最长不下降子序列长度为 L[u] + k + R[r]。

Tip1：为什么将这 k 个元素修改为 a[r] 是可行的。
这里贪心地令这 k 个元素去配合 a[r] 为左端点的最长不下降子序列，因为即使让它去配合 a[r] 更后面的数 a[rr] 去形成最长不降序列，那他也不会有更优答案，因为他不会比 a[rr - k, rr - 1] 更优，那时 L[u] 的选择更广。

Tip2：如何用树状数组维护前缀最大值。

逐个加入 L[i] 时，在数轴上，下标为 a[i] 的位置放上数值 L[i]，这样，查询满足 a[u] <= a[r] 的 u 中最大的 L[u] 时，只需要在数轴上 <= a[r] 的部分查询最大值即可。可以用线段树来维护区间最大值，但既然只涉及到前缀最大值，可以用树状数组完成更为方便。

Tip3：这里 a[i] 的范围有限，只有 1e6，建立这么大的树状数组可行，但当数据更大时，需要先进行离散化处理。

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

class FenwickTree{
public:
    int n;
    vector<int>bit;
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void update(int p, int v){
        while(p <= n){
            bit[p] = max(bit[p], v);
            p += p & -p;
        }
    }

    int query(int p){
        int res = 0;
        while(p > 0){
            res = max(res, bit[p]);
            p -= p & -p;
        }
        return res;
    }
};

void solve(){
    int n, k; cin >> n >> k;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<int>L(n + 2), R(n + 2);
    // L[i] 表示以 a[i] 结尾的最长不降子序列长度
    // R[i] 表示以 a[i] 开头的最长不降子序列长度

    vector<int>tmp;
    for(int i = 1; i <= n; i++){
        int pos = upper_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin();
        if(pos == tmp.size()){
            tmp.emplace_back(a[i]);
        }
        else {
            tmp[pos] = a[i];
        }
        L[i] = pos + 1;
    }
    tmp.clear();
    for(int i = n; i >= 1; i--){
        int pos = upper_bound(tmp.begin(), tmp.end(), a[i], greater<>()) - tmp.begin();
        if(pos == tmp.size()) {
            tmp.emplace_back(a[i]);
        }
        else{
            tmp[pos] = a[i];	
        } 
        R[i] = pos + 1;
    }

    FenwickTree mx_bit(1e6);
    int res = k + R[k + 1];

    for(int r = k + 2; r <= n + 1; r++){
        mx_bit.update(a[r - k - 1], L[r - k - 1]);
        res = max(res, mx_bit.query(a[r]) + k + R[r]);
    }

    cout << res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

8. 扫描游戏（20分）

几何处理：

  • 先将整个图像按 $y=x$ 直线翻转，这样回到我们熟悉的从 $x$ 轴正半轴出发，逆时针旋转，这一步骤在读入时交换 $x$ 与 $y$ 的读入顺序即可完成。
  • 根据上一步操作，将每个点的角度定义为从 $x$ 轴正半轴逆时针旋转到原点与该点直线的角度。为方便比较角度大小且不引入 double 类型，记录每个点的如下性质：象限，在该象限内的 $x$, $y$ 坐标（即两者始终为正）。这样比较两者角度时，先比较象限值，再比较两者再各自象限内斜率 $y_1/x_1$ 与 $y_2/x_2$，也即比较 $y_1\times x_2$ 与 $y_2\times x_1$。

整体上采用如下思路：

  • 先将所有点按照距离原点的距离排序。

  • 将当前长度可以扫到的点加入一个小根堆（按角度从小到大）中。

  • 为了保证小根堆中的顺序就是我们吃到点的顺序，不难发现，只有当前这一圈还未扫到的角度范围内的点才能直接加入小根堆，而当前已经扫过的角度范围内的点，是不能加入小根堆的，他们只能在下一圈内被吃到。因此，额外维护一个数组，存入只有在下一圈内才可以被吃到的点。这样，每当扫完一圈，我们将数组内的元素全部重新压入小根堆中，这样就保证了小根堆中弹出元素的顺序就是我们吃点的顺序。

细节处理：

  • 如何保证同时吃掉的点的编号相同呢？只要让这次吃的点和上次吃的点比较角度大小，如果相同，那么将这个点的编号设置会和上一个相同即可。
  • 如何处理 $(0, 0)$ 这个毒瘤数据呢？直接将其改到 $(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
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
#include<bits/stdc++.h>
#define int long long
using namespace std;

class point{
public:
    int x, y, quadrant, value, idx;

    void setp(int x, int y, int v, int i){
        if(x == 0 && y == 0){
            this->x = 1, this->y = 0, quadrant = 1;
        }
        else if(x > 0 && y >= 0) {
            quadrant = 1;
            this->x = x;
            this->y = y;
        }
        else if(y > 0 && x <= 0){
            quadrant = 2;
            this->x = y;
            this->y = -x;			
        }
        else if(x < 0 && y <= 0){
            quadrant = 3;
            this->x = -x;
            this->y = -y;

        }
        else{
            quadrant = 4;
            this->x = -y;
            this->y = x;
        }
        value = v, idx = i;
    }

    int len() const {
        return x * x + y * y; 
    }

    // 用于小根堆排序
    bool operator > (const point &o) const {
        if(quadrant != o.quadrant) return quadrant > o.quadrant;
        return y * o.x > x * o.y;
    }

    // 用于比较角度
    bool operator >= (const point &o) const {
        if(quadrant != o.quadrant) return quadrant > o.quadrant;
        return y * o.x >= x * o.y;
    }

    // 用于判断角度相等
    bool operator == (const point &o) const {
        return quadrant == o.quadrant && y * o.x == x * o.y;
    }
};

void solve(){
     int n, l; cin >> n >> l;
     __int128 L = l;

     vector<point>p(n);

     for(int i = 0; i < n; i++){
         int x, y, v; cin >> y >> x >> v;
         p[i].setp(x, y, v, i);
     }

     sort(p.begin(), p.end(), [](const point &a, const point &b){
         return a.len() < b.len();
     });

     priority_queue<point, vector<point>, greater<point>>Q;

     int label = 0, run = 0;
     vector<int> res(n, -1);
     
     point last = {0, 0, -1, 0, 0};
    vector<point>next_round;

    while(run < n && p[run].len() <= L * L){
        Q.push(p[run++]);
    }

    while(!Q.empty() || !next_round.empty()){

        if(Q.empty() && !next_round.empty()){
            for(auto &u : next_round) Q.push(u);
            next_round.clear();
        }

        auto u = Q.top(); Q.pop();
        L += u.value;
        res[u.idx] = ++label;
        if(u == last) res[u.idx] = res[last.idx];
        last = u;

        while(run < n && p[run].len() <= L * L){
            if(p[run] >= u){
                Q.push(p[run++]);
            }
            else{
                next_round.push_back(p[run++]);
            }
        }
     }

     for(auto &i : res) cout << i << ' ';

}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

9. 数的拆分（25分）

首先考虑将 a 质因数分解，$a=p_1^{q_1}p_2^{q_2}\cdots p_n^{q_n}$，如果存在某个 $q_i = 1$ ，一定不满足题意。

假设现在所有 $q_i\ge 2$ ，那么分为以下三种情况：

  • $q_i\mod 3=0$，可以写作 $q_i=3k$
  • $q_i\mod 3=1$，可以写作 $q_i=4+3k$
  • $q_i\mod 3=2$，可以写作 $q_i=2+3k$

即，所有 $q_i$ 都可写作 $2m+3n$ 的形式，于是 $p_i^{q_i}=(p_i^m)^2(p_i^n)^3$，那么 $a$ 就可以表示成 $u^2v^3$ 的形式了。

综上，只要不存在某个 $q_i = 1$，$a$ 就是满足题设的。

为了在合适的时间复杂度内完成，做如下放缩：$1e18\ge a=u^2v^3\ge (\min(u, v))^5$

得到 $\min(u,v)\le 10^{\frac{18}{5}}<4000$，这样，把 $4000$ 以下的 $p_i$ 全部筛掉（即 $u$ 或 $v$ 至少有一者被筛干净），最后只能剩下平方根或立方根。

$T=1e5$，遍历 4000 个数去筛也不太合适，因此先做一个线性筛，得到 4000 内质数，再用这些质数去筛。

（这题还有个恶心的点，是 sqrt 和 cbrt 的精度问题，会导致偏差，需要自行处理）

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

class Euler{
public:
    vector<int>primes;
    vector<bool>comp;

    Euler(int n){
        comp.resize(n + 1);
        for(int i = 2; i <= n; i++){
            if(!comp[i]) primes.emplace_back(i);
            for(int j = 0; i * primes[j] <= n; j++){
                comp[i * primes[j]] = true;
                if(!(i % primes[j])) break;
            }
        }
    }
};

void solve(){
    Euler sieve(4000);

    auto check = [&](int n) -> bool{
        for(auto &u : sieve.primes){
            if(n % u == 0){
                int q = 0;
                while(n % u == 0){
                    n /= u, q++;
                }
                if(q == 1) return 0;
            }
        }
        int sq = sqrt(n), cb = cbrt(n);
        if((sq + 1) * (sq + 1) <= n) sq++;    	
        if((cb + 1) * (cb + 1) * (cb + 1) <= n) cb++;
        return sq * sq == n || cb * cb * cb == n;
    };

    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        if(check(n)) cout << "yes" << '\n';
        else cout << "no" << '\n';	
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

10. 推导部分和（25分）

可以先去做这题：AT_ABC238_E Range Sums - 洛谷。

本题与上题的唯一区别就是，我们需要在并查集上维护每两个前缀和的差。

记 $S$ 为前缀和数组，那么每给出一个 [l, r] 的和为 s ，等价于给出 $S_r-S_{l-1}=s$。

这样，我们建立带权并查集，每个结点维护到达根节点的距离（$dis_i=S_根-S_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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, m, q; cin >> n >> m >> q;
    
    vector<int>p(n + 1), dis(n + 1);
    for(int i = 1; i <= n; i++) p[i] = i;
    function<int(int)>find = [&](int x){
        if(x == p[x]) return x;
        int px = p[x];
        p[x] = find(p[x]);
        dis[x] += dis[px];
        return p[x];
    };
    auto merge = [&](int x, int y, int w){
        int fx = find(x), fy = find(y);
        if(fx == fy) return;
        p[fx] = fy;
        dis[fx] = dis[y] - dis[x] + w;
    };

    for(int i = 1; i <= m; i++){
        int l, r, s; cin >> l >> r >> s;
        merge(l - 1, r, s);
    }
    
    while(q--){
        int l, r; cin >> l >> r;
        if(find(l - 1) != find(r)) cout << "UNKNOWN" << '\n';
        else cout << dis[l - 1] - dis[r] << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}