小花生

study & life record.

第十五届蓝桥杯国赛C++ B组

发表于 分类于 ，

第十五届蓝桥杯软件赛国赛C++ B组 题解。

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

void solve(){
    string s = "kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th";
    
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        for(int j = 8; j <= 16 && i + j - 1 < s.size(); j++){
            string tmp = s.substr(i, j);
            int dig = 0;
            int chr = 0;
            for(auto &i : tmp){
                dig += isdigit(i);
                chr += ('a' <= i && i <= 'z') || ('A' <= i && i <= 'Z');
            }
            res += (dig && dig + chr != j);
        }
    }

    cout << res;
}

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

B. 蚂蚁开会

由于题目提到：不保证任意两条线段之间交点有限，所以求交点是肯定不可行的。

观察数据范围，不妨直接标记每条线段所经过的整点，在所有被标记过的整点中寻找被标记次数大于 1 的即可。

标记线段经过的整点时，可以将线段分为 “两个方向长度的gcd” 个段，这样每个段的两个端点都是整点，且只有这些端点是整点。

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; cin >> n;
    
    unordered_map<int, unordered_map<int, int>> mp;

    for(int i = 0; i < n; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int g = gcd(c - a, d - b);

        int x = a, y = b;
        int dx = (c - a) / g, dy = (d - b) / g;

        mp[x][y] ++;
        do{
            x += dx, y += dy;
            mp[x][y] ++;
        } while(!(x == c && y == d));
    }

    int res = 0;
    for(auto &[_, l] : mp){
        for(auto &[_, cnt] : l){
            res += cnt > 1;
        }
    }
    cout << res << '\n';
}

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

C. 选数概率

$$
\frac{ab}{C(a+b+c,2)}=\frac{517}{2091},\frac{bc}{C(a+b+c,2)}=\frac{2632}{10455},\frac{ab}{C(a+b+c,2)}=\frac{308}{2091}
$$

于是不难得到：
$$
ab:bc:ab=517\times 5:2632:308\times5
$$
进而不难得到：
$$
a:b:c=ab\times ac:ab\times bc:ac\times bc=55:94:56
$$
先要求 $a+b+c$ 最小值，直接令 $a=55,b=94,c=56$ 即可。

（这里可以验证一下是否满足给出的等式，同时不难发现，由于 $ab$,$C(a+b+c,2)$ 都是二次的，因此其值只与 $a,b,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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int i = 517 * 5, j = 2632, k = 308 * 5;

    int a = i * k, b = i * j, c = j * k;
    int g = gcd(gcd(a, b), c);
    a /= g, b /= g, c /= g;

    if(2091 * a * b != 517 * (a + b + c) * (a + b + c - 1) / 2){
        cout << "No" << '\n';
        return;
    }
    cout << a << ',' << b << ',' << c << '\n';
}

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

D. 立定跳远

增加检查点 $=$ 在检查点间多跳跃一次

使用爆发技能 $=$ 在检查点间多跳跃一次

所以其实爆发技能和一个检查点的效果是等价的，也就是说，相当于现在我们可以多跳跃 $m+1$ 次。

接下来二分单次跳跃的距离 $L$，看我们需要多跳跃的次数是否在 $m+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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, m; cin >> n >> m;
    m++;

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

    auto check = [&](int x){
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            if(a[i] == a[i - 1]) continue;
            cnt += (a[i] - a[i - 1] + x - 1) / x - 1;
        }
        return cnt <= m;
    };

    int l = 0, r = a[n] - a[0];
    while(l + 1 != r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }

    cout << r << '\n';
}

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

E. 最小字符串

贪心插入显然是最优的。

我们可以先将插入串做一个排序，然后用两个指针分别指向被插入串和插入串。

只要这里选择插入串中的字符是更优的，就选择插入串，否则选择原串。

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

void solve(){
    int n, m; cin >> n >> m;
    string a, b; cin >> a >> b;

    sort(b.begin(), b.end());

    for(int i = 0, j = 0; i < n; i++){
        while(j != m && b[j] < a[i]){
            cout << b[j++];
        }
        cout << a[i];
        if(i == n - 1){
            while(j != m){
                cout << b[j++];
            }
        }
    }

}

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

