2024 CCPC郑州邀请赛

F. 优秀字符串（模拟）

题意

​     如果给定字符串$s$的长度为5，第三个字符与第五个字符相同且前四个字符互不相同，认为此字符串为”优秀字符串”，求“优秀字符串”的数量.

思路

​     签到题，直接模拟即可.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, ans = 0;cin >> n;
    set<char> st;
    for (int i = 1; i <= n;i++){
        string str;
        cin >> str;
        if(str.size()==5&&str[2]==str[4]){
            st.insert(str[0]),st.insert(str[1]);
            st.insert(str[2]),st.insert(str[3]);
            if(st.size()==4)
                ans++;
        }
        st.clear();
    }
    cout << ans << endl;
    return 0;
}

J. 排列与合数 (暴力枚举)

时间复杂度：$O(T \cdot 5! \cdot \sqrt n)$

题意

​     有$t$组数据，每组给定一个恰好 $5$ 位且各个数位均不相同的十进制正整数$n$。可以任意排列该数字，保证数字没有前导零。请问是否存在一个方案使得重新排列的整数为 合数，若存在，则输出任意一个排列得到的合数，反之，则输出“-1”.

数据范围

  • $1 \le T \le 10^5$
  • $10^4 \le n < 10^5$

思路

​     判断整数$x$是否为合数，只需满足$x$不是质数且$x \ne 1$ ，但本题保证各个数位均不相同，故只需判断是否为质数即可.

​     从暴力枚举的角度，$t$组数据，每组数据进行全排列枚举$O(5!)$，并对每个数进行朴素判质数$O(\sqrt n)$操作，那么复杂度为 $\colorbox{Yellow}{O(120Tn)}$，最坏情况的数值为$10^5 \times 120 \times \sqrt {10^5} \ge 10^9$ ，考虑 剪枝优化，当排列的整数为偶数时，也就是最后一位是偶数，那么一定是满足条件的合数，直接退出循环并输出 .

​ Note: 使用埃氏筛或者欧拉筛预处理可以将复杂度降为$O(120T)$ ! 全排列除了使用深搜回溯的方式，也可以使用函数$next\underline{~} \;permutation()$ 加以实现，非常实用

Code:

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 endl '\n' 
using i64 = long long;
using namespace std;
char s[10];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    auto isPrime = [&](int x) -> bool { //判断质数
        if(x==1)
            return 0;
        for (int i = 2; i <= x / i;i++)
            if(x%i==0)
                return 0;
        return 1;
    };
    while(t--){
        cin >> s + 1;
        vector<int> p(6);
        iota(p.begin(), p.end(), 0);
        bool flag = 0;
        do{
            if (s[p[1]] == '0') //不含前导零
                continue;
            int n = (s[p[1]] - '0') * 10000 + (s[p[2]] - '0') * 1000 + (s[p[3]] - '0') * 100 + (s[p[4]] - '0') * 10 + (s[p[5]] - '0');
            if (!isPrime(n) && n != 1){
                cout << n << endl;
                flag = 1;
                break;
            }
        } while (next_permutation(p.begin() + 1, p.end())); //全排列函数
        if(!flag){
            cout << "-1" << endl;
        }
    }
    return 0;
}

B. 扫雷1 (贪心)

时间复杂度：$O(n \log n)$

题意

​     进行$n$轮扫雷，已知每轮扫雷开始之前均会获得1枚金币，且后续不会被回收。在第$i$轮扫雷中，可以花费$c_i$枚金币购买一个地雷检测器，购买数量不限。请问在这$n$轮结束后最多能购买的地雷检测器的数量？

数据范围

  • $1 \le n \le 2 \times 10^5$
  • $1 \le c_i \le 10^9$

思路

​     设当前拥有的金币数为$cnt$,显然，每次的购买数量为$\dfrac{cnt}{c_i}$，为使得购买数量最大化，显然， 贪心地选择$c_i$最靠后的最小值一定是最优的，因为前面轮数积累的金币数固定，且$c_i$的值较小，故购买数量一定更大。

