小花生

study & life record.

第十六届蓝桥杯省赛C++ A组

发表于 分类于 ，

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

初次参加，80/100 分左右。

H 题没拿下，一是先前没接触过基环树（虽然问题并不出在这里，想到了用 dsu + dfs 找环），然后是赛时对最优情况没有找全，没有想清楚 quq，再接再厉叭。

bilibili 2025 蓝桥杯省赛 c++ A组 解析。

A. 寻找质数

会判质数即可，签到，答案 17609。

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

struct Euler{
    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(1e6);
    cout << sieve.primes[2024] << '\n';
    
    // 逐个判
    vector<int> primes;
    for(int x = 2; primes.size() < 2025; x++){
        int ok = 1;
        for(int i = 2; i * i <= x; i++){
            if(x % i == 0){
                ok = 0;
                break;
            }	
        }
        if(ok) primes.emplace_back(x);
    }
    cout << primes[2024] << '\n';
}

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

// 17609

B. 黑白棋

很典型的暴力题，数一数空位的数量，有 26 个，可以直接二进制枚举了。

就是码量比较大，每种情况需要判断三个条件是否都满足，都满足的输出即可。

答案 101001010011101100010110011001100110。

（b站上有 up 主做了纯推理完成的视频，大家也可以去看看）

（没写 dfs 是因为怕 debug，写起来不方便）

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

void solve(){
    vector<vector<int>> a = {
        {  1,  0, -1,  0, -1, -1 },
        { -1, -1, -1,  0, -1, -1 },
        { -1, -1, -1,  1,  0,  0 },
        { -1, -1, -1, -1, -1, -1 },
        { -1, -1,  1, -1, -1,  1 },
        { -1,  0, -1, -1,  1, -1 },
    };
    
    vector<pair<int, int>> p = {
        {0, 2}, {0, 4}, {0, 5},
        {1, 0}, {1, 1}, {1, 2}, {1, 4}, {1, 5},
        {2, 0}, {2, 1}, {2, 2},
        {3, 0}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5},
        {4, 0}, {4, 1}, {4, 3}, {4, 4},
        {5, 0}, {5, 2}, {5, 3}, {5, 5}
    };
    
    
    for(int i = 0; i < 1 << 25; i++){
        for(int k = 0; k < 25; k++){
            a[p[k].first][p[k].second] = i >> k & 1;
        }
        
        int ok = 1;
        
        for(int i = 0; i < 6; i++){
            int cnt = 0;
            for(int j = 0; j < 6; j++){
                cnt += a[i][j];
            }
            if(cnt != 3) ok = 0;
        }
        
        if(!ok) continue;
        
        for(int j = 0; j < 6; j++){
            int cnt = 0;
            for(int i = 0; i < 6; i++){
                cnt += a[i][j];
            }
            if(cnt != 3) ok = 0;
        }
        
        if(!ok) continue;

        for(int i = 0; i < 6; i++){
            for(int j = 0; j <= 3; j++){
                if(a[i][j] == a[i][j + 1] && a[i][j] == a[i][j + 2]){
                    ok = 0;
                }
            }
        }
        
        if(!ok) continue;
        
        for(int j = 0; j < 6; j++){
            for(int i = 0; i <= 3; i++){
                if(a[i][j] == a[i + 1][j] && a[i][j] == a[i + 2][j]){
                    ok = 0;
                }
            }
        }	
        
        if(!ok) continue;
        
        for(int i = 0; i < 6; i++){
            for(int j = i + 1; j < 6; j++){
                int same = 1;
                for(int k = 0; k < 6; k++){
                    if(a[i][k] != a[j][k]) same = 0;
                }
                if(same) ok = 0;
            }
        }
        
        if(!ok) continue;
        
        for(int i = 0; i < 6; i++){
            for(int j = i + 1; j < 6; j++){
                int same = 1;
                for(int k = 0; k < 6; k++){
                    if(a[k][i] != a[k][j]) same = 0;
                }
                if(same) ok = 0;
            }
        }
        
        if(!ok) continue;
        
        for(auto &v : a){
            for(auto &i : v){
                cout << i;
            }
        }
    }

}

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

// 101001010011101100010110011001100110

C. 抽奖

模拟题，照着题意实现即可，需要注意的是，判断得分的时候一定要从高分往低分判，

一次抽奖最多只能获得一次积分，如果同时命中多个奖项，以积分最大的那个奖项为准。

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;

