2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest

A

给定两个整数n , d，然后要求构造一个数字k，要求n × k 的值的数位中包含0...9 至少一次，并且d ( 1 ≤ d ≤ 9 ) 至少两次。

解释：构造一个数字是1234567890+d，这样一定会有两个`出现，由于不能改变后面的位数，因此可以先乘上n的位数，然后加上n，并减去除于n的余数，即可被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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1234567890;
void Totoro()
{
    int n, d;
    cin >> n >> d;
    ll x = M + d;
    int temp = n;
    int cnt = 0;
    while (temp)
    {
        temp /= 10;
        cnt++;
    }
    x = pow(10, cnt) * x;
    x += n;
    x -= x % n;
    cout << x / n << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

B

题意

进行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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1234567890;
void Totoro()
{
    int n;
    cin >> n;
    vector<pair<int, int>> p;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        while (!p.empty() && p.back().first >= x)
        {
            p.pop_back();
        }
        p.push_back({x, i});
    }
    ll ans = 0;
    ll earn = 0;
    ll las = 0;
    for (auto &[x, y] : p)
    {
        earn += y - las;
        las = y;
        ans += earn / x;
        earn -= earn / x * x;
    }
    cout << ans << '\n';
}
int main()
{
    int t = 1;
    while (t--)
    {
        Totoro();
    }
}

F

题意

给出优秀字符串的定义：

  • 长度为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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1234567890;
bool check(string s)
{
    map<char, int> mp;
    for (int i = 0; i < 4; i++)
    {
        mp[s[i]]++;
    }

    return mp.size() == 4;
}
void Totoro()
{
    int n;
    cin >> n;
    int ans = 0;
    while (n--)
    {
        string s;
        cin >> s;
        if (s.length() == 5 && s[2] == s[4] && check(s))
        {
            ans++;
        }
    }
    cout << ans << '\n';
}
int main()
{
    int t = 1;
    while (t--)
    {
        Totoro();
    }
}

H

题意

题目给出2 n 次操作，每次操作有两种情况：

  • − 1 ：从当前集合中取出一个数。
  • 非− 1 ：将当前数字放入集合中。

两种情况各n次，求最后取出的数字数组为递增（小于等于后一项）的概率，概率$ \(表示为：\) pq^{-1} mod~~998244353$。

解释：贪心的想，每一次去取出来的一定是最小的，但是如果要放进去的比之前取出来的要小，那就是一定不可能的了，剩下的取数就每一次去用逆元去计算即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int M = 1234567890;
const int mod = 998244353;
int qpow(int x, int n)
{
    int ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}
int inv(int x)
{
    return qpow(x, mod - 2);
}
int ope[400005];
void Totoro()
{
    int n;
    cin >> n;
    int sz = 0;
    map<int, int> mp;
    int mx = -1;
    int ans = 1;
    for (int i = 1; i <= 2 * n; i++)
        cin >> ope[i];
    for (int i = 1; i <= 2 * n; i++)
    {
        int num = ope[i];
        if (num != -1)
        {
            if (mx > num)
            {
                cout << 0 << '\n';
                return;
            }
            mp[num]++;
            sz++;
        }
        else
        {
            ans = ans * (*mp.begin()).second % mod;
            ans = ans * inv(sz) % mod;
            sz--;
            mx = max(mx, (*mp.begin()).first);
            (*mp.begin()).second--;
            if ((*mp.begin()).second == 0)
                mp.erase(mp.begin());
        }
    }
    cout << ans << '\n';
}
signed main()
{
    int t = 1;
    while (t--)
    {
        Totoro();
    }
}

J

题意

给出一个五位整数，然后将其每位重新排列，组成一个合数并输出；如果无法构造，则输出-1。

很明显：如果包含偶数直接换过去，注意要处理前导0。

如果是奇数，一定是13579，直接排列成样例给的那种即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1234567890;
void Totoro()
{
    string s;
    cin >> s;
    if (s[4] == '0')
    {
        cout << s << '\n';
        return;
    }
    for (int i = 0; i < s.length(); i++)
    {
        if ((s[i] - '0') % 2 == 0 && s[4] != '0')
        {
            swap(s[i], s[4]);
            cout << s << '\n';
            return;
        }
    }
    cout << 97531 << '\n';
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

L

有一份长度为n 的代码，一共有m 行有错，并且给出有bug的行标，修复bug的规则为：

每次能选择一个数字i，然后修复前i 行的所有bug，设前i 行的bug数为x ，则本次需要花费的时间为：$ t_i=i+x^4$

求最少的修复所有bug时间。

解释：

一道很明显的dp题目。

我们可以用\(dp [ i ]\)表示修复前i个bug需要的最短时间，那么状态转移方程为： \(dp[i]=\min_{1\le j\le i}(dp[j]+a[i]+(i-j)^4)\)

但这样是不会通过的，复杂度是不会允许的。

因此需要进行优化，考虑通过4次方进行优化，由于不会出现同时选取太多的bug，因为一定不优秀，因此枚举bug的上界可以换一下。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1234567890;
const int maxn=2e5+5;
int n,m;
ll a[maxn],dp[maxn];
void Totoro()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        dp[i] = 1e18;
    for (int i = 1; i <= m; i++)
    {
        for (int j = i - 1; j >= max(0, i - 50); j--)
        {
            dp[i] = min(dp[i], dp[j] + a[i] + 1ll * (i - j) * (i - j) * (i - j) * (i - j));
        }
    }
    cout << dp[m];
}
int main()
{
    int t = 1;
    while (t--)
    {
        Totoro();
    }
}

M

题意

给出两个长度为n 的数组a , b,要求对每个$ a_i$进行以下操作正好一次：

  • 将$ a_i\(变成满足\) |a_i−x|kb_i$的任意整数x xx。

求出最小的非负整数k，使得存在一个x能够将操作后的a数组按位等于b数组。

思路：这是一道很明显的二分题目，因为有单调性。k越大越容易满足题意，k越小越不容易满足题意。

因此只需要二分答案即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1234567890;
bool check(ll x, int n, vector<ll> a, vector<ll> b)
{
    ll l = -1e18;
    ll r = 1e18;
    for (int i = 1; i <= n; i++)
    {
        ll d = x * b[i];
        l = max(l, a[i] - d);
        r = min(r, d + a[i]);
    }
    return l <= r;
}
void Totoro()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    vector<ll> b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    ll l = 0;
    ll r = 1e9;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid, n, a, b))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << '\n';
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}