题目来源：
问题描述
| 试题编号： | 202112-3 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 试题名称： | 登机牌条码 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 时间限制： | 1.0s | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 内存限制： | 512.0MB | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 问题描述： | 题目背景西西艾弗岛景色优美，游人如织。但是，由于和外界的交通只能靠渡船，交通的不便严重制约了岛上旅游业的发展。西西艾弗岛管委会经过努力，争取到了一笔投资，建设了一个通用航空机场。在三年紧锣密鼓的主体建设后，西西艾弗岛通用航空机场终于开始进行航站楼内部软硬件系统的安装和调试工程了。小 C 是机场运营公司信息部的研发工程师，最近，信息部门的一项重要任务是，研发登机牌自助打印系统。如图所示的是设计部门根据国际民航组织的行业标准设计的登机牌样张。
登机牌上最重要的部分就是最下方的机读条形码了。小 C 承担了生成机读条形码算法的开发工作。从被编码的数据到条形码，中间有好多步骤要走。小 C 请你来帮忙，让你帮忙处理一下数据编码的问题。 题目描述登机牌上的条形码，是 PDF417 码。PDF417 码的结构如下图所示。
PDF417 码组成的基本元素是码元（Module），所有的码元都是等大的矩形，填充有黑色或白色。码元先组成行，若干行堆叠组成整个 PDF417 码。每一行中，每 17 个码元表示一个码字（Code word）。码字是 PDF417 编码中的最小数据单位。每个码字图案中，有交替排列的四个黑色矩形和四个白色矩形，这便是 “417” 的由来。每行开始和结尾有固定的起始和中止图案。与他们相邻的是行左侧和右侧标志，表示行号、行内码字个数等信息。中间的是有效数据区。编码的步骤是：先按照编码规则，将被编码的数据转换为码字；接着根据选定 PDF417 码的宽度（即每行码字的数目）以及冗余程度计算校验码字；最后将码字按规则转换为对应的图案，并按照从左至右，从上至下的的顺序填入有效数据区，并与起始终止图案和行左右标志拼合，形成完整的 PDF417 码。 每个码字是一个 0 至 928 之间的数字，每个码字可以编码两个输入字符。对于输入的被编码的数据，按照下表进行编码。编码器共有三种模式：大写字母模式、小写字母模式和数字模式。在编码开始时，编码器处于大写字母模式。编码器处于某种模式时，仅能编码对应类型的字符，如果需要编码其它类型的字符，需要通过特殊值切换到对应模式下。要进行模式切换，可以有多种切换方法。例如，要从大写模式切入小写模式，可以直接用 27 切入，也可以先用 28 切入数字模式后立刻再用 27 切入小写模式。你需要选择最短的方式进行切换，因此只有前一种方法是正确的。需要注意的是，从小写模式不能直接切入大写模式，必须要经过数字模式过渡。
按照这个方法可以得到一系列的不超过 30 的数字。如果有奇数个这样的数字，则在最后补充一个 29，使之成为偶数个。将它们两两成组，假设?H?和?L?是一组中连续出现的两个数字，那么可以得到一个码字是： 例如，要编码 “ Data 由于只有奇数个数字，需要在末尾补充 29，然后将它们两两成组： Data 最后计算码字，例如：30×7+4=214，以此类推，可以得到码字为： Data 接下来要计算校验码。校验码字的数目，由校验级别确定。假设校验级别为?s(0≤s≤8)，则校验码字的数目为?k=2s+1。特别地，如果指定了?s=?1，则表示不需要计算校验码字。要计算校验码字，首先要确定数据码字。数据码字由以下数据按顺序拼接而成（如图所示）：
设全部数据码字依次为?dn?1,dn?2,…,d0；校验码字依次为?ck?1,ck?2,…,c0。那么校验码字按照如下方式计算： 取?k?次多项式?g(x)=(x?3)(x?32)…(x?3k),?(n?1)?次多项式?d(x)=dn?1xn?1+…dn?2xn?2+…d1x+d0，找到多项式?q(x)?和不超过?(k?1)?次的多项式?r(x)，使得 例如，如果要将? Data 因此有?g(x)=x2?12x+27，d(x)=6x5+214x4+841x3+821x2+449x+900，不难得到?r(x)=?32902164x+98246277，因此相应可以计算出?c1=229≡?32902164mod929，c0=811≡98246277mod929。这样，全部码字序列即为： Data 在本题中，你需要帮助小 C 完成的任务是，给定被编码的数据，计算出需要填入有效数据区的码字序列。被处理的数据中只含有大写字母、小写字母和数字。 输入格式从标准输入读入数据。 输入的第一行包含两个用空格分隔的整数?w、s，分别表示有效数据区每行能容纳的码字数和校验级别。保证?0<w<929，?1≤s≤8。特别地，当?s=?1?时，表示不需要计算校验码字。 输入的第二行是一个非空字符串，仅包含大小写字母和数字，长度保证编码后全部数据码字的个数少于 929。 输出格式输出到标准输出。 输出若干行，每行一个数字，表示编码后的全部码字序列。 样例1输入Data 样例1输出Data 样例1解释要求编码数据是? 样例1输入Data 样例1输出Data 样例2解释本组数据即为此前用于说明编码过程的示例。 子任务对于?20%?的数据，有?s=?1，且输入字符串中仅含有大写字母或小写字母； 对于?40%?的数据，有?s=?1； 对于?80%?的数据，有?s≤2; 对于?100%?的数据，满足全部对于输入的要求。 |
解题思路：
本题前 40 分，认真模拟即可拿到分数。
后 60 分得分难点在于 如何求解 r(x)， 即如何进行多项式求余?。
多项式求余思路我是看的这篇文章滴：
?https://ccf-csp-project.github.io/CSP-Project-with-MkDocs/problem/24/3/1/#100
代码：
/* 100 */
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <math.h>
using namespace std;
void char2num(string &s, vector<int> &a) {
int preStatus = 0, curStatus; // 0:A-Z; 1:a-z; 2:0-9
map<int, char> myMap;
myMap[0] = 'A';
myMap[1] = 'a';
myMap[2] = '0';
for (char c: s) {
if (c <= 'Z' && c >= 'A') {
curStatus = 0;
}
else if (c <= 'z' && c >= 'a') {
curStatus = 1;
}
else {
curStatus = 2;
}
if (preStatus != curStatus) {
if ((preStatus == 0 && curStatus == 1) || (preStatus == 2 && curStatus == 1)) {
a.emplace_back(27);
}
else if ((preStatus == 1 && curStatus ==2) || (preStatus == 2 && curStatus == 0) || (preStatus == 1 && curStatus ==0) || (preStatus == 0 && curStatus ==2)) {
a.emplace_back(28);
}
if (preStatus == 1 && curStatus == 0) { // 转两次
a.emplace_back(28);
}
}
a.emplace_back(c - myMap[curStatus]);
preStatus = curStatus;
}
if (a.size() % 2 != 0) {
a.emplace_back(29);
}
}
void calculateG(int k, vector<int> &g) {
g[0] = 1;
int b = 3;
for (int i = 1; i <= k; ++i) {
for (int j = i; j > 0; --j) {
g[j] = (g[j - 1] - (g[j] * b) % 929 + 929) % 929;
}
g[0] = (-1 * (g[0] * b) % 929 + 929) % 929;
b = (3 * b) % 929;
}
/*
cout<<"* "<<g.size()<<endl;
for (int i = g.size() - 1; i >= 0; --i) {
cout<<g[i]<<" ";
}cout<<endl;
*/
}
void calculateR(int k, vector<int> xkd, vector<int> g, vector<int> &r) {
/*
cout<<"**XKD ";
for (int i = xkd.size() - 1; i >= 0; --i) cout<<xkd[i]<<" "; cout<<endl;
cout<<"**G ";
for (int i = g.size() - 1; i >= 0; --i) cout<<g[i]<<" "; cout<<endl;
*/
// 多项式除余！
for (int i = xkd.size() - 1; i >= k; --i) {
if (xkd[i] == 0) {
continue;
}
int a = xkd[i];
for (int j = 0; j < g.size(); ++j) {
xkd[i - j] = (xkd[i - j] - (a * g[g.size() - 1 - j]) % 929 + 929) % 929;
}
}
for (int i = k - 1; i >= 0; --i) {
//r[i] = ((-1 * xkd[i]) % 929 + 929) % 929;
r[i] = (929 - xkd[i]) % 929;
}
}
void checkCode(int k,vector<int> b,vector<int> &r) {
vector<int> g(k + 1, 0), xkd(b.size() + k, 0);
// 计算g(x)
calculateG(k, g);
// 计算 x^k * d(x)
for (int i = 0; i < b.size(); ++i) {
xkd[k + b.size() - 1 - i] = b[i];
}
// 计算 r(x)
calculateR(k, xkd, g, r);
}
int main(){
int w, s;
string str;
cin>>w>>s;
cin>>str;
// 字符转码字
vector<int> a;
char2num(str, a);
// 计算 30 * H + L
vector<int> b;
b.emplace_back(0); // 长度预记为 0
for (int i = 0; i < a.size() / 2; ++i) {
b.emplace_back(30 * a[2 * i] + a[2 * i + 1]);
}
// 填充
int k = (s != -1? pow(2, s + 1) : 0);
while ((k + b.size()) % w != 0) {
b.emplace_back(900);
}
b[0] = b.size();
// 计算校验码
vector<int> cc(k, 0);
if (s != -1) {
checkCode(k, b, cc);
}
// 输出结果
for (int i = 0; i < b.size(); ++i) {
cout<<b[i]<<endl;
}
for (int i = k - 1; i >= 0 && s != -1; --i) {
cout<<cc[i]<<endl;
}
return 0;
}
参考文章：
https://ccf-csp-project.github.io/CSP-Project-with-MkDocs/problem/24/3/1/#100