F. 数位翻转

由于数据范围比较小，可以直接考虑处理出翻转后的序列 $b$，然后进行一个 $O(n^2)$ 的 $dp$ 来选择哪些段进行翻转。

处理翻转就先得到二进制 01 串然后反着倒回十进制就好了。

$dp[i][j][0/1]$：表示前 i 个字符，至此翻转过 j 个段，第 i 个字符（不翻转/翻转）。

转移就很简单了：
$$
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i]\
dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + b[i]
$$
最后在 $dp[n][j][0/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
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int inf = 1e18;

void solve(){
    int n, m; cin >> n >> m;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++){
        int x; cin >> x; a[i] = x;
        
        string s;
        while(x){
            s += (x & 1) + '0';
            x >>= 1;
        }
        for(auto &c : s){
            b[i] <<= 1;
            b[i] += c - '0';
        }
    }

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, -inf)));
    dp[0][0][0] = 0;
    
    for(int i = 1; i <= n; i++){
        dp[i][0][0] = dp[i - 1][0][0] + a[i];
        for(int j = 1; j <= m; j++){
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i];
            dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + b[i];
        }
    }

    int res = 0;
    for(int j = 0; j <= m; j++){
        res = max(res, dp[n][j][0]);
        res = max(res, dp[n][j][1]);
    }

    cout << res << '\n';
}

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

G. 数星星

一个 $|V_G|$ 的星星，就是在中间的点选择了它的 $|V_G|-1$ 的邻点。

那么其实图中有用的信息就只有度数，我们把每个点的度数都记录下来。

那么最后的答案就是：
$$
\sum_u\sum_{k=L}^R C_{d[u]}^{k-1}
$$
这个直接计算显然复杂度大了，不妨考虑一点记忆化，处理过 $d[u]$ 的值，就记录下 $\sum_{k=L}^R C_{d[u]}^{k-1}$ 的值，避免重复计算，而不同的 $d[u]$ 值肯定是不多的，这样处理就能有效控制时间复杂度了。

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

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

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);
}

vector<int> fact(N);
void init(){
    fact[0] = 1;
    for(int i = 1; i < N; i++){
        fact[i] = fact[i - 1] * i % mod;
    }
}

int C(int a, int b){
    if(a < b) return 0;
    return fact[a] * inv(fact[b] * fact[a - b] % mod) % mod;
}

void solve(){
    int n; cin >> n;
    vector<int> d(n);

    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        u--, v--;
        d[u] ++, d[v] ++;
    }

    int L, R; cin >> L >> R;

    int res = 0;
    unordered_map<int, int> mp;
    for(int i = 0; i < n; i++){
        if(mp.count(d[i])){
            res += mp[d[i]];
            continue;
        }
        int sum = 0;
        for(int j = L; j <= R; j++){
            sum += C(d[i], j - 1);
            sum %= mod;
        }
        res += (mp[d[i]] = sum);
           res %= mod;
    }
    cout << res << '\n';
}

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

H. 套手镯

我们可以先考虑一维的情况：

给出一堆区间，找到一个框框 $[L,R]$ 使得完全包含的区间最多。

将区间按右端点排列，然后用一个优先队列保存左端点，每次加入一个新区间，将左端点不能满足的全部弹出即可。这个过程中，优先队列大小的最大值就是框框能包含的最多区间数了。

那么对于这个二维的情况，我们一维一维的处理就好了，先在 $y$ 轴上按上述手段处理一遍，然后提取出所有在当前无限长框框（$y=down,y=up$）中的圆，再在 $x$ 轴上处理一遍，就能求出一次最多能包含的圆的个数了。

注意最后要把 $w,h$ 反过来再做一遍。

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

struct cir{
    int x, y, r;

    bool operator> (const cir &o) const{
        return y - r > o.y - o.r;
    }
};

struct seg{
    int l, r;
    seg(int l = 0, int r = 0) : l(l), r(r) {}
    bool operator> (const seg &o) const{
        return l > o.l;
    }
};

