中石大第41次CSP培训模拟2题解

作业链接：https://www.luogu.com.cn/contest/314407

邀请码：微信群通知

难度：普及-

赛时答疑与赛后题解：线下答疑

A. [NOIP 2008 普及组] ISBN 号码

[NOIP 2008 普及组] ISBN 号码

思路

简单模拟。

依次提取字符串中的前 9 位数字，按规则计算加权和并对 11 取模得出正确的识别码。将其与输入的最后一位字符进行比对，相等则输出 “Right”，否则替换最后一位并输出正确的字符串。

代码

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;

char num[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'X'};

string s;
int ans, code;

int main() {
    cin >> s;
    int j = 0;
    for(int i = 0; i < 9; i ++) {
        if(s[j] == '-') j ++;
        ans += ((s[j ++] - '0') * (i + 1)) % 11;
        ans %= 11;
    }

    for(int i = 0; i < 11; i ++)
        if(num[i] == s[12])
            code = i;

    if(ans == code)
        cout << "Right" << endl;
    else {
        s[12] = num[ans];
        cout << s << endl;
    }
    return 0;
}

B. 逛画展

逛画展

方法一：暴力枚举（60分）

思路

双重循环暴力枚举区间的起点和终点，用数组统计当前区间内的画师种类。配合两个关键剪枝：当剩余画作总数不足 m 时直接结束外层循环，以及一旦找齐 m 位画师就更新答案并立刻跳出内层循环。时间复杂度O(n2)。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10; // 60 分的数据范围 n <= 10^5
const int M = 2e3 = 5;

int n, m, min_price, x, y;
int a[N], cnt[M];

int main() {
    min_price = 1e9;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    for(int i = 1; i <= n; i ++) {
        // 剪枝：如果剩下的画已经不够 m 幅，直接结束
        if(n - i + 1 < m) break;
        int types = 0;
        // 每次重新枚举前只清空前 m 个画师的计数
        for(int k = 1; k <= m; k ++)
            cnt[k] = 0;

        for(int j = i; j <= n; j ++) {
            if(cnt[a[j]] == 0) types ++;
            cnt[a[j]] ++;
			// 找齐了所有画师的画
            if(types == m) {
                if(min_price > j - i + 1) {
                    min_price = j - i + 1;
                    x = i;
                    y = j;
                }
                // 找到以 i 为起点的最短合法区间后，立刻退出内层循环
                break;
            }
        }
    }

    cout << x << ' ' << y << endl;
    return 0;
}

方法二：双指针（滑动窗口）

思路