​     不难想到，依次找到最远的最小值、次小值、…… 、较大值，类似于单调栈的操作，需要维护最值的最远下标，当找到当前的最值后统计数量并依次找次大值，保证该次大值的下标高于最大值，遍历即可。该维护最值的下标过程和遍历操作可使用优先队列或者map实现。

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
    vector<int> c(n + 1);
    i64 ans = 0;
    map<int, int> mp;
    for (int i = 1; i <= n;i++){
        cin >> c[i];
        mp[c[i]] = i;
    }
    int cur = 0, sum = 0;
    for(auto i:mp){
        if (i.second > cur){
            sum += (i.second - cur);
            ans += sum / i.first;
            cur = i.second, sum = sum % i.first; 
            //需记录当前遍历到的位置和所剩金币
        }
    }
    cout << ans << endl;
    return 0;
}

M. 有效算法（二分，线段相交）

时间复杂度：$O(T \times n \log n)$

题意

    给定长度为$n$的正整数序列$\{a_n\}$和$\{b_n\}$ ，对于每个$a_i$，进行恰好一次转换：

  • 将$a_i$ 变成满足$|a_i-x| \le k \times b_i$ 的任意整数$x$

    请求出 最小 的非负整数$k$，使得存在至少一种方案使得$a_i$所有数均相等 .

数据范围

  • $1 \le T \le 1.5 \times 10^5$
  • $2 \le n \le 3 \times 10^5,\sum n \le 3 \times 10^5$
  • $1 \le a_i,b_i \le 10^9$

思路

​     题目所求是最小值，不难想到 二分答案 的操作。对$k$的值进行二分查找，所以需要找到二分函数判定的条件：

  • 设$c=k \times b_i$，显然$c$是定值，拆开绝对值，即 $a_i-c \le x \le a_i+c$
  • 存在一种方案使得转换成$x$ 的值完全一致，不难想到，将各个区间范围抽象成线段，只需要判断所有线段是否两两相交
  • 设线段的左端点为$L$，右端点为$R$ ，那么线段相交的条件就是$L_{max} \le R_{min}$.

tips:需要注意二分的上界，过小则范围不够，过大则爆long long !

​