void solve(){
    int n, w, h; cin >> n >> w >> h;
    vector<cir> p(n);
    for(int i = 0; i < n; i++){
        int x, y, r; cin >> x >> y >> r;
        p[i] = {x, y, r};
    }

    sort(p.begin(), p.end(), [](const cir &a, const cir &b){
        return a.y + a.r < b.y + b.r;
    });

    int res = 0;

    auto dodo = [&]{
        priority_queue<cir, vector<cir>, greater<cir>> Q; 
        for(int i = 0; i < n; i++){
        	Q.push(p[i]);

        	auto u = Q.top();
        	while(p[i].y + p[i].r - h > u.y - u.r){
        		Q.pop();
        		if(Q.empty()) break;
        		u = Q.top();
        	}

        	if(Q.empty()) continue;

        	auto tmp = Q;
        	vector<seg> segs;
        	while(!tmp.empty()){
        		auto v = tmp.top();
        		tmp.pop();
        		segs.emplace_back(v.x - v.r, v.x + v.r);
        	}

        	sort(segs.begin(), segs.end(), [](const seg &a, const seg &b){
        		return a.r < b.r;
        	});

        	priority_queue<seg, vector<seg>, greater<seg>> S;
        	for(int j = 0; j < segs.size(); j++){
        		S.push(segs[j]);

        		auto s = S.top();
        		while(segs[j].r - w > s.l){
        			S.pop();
        			if(S.empty()) break;
        			s = S.top();
        		}

        		int sz = S.size();
        		res = max(res, sz);
        	}
        }
    };

    dodo();
    swap(w, h);
    dodo();

    cout << res << '\n';
}

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

I. 跳石头

不难发现：
$$
S_x=c_x\cup S_{x+c_x}\cup S_{2x}
$$
因此每一个集合所包含的权值都能由后面的集合转移而来，我们逆序处理一遍，就能得到所有集合了。

对于这种转移，用 $bitset$ 可以非常高效的实现（或运算）。

统计集合的最大元素个数即可。

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 n; cin >> n;
    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> c[i];
    }

    int res = 0;
    vector<bitset<40001>> uni(n + 1);
    for(int i = n; i >= 1; i--){
        uni[i][c[i]] = 1;
        if(i + c[i] <= n) uni[i] |= uni[i + c[i]];
        if(i + i <= n) uni[i] |= uni[i + i];
        res = max(res, (int)uni[i].count());
    }

    cout << res << '\n';
}

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

J. 最长回文前后缀

第一步，找出当前就存在的公共前后缀，统计个数后删去。

对于剩下的部分，我们一定是删去某个前缀或某个后缀（否则就没有回文前后缀了），然后考虑得到最长的回文前后缀。

这一部分可以用 KMP 实现：

先考虑删去后缀，对一个字符串 $s = c_1c_2\cdots c_n$，我们希望找到一个 $c_1c_2…=c_rc_{r-1}…$ 的最长回文前后缀。我们记 $t$ 是 $s$ 的逆序。

做拼接：str=s+#+t，这样，我们只需要利用 KMP 求出 str 中的 “最长相同前后缀” 即可，实现是 $O(n)$ 的。

再详细一些：str = c_1c_2...c_n#c_nc_{n-1}...c_1，在 $str$ 中 字符 # 后的最长相同前后缀，就等价于 $s$ 的前缀 与 删去一段后缀后的回文后缀。

同样的，考虑删除前缀的话，就做拼接 str=t+#+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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    string s; cin >> s;
    int cnt = 0;
    
    {
        int i = 0, j = s.size() - 1;
        while(s[i] == s[j]){
            i++, j--, cnt++;
        }
        s = s.substr(i, s.size() - 2 * cnt);
    }

    auto get_f = [](string s){
        int n = s.size();
        vector<int> f(n + 1);
        for(int i = 1, j = 0; i < n; i++){
            while(j && s[i] != s[j]){
                j = f[j];
            }
            j += (s[i] == s[j]);
            f[i + 1] = j;
        }
        return f;
    };

    int res = 0;

    auto dodo = [&](string a, string b){
        auto f = get_f(a + "#" + b);
        for(int i = a.size() + 2; i < f.size(); i++){
            if(i + f[i] < f.size()) res = max(res, f[i]);
        }
    };

    string t = s;
    reverse(t.begin(), t.end());
    dodo(s, t);
    dodo(t, s);

    cout << cnt + res << '\n';
}

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