利用双指针维护一个滑动窗口，右指针不断向右扩展直到凑齐 m 位画师，然后左指针尝试向右收缩来寻找更短的合法区间。i、j指针实际上先后对同一个数组进行了一次遍历，时间复杂度为O(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
40
41
42
43
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
const int M = 2e3 + 5;

int n, m, min_price, x, y, types;
int a[N], cnt[M];

int main() {
    min_price = 1e9;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> a[i];

    int j = 0;
    for(int i = 0; i < n; i ++) {
        // 右指针 j 负责开疆拓土，一直往右走直到凑齐 m 位画师
        while(j < n && types < m) {
            if(cnt[a[j]] == 0) types ++;
            cnt[a[j]] ++;
            j ++;
        }
        
        // 如果把剩下的全看完了都不够 m 位画师，说明后面也不可能了，直接结束
        if(types < m) break;

        // 更新最小区间（注意此时 j 已经多加了 1，所以区间长度就是 j - i）
        if(min_price > j - i) {
            min_price = j - i;
            x = i + 1;
            y = j;
        }

        // 左指针 i 准备前进一步，把当前的画移出窗口
        cnt[a[i]] --;
        if(cnt[a[i]] == 0) types --;
    }

    cout << x << ' ' << y << endl;
    return 0;
}

方法三：队列

思路

用队列模拟滑动窗口，将画作依次入队并用数组统计频次。如果队头画作的画师在队列中出现次数大于 1，说明队头元素是多余的，直接将其不断出队来极限压缩区间长度，从而实现 O(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
40
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
const int M = 2e3 + 5;

int n, m, min_price, x, y, types;
int a[N], cnt[M];
queue<int> q; // 队列里存的是画的编号（索引）

int main() {
    min_price = 1e9;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    for(int i = 1; i <= n; i ++) {
        // 新画作入队
        q.push(i);
        if(cnt[a[i]] == 0) types ++;
        cnt[a[i]] ++;
        // 核心优化：如果队头的画师在队列中出现次数大于 1
        // 说明这幅画是多余的，直接出队，缩小区间代价
        while(!q.empty() && cnt[a[q.front()]] > 1) {
            cnt[a[q.front()]] --;
            q.pop();
        }
        // 如果刚好凑齐了 m 位大师的画，就更新最小花费
        if(types == m) {
            if(min_price > i - q.front() + 1) {
                min_price = i - q.front() + 1;
                x = q.front();
                y = i;
            }
        }
    }
    cout << x << ' ' << y << endl;
    return 0;
}

C. [CSP-S 2020] 儒略日

[CSP-S 2020] 儒略日

【数据范围】

测试点编号Q=ri≤
11000365
21000104
31000105
4100003 × 105
5100002.5 × 106
61052.5 × 106
71055 × 106
8105107
9105109
10105年份答案不超过 109

10分做法

思路

ri ≤ 365，一年内，枚举判断给定的天数落在几月几日即可。因为 4713≡1 (mod 4) ，而公元前1年为闰年，所以4713年为闰年。

代码

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;

int month_days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int q;
long long r;

int main() {
    cin >> q;
    while(q --) {
        cin >> r;
        // 1月1日是第 0 天，为了方便计算前缀和，天数先加 1
        r ++; 
        // 公元前 4713 年是闰年，2 月加一天
        month_days[2] ++; 
        long long sum_days = 0, target_month;
        for(int i = 1; i <= 12; i ++) {
            sum_days += month_days[i];
            if(sum_days >= r) {
                target_month = i;
                r -= (sum_days - month_days[i]);
                printf("%lld %lld 4713 BC\n", r, target_month);
                break;
            }
        }
        // 恢复平年天数，防止影响下一轮 while 循环的查询
        month_days[2] --; 
    }
    return 0;
}

40分做法

思路

ri ≤ 3 * 105，而1582年10月4日是2299160天，仅计算儒略历即可。引入年份计算，4年一个闰年，所以以4年为周期计算年份。

代码

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>

using namespace std;

int month_days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int q;
long long r, year, is_leap;

int main() {
    cin >> q;
    while(q --) {
        cin >> r;
        
        // 4 年周期 O(1) 计算
        year = r / (365 * 4 + 1) * 4;
        r %= 365 * 4 + 1;

        // 处理平年跨越
        is_leap = 1;
        if(r >= 366) {                   // 如果超过了第一年（闰年），说明已经跨过了一个平年
            year += (r - 1) / 365;       // 算出跨越了几个 365 天
            r = (r - 1) % 365 + 1;       // 算出在这一年里是第几天 (转为 1-based)
            is_leap = 0;
        }
        
        // 如果是第一年（闰年），上面没减过 365，手动加 1 转换为从 1 开始的天数
        if(is_leap == 1) r ++; 
        
        // 如果是闰年，2 月加一天
        if(is_leap == 1) month_days[2] ++; 
        long long sum_days = 0, target_month;
        for(int i = 1; i <= 12; i ++) {
            sum_days += month_days[i];
            if(sum_days >= r) {
                target_month = i;
                r -= (sum_days - month_days[i]);
                
                // 判断并输出公元前或公元后（注意没有公元 0 年）
                if(year - 4713 < 0)
                    printf("%lld %lld %lld BC\n", r, target_month, 4713 - year);
                else 
                    printf("%lld %lld %lld\n", r, target_month, year - 4712);
                break;
            }
        }
        // 恢复 2 月天数，防止污染下一次查询
        if(is_leap == 1) month_days[2] --; 
    }
    return 0;
}
中石大CSP培训 > 202603
#CSP #题解 #算法 #队列 #模拟 #字符串 #双指针 #滑动窗口 #数学
中石大第41次CSP培训模拟2题解
https://blog.yanjz.top/CUP-CSP41-test3/
作者
严嘉哲
发布于
2026年3月24日
许可协议