Code:

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
#include<bits/stdc++.h>
#define inf 1E10
#define endl '\n' 
using i64 = long long;
using namespace std;
int t, n;
int a[300010], b[300010];
bool check(i64 x){
    i64 L, R, lmax = -1E18, rmin = 1E18;
    for (int i = 1; i <= n;i++){
        L = (i64)a[i] - x * b[i];
        R = (i64)a[i] + x * b[i];
        lmax = max(lmax, L), rmin = min(rmin, R);
    }
    return (lmax <= rmin);
}
void solve(){
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    for (int i = 1; i <= n;i++)
        cin >> b[i];
    i64 l = 0, r = inf, ans;
    while(l<=r){
        i64 mid = l + r >> 1;
        if (check(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    cout << ans << endl;
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    cin >> t;
    while(t--)
        solve();
    return 0;
}

H. 随机栈 (概率论/逆元)

前置知识：逆元（除法取模）

题意

​     有一个初始为空的多元集合（$multiset$），总共进行 $2n$ 次操作，其中$n$次插入$n$次取出。给定操作序列$a$，插入时$a_i \ge 0$，取出时$a_i = -1$。已知每次取出元素的事件相互独立，并保证每次取出时集合一定非空，将取出的数排成一个序列，请问这个序列递增（当$i \in [1,n), a_{i+1} \ge a_i$）的概率是多少? 由于答案可能不是整数，只需要输出这个值对$998244353$取模的结果 .

数据范围

  • $1 \le n \le 2 \times 10^5$
  • $-1 \le a_i \le n$

思路

​     题设条件是取出的数应当递增序列，不难想到，每次取数应当是当前集合内的最小值，同时，如果插入的数严格小于已经取出的元素（递增序列）的最大值，那么递增序列显然无效，最终的概率就是0 .

​     如若能构建递增序列，由于每次取元素的事件是独立的，设第$i$次取数的概率为$p_i$，所以最终的概率为$\prod \limits_{i=1}^n p_i$ ；设第$i$ 次取数时元素内最小值为$x$，且$x$的元素数量为$cnt$，那么$p_i = \dfrac{x}{cnt}$ .

​     综上，需要维护的信息是当前集合内的各个元素，集合内的最小值以及各个元素的数量，可以使用$STL$容器$multiset$ 直接模拟插入和删除，元素的数量则可以用 $map$ 加以维护 .

​     最后，需要运用到除法取模的相关数论知识（逆元），因$\dfrac{P}{Q}(mod\: 998244353)=P \cdot Q^{-1} (mod\: 998244353)$ ，根据费马定理，如果模数是一个质数，有$Q^{p-1} mod \:p=1$ ，则$Q^{-1}$的逆元的数值等于$Q^{p-2}$ ，最终的答案就是$P \times Q^{p-2} (mod \: 998244353)$ ，需要应用快速幂取模 .

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
const i64 p = 998244353;
using namespace std;
int power_mod(i64 a, i64 b, i64 mod){
    i64 res = 1LL;
    a = a % mod;
    while (b){
        if (b & 1)
            res = (res * a) % mod;
        b /= 2;
        a = (a * a) % mod;
    }
    return res;
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
    n <<= 1;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int num = 0, mx = 0; // mx表示当前递增序列的最大值
    i64 P = 1LL, Q = 1LL;
    map<int, int> cnt;
    multiset<int> st;
    bool flag = 1;
    for (int i = 1; i <= n;i++){
        if(a[i]>=0){
            if (a[i] < mx){
                flag = 0;
                break;
            }
            st.insert(a[i]), cnt[a[i]]++;
        }else{
            int temp = *st.begin();
            (P *= cnt[temp]) %= p;
            (Q *= st.size()) %= p;
            st.erase(st.find(temp));
            cnt[temp]--;
            mx = max(mx, temp);
        }
    }
    i64 inv = power_mod(Q, p - 2, p); // Q的逆元值
    i64 ans = (P * inv) % p;
    cout << (flag ? ans : 0) << endl;
    return 0;
}

L. Toxel 与 PCPC II (动态规划)

时间复杂度：$O(50m)$

题意

​     需要调试一段共有$n$行的代码，已知其中有$m$行代码有$bug$，位置为$a_1,a_2,…,a_m$ .

​     每次调试可以选定一个整数$i$,使得程序从第$1$行开始运行到第$i$行，共需要时间$i$秒；同时，会对前$i$行所有的$bug$进行修复，假设现存的$bug$数为$x$，则需要$x^4$进行修复 .

​     请问最短需要多少秒才能完成$debug$ ，修复整个代码所有的漏洞？

数据范围

  • $1 \le m \le n \le 2 \times 10^5$
  • $1 \le a_i \le n$

思路

​     根据直觉，本题存在多状态且子问题有重叠，可使用动态规划进行求解 .

​     设$dp[i]$表示前$i$行代码被修复（含运行）的最短时间，其状态转移方程显然为：

  • $dp[i]=Max(dp[i],dp[j]+(i-j)^4+a[i])$，其中$1 \le j < i<=m$

​     总时间复杂度为$O(m^2)$ ，无法通过本题，所以应当对时间复杂度进行优化.

​     不难注意到，$x^4$的指数增长极快，$50^4 > 2 \times 10^5$ ，而代码位置的上界就是$2 \times 10^5$ ， 粗略估计只需考虑$i-j \le 50$的范围即可（实际更小）。此时时间复杂度便降为$O(50m)$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<i64> a(m + 1), dp(m + 1, 1E15);
    dp[0] = 0;
    for (int i = 1; i <= m;i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        for (int j = i - 1; j >= 0 && i - j <= 50; j--)
            dp[i] = min(dp[i], dp[j] + 1LL * (i - j) * (i - j) * (i - j) * (i - j) + a[i]); 
    cout << dp[m] << endl;
    return 0;
}

​

​