发表更新刷题集16 分钟读完 (大约2470个字)

CSP 202112-3 登机牌条码 （100分详细图解）

​​点击阅读更多查看文章内容

CSP 202112-3 登机牌条码

更新：2023-5-15

感谢这位同学提出的代码错误，经过改正后，已经可以满分通过了，博客中出现的相应代码也都改正过了，可以直接提交

题目链接

大模拟
做这类题首先一定要读懂题目，这种题往往不会有什么很高深的算法，就是对整个过程的一个模拟，一定要完全理解了题目的整个内容之后再开始写代码

题目整体可以分为两部分，第一部分是求数据码字，第二部分是求校验码，其中数据码字比较好求，看懂题目跟着题目走就可以了，求出数据码字就可以水40分了，后面的难点在于求校验码，这里我的代码只拿到了60分，但没有找到出错的地方，下面给大家详细写一下我的思路，希望能帮助到大家，如果大家找出了我代码中的错误，还请不吝赐教。

数据码字的求解

求数据码字就是给你一个字符串然后对其进行一个编码，其中各个字符所对应的值题目中都已经给出了，唯一需要注意的点就是三种模式的切换。

首先可以先写一个transmode函数用来进行三种模式的切换

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
void transmode(vector<int> &vec, int &oldm, int newm)
{
    if (oldm == 1)
    {
        if (newm == 2)
            vec.push_back(27);
        if (newm == 3)
            vec.push_back(28);
    }
    if (oldm == 2)
    {
        if (newm == 1)
        {
            vec.push_back(28);
            vec.push_back(28);
        }
        if (newm == 3)
            vec.push_back(28);
    }
    if (oldm == 3)
    {
        if (newm == 1)
            vec.push_back(28);
        if (newm == 2)
            vec.push_back(27);
    }
    oldm = newm;
}

有了模式切换之后就可以对字符串进行一个初步的编码，定义一个mode变量用来保存当前的模式，遍历字符串，首先切换到当前字符的模式，然后加入字符的编码即可，最后注意是否需要填充字符，全部字符转换完成后，按照题目要求两两一组计算码字即可

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
vector<int> bianma(string s)
{
    vector<int> ret;
    int mode = 1; //当前模式：1：大写；2：小写；3：数字
    for (char c : s)
    {
        if (isupper(c)) //大写字母
        {
            //将模式换为大写
            if (mode != 1)
                transmode(ret, mode, 1);
            ret.push_back(c - 'A');
        }
        if (islower(c)) //小写字母
        {
            //将模式换为小写
            if (mode != 2)
                transmode(ret, mode, 2);
            ret.push_back(c - 'a');
        }
        if (isdigit(c)) //数字
        {
            if (mode != 3)
                transmode(ret, mode, 3);
            ret.push_back(c - '0');
        }
    }
    if (ret.size() % 2 != 0)
        ret.push_back(29);
    vector<int> mazi;
    for (int i = 0; i < ret.size(); i += 2)
    {
        int temp = 30 * ret[i] + ret[i + 1];
        mazi.push_back(temp);
    }
    return mazi;
}

得到码字之后，我们还需要计算数据码字，这里首先求出校验码字的个数（不需要求出），然后求出总数据所占的行数，并进一步求出填充字符的个数，以及数据码字的长度，与原码字组合得到最终的数据码字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> getsjmz(vector<int> mazi, int w, int s)
{
    int jycnt = 0;
    if (s != -1)
        jycnt = pow(2, s + 1);
    int cnt = 1 + mazi.size() + jycnt;
    int line = ceil(double(cnt) / w);
    int tccnt = w * line - cnt;
    int len = w * line - jycnt;

    vector<int> ret;
    ret.push_back(len);
    for (int i : mazi)
        ret.push_back(i);
    for (int i = 0; i < tccnt; i++)
        ret.push_back(900);
    return ret;
}

校验和的求解

求出数据码字后，我们就要开始校验和的求解了，这是本题的难点所在

首先我们先明确一个概念：通过向量来表示多项式，向量的下标是x的幂，对应的值为x的系数，例如向量{1,-2,3}所表达的多项式是：1-2x+3x^2^

明确了这个概念后我们就可以开始求解校验和了，我们将校验和的求解分成两部分，一是求解g(x)和d(x)多项式，二是进行多项式的取模运算求出r(x)

求解多项式

题目中给出：g(x)=(x-3)(x-3^2^)…(x-3^k^)
我们先计算第一个(x-3)*(x-3^2^)

这里我们首先通过乘法的分配律将其改写为(x-3)*x+(x-3)*(-3^2^)，

