小花生

study & life record.

2024年5月CSP校内选拔赛

发表于 分类于 ，

2024年5月CSP校内选拔赛，回顾+题解。

得分245/400，AC了两个小难题，差强人意。

题解

A. 装饰品

考点：乘法原理，快速幂，费马小定理

题意：将 m 种元素填入 n 个盒子，要求不存在任何长度大于等于 2 的回文子串，求解填入的方法数。
（结果对 1e9 + 7 取模）（对所有数据，$1\leq n,m\leq1e18$）

分析：不难发现，只要满足不存在长度为 2，3 的回文子串，就不会出现回文子串。所以填入时只需保证填入的元素不与前两个位置相同即可。即 $m\times (m-1)\times(m-2)^{n-2}$ 对 1e9 + 7 取模为所求。

实际上，n 与 m 范围过大，需要考虑多个优化：
1）快速幂。
2）取模运算对加法友好，在开始前将 m 对 1e9 + 7 取模。
3）根据费马小定理，由 1e9 + 7 is prime，在开始前将 n 对 1e9 + 6 取模。

费马小定理：
$\ \ $若 p 是一个质数，且 a 不是 p 的倍数，则有 $a^{p-1}\equiv 1\ (mod\ p)$

完整代码：

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

const int p = 1e9 + 7;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

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

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = read();
    while(t--){
        int n = read() % (p - 1), m = read() % p;
        if(n == 1){
            cout << m % p << '\n';
        }
        else{
            int ans = ((m % p) * ((m - 1) % p)) % p;
            ans = (qmi(m - 2, n - 2) * ans) % p;
            cout << ans << '\n';
        }
    }
    return 0;
}

B. 幻兽帕鲁

题意：给定长度为 n 的数列，在其中取数，规定不能连续取超过 k 个数，求取出数的和的最大值。

分析：
1）朴素dp，从动态规划开始入手，规定 dp[i][j] 表示第 i 天，连续取出 j 个数时，已取出数的最大值。
状态转移：dp[i][0] 由前一天的 dp 最大值决定。
$j > 0$ 时，dp[i][j] = dp[i - 1][j - 1] + a[i]。
（时间复杂度 $O(n^2)$​ 得分 50/100）

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>
using namespace std;

const int N = 1005;
int a[N], dp[N][N];

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int n = read(), k = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
        
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            dp[i][0] = max(dp[i][0], dp[i - 1][j]);
        }
        for(int j = 1; j <= k; j++){
            dp[i][j] = dp[i - 1][j - 1] + a[i];
        }
    }
    
    int ans = 0;
    for(int i = 0; i <= k; i++){
        ans = max(ans, dp[n][i]);
    }
    cout << ans;
    return 0;
}

2）单调栈优化dp，不难发现，当dp[i][j]中，有 j1 < j2 且 dp[i][j1] > dp[i][j2] 时，dp[i][j_2]是不必考虑的。使用单调栈维护每一个dp[i]的情况即可。AC代码：

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

const int N = 1e5 + 10;
int a[N];
vector<PII>dp[N];

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

signed main() {
    int n = read(), k = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();

    dp[1].emplace_back(0, 0);
    if (a[1] > 0) dp[1].emplace_back(a[1], 1);
    for (int i = 2; i <= n; i++) {
        auto tmp = dp[i - 1].back();
        dp[i].emplace_back(tmp.first, 0);
        int pos = upper_bound(dp[i - 1].begin(), dp[i - 1].end(), make_pair(dp[i][0].first - a[i], 1000000)) - dp[i - 1].begin();
        for (int j = pos; j < dp[i - 1].size(); j++) {
            if (dp[i - 1][j].second != k)
                dp[i].emplace_back(dp[i - 1][j].first + a[i], dp[i - 1][j].second + 1);
        }
    }

    cout << dp[n].back().first;

    return 0;
}

补充

AC后非常满足，直到看到出题人题解（单调队列优化dp）：

好一个正难则反。

C. 下水道鼠鼠

题意：图中一些点上给定若干块蛋糕（称为聚落），称在距离 s 内，存在蛋糕数为 s 的结点的点为宜居点，输出宜居点的个数及所有宜居点。

分析：考虑聚落向外扩散，初始化所有除聚落的点的宜居值为 -1，聚落的宜居值=蛋糕数量，开始时将所有点压入优先队列，向外更新宜居值即可。（感觉比前面两题简单www）

完整代码：

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>
using namespace std;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
int n, m, k;
vector<int> g[N]; bool vis[N];
priority_queue<PII> q;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main() {
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        g[x].emplace_back(y), g[y].emplace_back(x);
    }

    for (int i = 1; i <= k; i++) {
        int p = read(), s = read();
        q.emplace(s, p);
    }

    while (!q.empty()) {
        int s = q.top().first, u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        if (s == 0) continue;

        for (auto& v : g[u]) {
            if (!vis[v]) {
                q.emplace(s - 1, v);
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        if (vis[i]) res++;
    cout << res << '\n';

    for (int i = 1; i <= n; i++)
        if (vis[i]) cout << i << ' ';

    return 0;
}