int get_val(int x, int y, int z){
    vector<int> u = {x, y, z};
    if(u[0] + 1 == u[1] && u[1] + 1 == u[2]) return 200;
    sort(u.begin(), u.end());
    if(u[0] == u[2]) return 200;
    if(u[0] == u[1] || u[1] == u[2]) return 100;
    if(u[0] + 1 == u[1] && u[1] + 1 == u[2]) return 100;
    return 0;
}

void solve(){
    int n; cin >> n;
    vector<int> a(n), b(n), c(n);
    for(auto &i : a) cin >> i;
    for(auto &i : b) cin >> i;
    for(auto &i : c) cin >> i;
    
    int m; cin >> m;
    int res = 0;
    int x = 0, y = 0, z = 0;
    while(m--){
        int u, v, w; cin >> u >> v >> w;
        x = (x + u) % n, y = (y + v) % n, z = (z + w) % n;
        res += get_val(a[x], b[y], c[z]); 
    }
    cout << res << '\n';
}

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

D. 红黑树

不难发现，一个点的颜色，与左子树的相同，与右子树的相反，考虑先转成 0-index，然后从二进制角度做。

每次往右走，就是给二进制末尾多添一个 1，往左走就是多添一个 0。

所以二进制里有几个 1，就是往右走了几次，就是颜色翻转了几次。

如果翻转的次数是偶数，那么与根节点颜色相同为 RED，否则为 BLACK。

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

void solve(){
    int m; cin >> m;
    
    while(m--){
        int n, k; cin >> n >> k;
        n--, k--;
        
        int cg = 0;
        for(int i = n; i >= 0; i--){
            if(k & 1) cg++;
            k >>= 1;
        }
        
        if(cg & 1) cout << "BLACK" << '\n';
        else cout << "RED" << '\n';
    }

}

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

E. 黑客

注意这个数据，读入第一行的 all，如果 all == 1 特判掉，返回 0，以免 nm 相乘为 -1，导致越界 RE。

接下来，考虑对于一组特定的 n, m，有多少种矩阵的种类。

令剩下的数个数分别为 cnt[i]，种类数就是 $\dfrac{(nm)!}{\prod_i(cnt[i])!}$.

为了对每组 (n, m)，能快速得到这个结果，先保存所有元素的 $\prod_i(cnt[i])!$ ，然后先除以总个数，再乘上实际个数即可。

然后就是怎么找到（n，m）的所有组合，直接遍历数组找 cnt 有没有记录过 nm / 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int mod = 1e9 + 7;
constexpr int N = 5e5 + 5;

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

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

void solve(){
    int all; cin >> all;
    vector<int> a(all);
    for(auto &i : a) cin >> i;

    // 特判
    if(all == 1) {
        cout << 0 << '\n';
        return;
    }
    
    // 阶乘预处理
    vector<int> fact(all + 1);
    fact[0] = 1;
    for(int i = 1; i <= all; i++){
        fact[i] = fact[i - 1] * i % mod;
    }

    // 计算 n * m
    int mul = all - 2;
    vector<int> cnt(N);
    for(auto &i : a){
        cnt[i] ++;
    }

    // 保存所有元素得到的 prod
    int prod = 1;
    for(auto &i : cnt){
        prod = prod * fact[i] % mod;
    }
    
    // 标记已经记录过的组合
    unordered_map<int, unordered_map<int, int>> seen;
    
    int res = 0;
    for(auto &i : a){
        if(mul % i == 0 && cnt[mul / i]){
            if(seen[i][mul / i]) continue;
            seen[i][mul / i] = seen[mul / i][i] = 1;

            int newprod;
            int dd = 1;
            // 分类，n m 是否相同，计算 newprod
            if(i == mul / i){
                newprod = prod * inv(fact[cnt[i]]) % mod * (fact[cnt[i] - 2]) % mod;
            }
            else{
                dd = 2;
                newprod = prod * inv(fact[cnt[i]]) % mod * inv(fact[cnt[mul / i]]) % mod 
                            * (fact[cnt[i] - 1]) % mod * (fact[cnt[mul / i] - 1]) % mod;
            }
            // 更新答案
            res += dd * fact[mul] * inv(newprod) % mod;
            res %= mod;
        }
    }
    cout << res << '\n';
}

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

F. 好串的数目