首先计算(x-3)*x，x-3对应的向量是{-3,1}，(x-3)*x的结果为x^2^-3x，即{0,-3,1}。到这里大家应该看出规律了吧，一个多项式乘上x^n^，对应的结果就是向量向右移动n个位置，低位补0。

然后我们计算(x-3)*(-3^2^)，多项式运算的结果为-9x+27，对应的向量由{-3,1}变为{27,-9}即在原来的基础上乘上-9,由此我们又可以得出规律，一个多项式乘上一个系数，对应的结果就是向量的各位同时乘上这个系数

然后我们将这两个结果得到的向量相加最终得到{27,-12,1}，对应的多项式为x^2^-12x+27，正是多项式运算的结果

下面通过一个手写版的可能更好看一些
在这里插入图片描述

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

//计算g(x)
//计算g(x)
vector<int> calcgx(int k)
{
    vector<int> gx(k + 1, 0); // gx[i]表示x的i次方的系数
    //初始值为x-3
    gx[1] = 1;
    gx[0] = -3;
    int A = -9;
    //初始值依次乘(x-3^i)
    for (int i = 2; i <= k; i++)
    {
        // temp保存原数组的值，将修改加到gx上
        vector<int> temp;
        temp.assign(gx.begin(), gx.end());
        //整个数组向前推进一位
        gx[0] = 0;
        for (int j = 1; j <= k; j++)
            gx[j] = temp[j - 1] % 929;
        //整个数组都乘上-3^i，并将结果相加
        for (int j = 0; j <= k; j++)
        {
            temp[j] = (temp[j] * A) % 929;
            gx[j] = (gx[j] + temp[j]) % 929;
        }
        A = (A * 3) % 929;
    }
    return gx;
}
//计算d(x)
vector<int> calcdx(vector<int> sjmz)
{
    vector<int> ret;
    for (int i = sjmz.size() - 1; i >= 0; i--)
        ret.push_back(sjmz[i]);
    return ret;
}

多项式取模

通过上面的方法，我们依次求出x^k^d(x)记为kd(x)以及g(x)后，就要计算kdx模gx的余数

这里我们以模拟竖式的方法来计算，通过下图我们可以将计算分为几个步骤

  1. 将除数乘上一个系数，使得被除数减除数之后能消掉最高位
  2. 被除数减除数
  3. 得到的结果继续按照第一步的方法计算，直到最终结果的最高位小于除数

在这里插入图片描述

知道如何计算之后，我们将对多项式的运算换成对向量的运算就可以了，具体过程如下：
在这里插入图片描述

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
//计算校验码
vector<int> calcjx(int k, vector<int> sjmz)
{
    // g(x)
    vector<int> gx = calcgx(k);
    // d(x)
    vector<int> dx = calcdx(sjmz);

    // x^k*d(x);整个数组向前推进x位
    vector<int> kdx(dx.size() + k, 0);
    for (int i = 0; i < dx.size(); i++)
        kdx[i + k] = dx[i] % 929;

    //计算kdx模gx的余数
    int lenkdx = kdx.size();
    int lengx = gx.size();
    while (lenkdx >= lengx)
    {
        int xs = (kdx[lenkdx - 1] / gx[lengx - 1]) % 929;
        int idx = 0;
        for (int i = lenkdx - lengx; i < lenkdx; i++)
            kdx[i] -= (gx[idx++] % 929 * xs % 929) % 929;
        lenkdx--;
    }
    vector<int> ret;
    ret.assign(sjmz.begin(), sjmz.end());

    int i = lengx - 2;
    //去掉头部的0
    while (kdx[i] == 0)
        i--;
    for (; i >= 0; i--)
    {
        kdx[i] = (-kdx[i]) % 929;
        if (kdx[i] < 0)
            kdx[i] += 929;
        ret.push_back(kdx[i]);
    }
    return ret;
}

至此这道题目的各种方法都已经实现完成了，下面放上题目的全部代码，再强调一下，这个代码只有60分，如果大家看完我的方法，发现有什么错误或是不妥的地方，还请不吝赐教。

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <bits/stdc++.h>

using namespace std;

