OscarWen
喜欢到处随意折腾
算法

CSP-202112题解

发表于 2022年2月11日 更新于 2023年2月18日
字数总计：4.9k 阅读时长：17分钟
考后复盘，前三题可以全部拿满，第四题拿25，第五题拿12
第一题签到题很简单就不放代码了，第四第五由于只是骗分也不放代码

第一题：序列查询
签到题目
主要题意为给定一组有序的数字序列A和一个最大值N，定义f(x)为序列中小于等于x的最大整数的下标，然后x从0到最大值累加f(x)，求最后的累加值
思路：由于是求累加值，不必要每个f(x)都用二分算出来，可以直接遍历给出的序列，在A[i]和A[i-1]间的x值所对应的f(x)值都相同，因此用乘法算出即可。
时间复杂度为O(n)

第二题：序列查询新解
主要题意为定义一个g(x)来估计第一题的f(x)，g(x)=x/t，t为一个常数，求每一个g(x)与f(x)的误差，然后累加所有的误差求得总误差
思路：不能暴力从0~N进行遍历计算，这样只能得70分，而且时间复杂度是O(Nlogn)，由于N很大所以一定会超时。可以使用双指针进行优化，因为观察到f(x)是x增大一段值才变化（由序列A来决定），而g(x)是x每增大t函数值就加一，那么分别在f、g上设置一个指针按一定的规则进行移动计算，可以将时间复杂度降低到O(n)
具体操作如下，设双指针i、j，外层循环遍历序列A并在每次循环时f自增一，在内层循环中j每次向前一段距离t（也可能小于t），在这段距离中f和g的值不变，即可通过乘法计算误差，当j再向前t会超过A[i]时内层循环停止，然后若有剩余的（即g中一段不变的值跨过了A[i]），这时先计算好当前剩余段f和g的误差，然后调整下次移动j指针的距离。
由于误差可能很大，记得开long long
?
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 <iostream>
#include <cstdio>
#include <cmath>
 
typedef long long LL;
const int N = 1e5 + 100;
 
int n, m;
int t;
LL a[N];
LL res;
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    a[n + 1] = m;
 
    t = m / (n + 1);
 
    LL f = 0, g = 0, u = t;
    for (LL i = 1, j = 0; i <= n + 1; i++, f++) {
        while (j + u <= a[i]) {
            res += abs(f - g) * u;
            j += u;
            u = t;
            g++;
        }
        if (j < a[i]) {
            res += abs(f - g) * (a[i] - j);
            u -= a[i] - j;
            j = a[i];
        }
 
    }
 
    printf("%lld", res);
    return 0;
}

第三题：登机牌条码
经典的大模拟题
思路：前半部分生成数据编码的部分比较简单，按照题目的意思直接模拟即可，这一部分可以拿到40分。难点在于后面校验码的生成，涉及到了多项式的除法，需要先将g(x)多项式展开，这里的展开我使用了深搜+记忆化的方法，然后计算d(x)除以g(x)的多项式余数，多项式除法的计算方法就是直接模拟人手算的过程，每次都除掉d(x)的最高次幂，直到不能除就剩下余数了。
需要格外注意的是，由于g(x)多项式的系数可能很大，多项式除法过程中产生的中间结果的数也很大，所以必须要一边取模一边计算，否则long long 都会爆

?
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <cstring>
#include <vector>
 
using namespace std;
 
typedef long long LL;
const int MOD = 929;
 
int w, s;
string str;
 
int code[2];
int p;
int mode;
vector<int> res;
int length, k;
 
vector<LL> g, f;
int pows[1025];
int memory[520][520];
 
int dfs(int d, int st, int pick) {
    int res = 0;
    if (d == pick)
        return 1;
    for (int i = st; i <= k; i++) {
        if (k - i + 1 < pick - d)
            break;
        if (memory[i + 1][pick - d - 1] == -1) {
            memory[i + 1][pick - d - 1] = dfs(d + 1, i + 1, pick);
        }
        res += memory[i + 1][pick - d - 1] * (-pows[i]);
        res %= MOD;
    }
    return res % MOD;
}
 
void pack(int num) {
    code[p++] = num;
    if (p == 2) {
        res.push_back(code[0] * 30 + code[1]);
        p = 0;
    }
}
 
void changeMode(int target) {
    if (mode == 0 && target == 1) {
        pack(27);
    } else if (mode == 0 && target == 2) {
        pack(28);
    } else if (mode == 1 && target == 0) {
        pack(28);
        pack(28);
    } else if (mode == 1 && target == 2) {
        pack(28);
    } else if (mode == 2 && target == 0) {
        pack(28);
    } else if (mode == 2 && target == 1) {
        pack(27);
    }
    mode = target;
}
 
void coding() {
    // 编码数据
    for (int i = 0; i < str.size(); i++) {
        if (str[i] >= 'A' && str[i] <= 'Z') {
            if (mode != 0)
                changeMode(0);
            pack(str[i] - 'A');
        } else if (str[i] >= 'a' && str[i] <= 'z') {
            if (mode != 1)
                changeMode(1);
            pack(str[i] - 'a');
        } else {
            if (mode != 2)
                changeMode(2);
            pack(str[i] - '0');
        }
    }
 
    if (p > 0)
        pack(29);
 
    if (s > -1)
        k = 2 << s;
    length = 1 + res.size() + k;
    if (length % w != 0) {
        for (int i = 0; i < w - (length % w); i++)
            res.push_back(900);
        length += w - (length % w);
    }
 
    // 计算g(x)的系数
    memset(memory, -1, sizeof memory);
    for (int i = 0; i <= k; i++)
        g.push_back(dfs(0, 1, i));
 
    f.push_back(length - k);
    f.insert(f.end(), res.begin(), res.end());
    for (int i = 0; i < k; i++)
        f.push_back(0);
 
    // 多项式除法
    for (int i = 0; i < length - k; i++) {
        f[i] %= MOD;
        LL div = f[i];
        for (int j = i; j < i + g.size(); j++) {
            f[j] -= g[j - i] * div;
        }
    }
 
    // 通过余数获取校验码
    for (int i = 0; i < k; i++) {
        f[i + length - k] = -f[i + length - k];
        if (f[i + length - k] < 0)
            f[i + length - k] = f[i + length - k] % MOD + MOD;
        res.push_back(f[i + length - k] % MOD);
    }
 
    length -= k;
}
 
int main() {
    scanf("%d%d", &w, &s);
    cin >> str;
 
    pows[0] = 1;
    for (int i = 1; i <= 1024; i++) {
        pows[i] = 3 * pows[i - 1] % MOD;
    }
    coding();
 
    printf("%d\n", length);
    for (int i = 0 ; i < res.size(); i++) {
        printf("%d\n", res[i]);
    }
 
    return 0;
}

第四和第五题可以通过暴力的方法骗到一点分，也就是说通过合理的时间分配，就算是很难的四、五题也可交一个很朴素的方法得到10~20分。

标签:

相关博文

2022 年 2 月
一 二 三 四 五 六 日
 123456
78910111213
14151617181920
21222324252627
28  

bgm

00:00