Dp，先将题目中的好串分为两类：1. 连续非递减子串 2. 两个连续非递减子串拼成的串。

记 $dp[0][i],dp[1][i]$ 分别表示以第 i 个数结尾的 1/2 类子串数目。

1 类子串的转移：

  • 如果该数和前一个数连续（等于或大1），那么以该数结尾的 1 类好串的数目为前一个结尾的 1 类好串数目 +1
  • 如果和前一个数不连续，那么以该数结尾的 1 类好串数目为 1 （它本身）

2 类子串的转移：

  • 如果该数和前一个数连续（等于或大1），那么以该数结尾的 2 类好串的数目与以前一个数结尾的 2 类好串的数目相同。
  • 如果和前一个数不连续，那么以该数结尾的 2 类好串数目 与 以前一个数结尾的 1 类好串的数目相同

最终结果为：以每个点结尾的 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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    string s; cin >> s;
    
    vector<vector<int>> dp(2, vector<int>(s.size()));
    
    dp[0][0] = 1;
    for(int i = 1; i < s.size(); i++){
        if(s[i] == s[i - 1] || s[i] == s[i - 1] + 1){
            dp[0][i] = dp[0][i - 1] + 1;
            dp[1][i] = dp[1][i - 1];
        }
        else{
            dp[0][i] = 1;
            dp[1][i] = dp[0][i - 1];
        }
    }	
    
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        res += dp[0][i] + dp[1][i];
    }
    cout << res << '\n';
}

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

G. 地雷阵

先看一个圆。它在 $[0,\pi/2]$ 上覆盖的区间为 $[\alpha-\beta,\alpha+\beta]$ 。

其中 $\tan \alpha = \dfrac{y}{x}$，$\tan \beta=\dfrac{r}{\sqrt{x^2+y^2-r^2}}$ 。