void transmode(vector<int> &vec, int &oldm, int newm)
{
    if (oldm == 1)
    {
        if (newm == 2)
            vec.push_back(27);
        if (newm == 3)
            vec.push_back(28);
    }
    if (oldm == 2)
    {
        if (newm == 1)
        {
            vec.push_back(28);
            vec.push_back(28);
        }
        if (newm == 3)
            vec.push_back(28);
    }
    if (oldm == 3)
    {
        if (newm == 1)
            vec.push_back(28);
        if (newm == 2)
            vec.push_back(27);
    }
    oldm = newm;
}
vector<int> bianma(string s)
{
    vector<int> ret;
    int mode = 1; //当前模式：1：大写；2：小写；3：数字
    for (char c : s)
    {
        if (isupper(c)) //大写字母
        {
            //将模式换为大写
            if (mode != 1)
                transmode(ret, mode, 1);
            ret.push_back(c - 'A');
        }
        if (islower(c)) //小写字母
        {
            //将模式换为小写
            if (mode != 2)
                transmode(ret, mode, 2);
            ret.push_back(c - 'a');
        }
        if (isdigit(c)) //数字
        {
            if (mode != 3)
                transmode(ret, mode, 3);
            ret.push_back(c - '0');
        }
    }
    if (ret.size() % 2 != 0)
        ret.push_back(29);
    vector<int> mazi;
    for (int i = 0; i < ret.size(); i += 2)
    {
        int temp = 30 * ret[i] + ret[i + 1];
        mazi.push_back(temp);
    }
    return mazi;
}
vector<int> getsjmz(vector<int> mazi, int w, int s)
{
    int jycnt = 0;
    if (s != -1)
        jycnt = pow(2, s + 1);
    int cnt = 1 + mazi.size() + jycnt;
    int line = ceil(double(cnt) / w);
    int tccnt = w * line - cnt;
    int len = w * line - jycnt;

    vector<int> ret;
    ret.push_back(len);
    for (int i : mazi)
        ret.push_back(i);
    for (int i = 0; i < tccnt; i++)
        ret.push_back(900);
    return ret;
}

//计算g(x)
vector<int> calcgx(int k)
{
    vector<int> gx(k + 1, 0); // gx[i]表示x的i次方的系数
    //初始值为x-3
    gx[1] = 1;
    gx[0] = -3;
    int A = -9;
    //初始值依次乘(x-3^i)
    for (int i = 2; i <= k; i++)
    {
        // temp保存原数组的值，将修改加到gx上
        vector<int> temp;
        temp.assign(gx.begin(), gx.end());
        //整个数组向前推进一位
        gx[0] = 0;
        for (int j = 1; j <= k; j++)
            gx[j] = temp[j - 1] % 929;
        //整个数组都乘上-3^i，并将结果相加
        for (int j = 0; j <= k; j++)
        {
            temp[j] = (temp[j] * A) % 929;
            gx[j] = (gx[j] + temp[j]) % 929;
        }
        A = (A * 3) % 929;
    }
    return gx;
}
//计算d(x)
vector<int> calcdx(vector<int> sjmz)
{
    vector<int> ret;
    for (int i = sjmz.size() - 1; i >= 0; i--)
        ret.push_back(sjmz[i]);
    return ret;
}
//计算校验码
vector<int> calcjx(int k, vector<int> sjmz)
{
    // g(x)
    vector<int> gx = calcgx(k);
    // d(x)
    vector<int> dx = calcdx(sjmz);

    // x^k*d(x);整个数组向前推进x位
    vector<int> kdx(dx.size() + k, 0);
    for (int i = 0; i < dx.size(); i++)
        kdx[i + k] = dx[i] % 929;

    //计算kdx模gx的余数
    int lenkdx = kdx.size();
    int lengx = gx.size();
    while (lenkdx >= lengx)
    {
        int xs = (kdx[lenkdx - 1] / gx[lengx - 1]) % 929;
        int idx = 0;
        for (int i = lenkdx - lengx; i < lenkdx; i++)
            kdx[i] -= (gx[idx++] % 929 * xs % 929) % 929;
        lenkdx--;
    }
    vector<int> ret;
    ret.assign(sjmz.begin(), sjmz.end());

    int i = lengx - 2;
    while (kdx[i] == 0)
        i--;
    for (; i >= 0; i--)
    {
        kdx[i] = (-kdx[i]) % 929;
        if (kdx[i] < 0)
            kdx[i] += 929;
        ret.push_back(kdx[i]);
    }
    return ret;
}
int main()
{
    int w, s;
    string str;
    cin >> w >> s >> str;
    int k = pow(2, s + 1);
    vector<int> mazi = bianma(str);
    vector<int> sjmz = getsjmz(mazi, w, s);
    //计算校验码
    if (s != -1)
        sjmz = calcjx(k, sjmz);
    for (int i : sjmz)
        cout << i << endl;
    system("pause");
    return 0;
}

CSP 202112-3 登机牌条码 （100分详细图解）

https://shnpd.github.io/2022/03/11/CSP 202112-3 登机牌条码 （100分详细图解）/

作者

ShiHaonan

发布于

2022-03-11

更新于

2025-03-13

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

目录

最新文章

分类

×