处理出所有的区间后，计算未被覆盖的区间占 $[0,\pi/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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<double, double> PDD;

constexpr double pi = 3.1415926535;

void solve(){
    int n; cin >> n;
    vector<PDD> seg(n);
    
    for(int i = 0; i < n; i++){
        int x, y, r; cin >> x >> y >> r;
    
        double alpha = atan2(y, x);	
        double beta = atan2(r, sqrtl(x * x + y * y - r * r));
    
        seg[i] = {alpha - beta, alpha + beta};
    }
    
    sort(seg.begin(), seg.end());
    
    double res = seg[0].first, p = seg[0].second;
    for(int i = 1; i < n; i++){
        if(seg[i].first < p) p = max(p, seg[i].second);
        else{
            res += seg[i].first - p;
            p = seg[i].second;
        }
    }
    res += pi / 2 - p;
    
    cout << fixed << setprecision(3) << res * 2 / pi << '\n';
}

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

H. 扫地机器人

n 个点 n 条边的无重边无自环的连通无向图 $\to$ 基环树

（也就是在树上多加了一条边，使其产生了一个环）

第一步是找出这个环，可以考虑 dsu + dfs，在依次加入边的过程中，判断两个端点是否在一个集合中，如果是，说明这两个点都在环上，分别记为 U，V。

然后从 U 开始 dfs，搜到 V 的那条路径就是这个基环树的环。

用 cir[i] 表示环上的第 i 个点。

考虑最长的路径会在哪些情况中产生：

  • 路径不经过环

  • 路径经过环的若干点，进入两个不同的子树

  • 路径经过环的所有点，进入环上一个点的两棵不同子树

其中，1 3 种情况可以一起处理掉，树形 dp 解决从该点向两颗（最大）子树延申得到的路径的最大点权和。

然后第 2 种情况是比较复杂的，首先解决环的问题，我们要在环上所有可取区间中择优选择，考虑将环倍增（这是处理环的常见手段了），这样可以比较容易的得到所有可取区间。

用 $q[i]$ 表示从 $cir[i]$ 进入子树得到的最大点权和，用 $w[i]$ 表示 $cir[i]$ 的点权。

那么就是选取 $i,j\ (j-i+1<=C)$，使得 $q[i]+q[j]+\sum_{i<k<j}w[k]$ 最大。

( C 表示环上点的个数 )

先做个前缀和 $pre[i]=\sum_{k=0}^{i-1}w[k]$。
$$
q[i]+q[j]+\sum_{i<k<j}w[k]=q[i]+q[j]+(pre[j]-pre[i + 1])
$$
令 $u[i]=q[i]-pre[i + 1], \ v[i]=q[j]+pre[j]$，即求 $u[i]+v[j]$ 最大值 $(j-C+1\le i\le j-1)$

这个做法就很多了，可以用 ST 表维护 $u$ 上的区间最大值，然后遍历右端点 $j$，这样统计出最大值，时间复杂度瓶颈在 ST 表的预处理 $O(C\log C)$。（也可以用单调队列实现这个最大值的查询）

将三种情况的答案取最大值即可。

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

class ST{
    vector<vector<int>>st;
    vector<int>lg;
public:
    ST(vector<int>v){
        int n = v.size();
        int m = log2(n) + 1;

        lg.resize(n + 1);
        for(int i = 2; i <= n; i++){
            lg[i] = lg[i >> 1] + 1;
        }

        st.resize(n, vector<int>(m));
        for(int i = 0; i < n; i++){
            st[i][0] = v[i];
        }
        for(int j = 1; j < m; j++){
            for(int i = 0; i + (1 << j) - 1 < n; i++){
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query(int l, int r){ 
        int k = lg[r - l + 1];
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

void solve(){
    int n; cin >> n;

    if(n == 1 || n == 2) while(1);

    vector<int> t(n);
    for(auto &i : t) cin >> i;

    vector<vector<int>> adj(n);
    
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x){
        return x == p[x] ? x : p[x] = find(p[x]);
    };

    int U, V;
    for(int i = 0; i < n; i++){
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);

        int fu = find(u), fv = find(v);
        if(fu == fv){
            U = u, V = v;
        } else{
            p[fu] = fv;
        }
    }

    vector<int> vis(n);
    vis[V] = 1;
    vector<int> cir;
    function<void(int, int)> dfs = [&](int u, int fa){
        if(u == V) {
            cir.emplace_back(u);
            return;
        }
        for(auto &v : adj[u]){
            if(v == fa) continue;
            dfs(v, u);
            if(vis[v]) {
                vis[u] = 1;
                cir.emplace_back(u);
            }
        }
    };
    dfs(U, V);

    int res = 0;
    // case 1, 3:
    {
        int sum_cir = 0;
        for(auto &i : cir){
            sum_cir += t[i];
        }

        function<int(int, int)> dfs = [&](int u, int fa){
            int max1 = 0, max2 = 0;
            for(auto &v : adj[u]){
                if(v == fa || vis[v]) continue;
                int d = dfs(v, u);
                if(d > max1){
                    max2 = max1;
                    max1 = d;
                }
                else if(d > max2){
                    max2 = d;
                }
            }
            // 在环上，对应 case 3
            if(vis[u]){
                res = max(res, max1 + max2 + sum_cir);
            }
            // 不在环上，对应 case 1 
            else{
                res = max(res, max1 + max2 + t[u]);
            }
            return max1 + t[u];
        };

        for(int i = 0; i < n; i++){
            if(!vis[i]) continue;
            dfs(i, -1);
        }
    }

    // case 2:
    {
        auto sub = t;
        function<void(int, int)> dfs = [&](int u, int fa){
        	int Mx = 0;
        	for(auto &v : adj[u]){
        		if(v == fa || vis[v]) continue;
        		dfs(v, u);
        		Mx = max(Mx, sub[v]);
        	}
        	sub[u] += Mx;
        };

        for(int i = 0; i < n; i++){
        	if(vis[i]) dfs(i, -1);
        }

        int C = cir.size();
        vector<int> val(2 * C);
        for(int i = 0; i < C; i++){
        	val[i] = val[i + C] = sub[cir[i]];
        }
        vector<int> w(2 * C);
        for(int i = 0; i < C; i++){
        	w[i] = w[i + C] = t[cir[i]];
        }
        vector<int> pre(2 * C + 1);
        for(int i = 1; i <= 2 * C; i++){
        	pre[i] = pre[i - 1] + w[i - 1];
        }

        vector<int> u(2 * C), v(2 * C);
        for(int i = 0; i < 2 * C; i++){
        	u[i] = val[i] - pre[i + 1];
        	v[i] = val[i] + pre[i];
        }

        ST st(u);

        for(int r = C; r < 2 * C; r++){
        	res = max(res, st.query(r - C + 1, r - 1) + v[r]);
        }
    }
       
    cout << res << '\n';
}

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