【CSP】2021-12-3 登机牌条码 大模拟 字符串处理+模拟数学运算（多项式除法）完整代码+思路+遇到问题

本文主要是介绍【CSP】2021-12-3 登机牌条码 大模拟 字符串处理+模拟数学运算（多项式除法）完整代码+思路+遇到问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2021-12-3 登机牌条码 大模拟 字符串处理+模拟数学运算（多项式除法）

做完一题回过来再看发现也不是做的时候觉得那么难，但是当时就是像傻子了一样，不会变通，想不到该怎么做。和碰到那个梯度下降的那道题一样，就蒙圈了找不到思路。以后碰到了模拟数学运算的题目，不是什么找数列找规律，就是简单的模拟手动计算，手动怎么计算，那么代码就怎么写。

然后看了别人的思路才会写，考试当然没有别人的思路可以看呢，那考试怎么办呢？

思路

这个题目分为两大部分，一部分是字符串处理，另一部分是模拟数学运算

1. 字符串处理

字符串处理其实并不难，虽然不难自己写出来了，但是找bug还是花了很长时间的。

字符串处理主要就是按照题目给的，将输入的字符串处理加工，然后转换成对应的数字，没有什么难理解的。

2. 模拟数学运算

模拟数学运算就是使用代码模拟这个的过程

就是遍历消除d（x）的k+1项到最后一项，那么最后k项的系数取反再取模就是所求的c

但是g(x)怎么求呢？肯定还是模拟手动啊。

循环遍历k次，每次乘以一个式子。

怎么乘呢？每个式子都有一个x和一个常数，乘以x就是左移一位，就是开头添加一个0，常数就是每个系数都乘以这个常数 就是这样。

实现过程（遇到的问题）

1. 首先是对字符串处理中遇到的问题

   写判断语句出错

   原本的

       if (a >= '0 && a <= '9')to_state = 2;if (a <= 'Z' && a >= 'A')to_state = 3;if (a <= '0' && a >= '9')to_state = 1;
   

   改过的

       if (a >= '0' && a <= '9')to_state = 2;if (a <= 'Z' && a >= 'A')to_state = 3;if (a <= 'z' && a >= 'a')to_state = 1;
   

   写的时候没按顺序写果然会出错，然后debug 才看到的，应该先检查下代码有没有问题再去debug 的

2. 初始状态没有搞清楚

   

   没有注意到这句话，还以为是一开始是啥初始状态就是啥呢。

3. 数据字段的开头有一个长度的数据

   这个数据我一开始没有主要到，还以为是输入的字符串的长度是多少就是多少呢，原来是在计算完转换成那个什么码后在看code_word有多长（包括他自己）

改完这3个bug就可以拿到40分了

4. 接下来就是模拟多项式除法的过程了（计算校验码的过程）

看了别人的思路后，再写就没有再出错了，只是在取模的问题上有点问题

一开始只在结尾处取模

        for (int i = k - 1; i >= 0; i--){int temp = (-1 * d[i]) % 929;code_word.push_back(temp >= 0 ? temp : temp + 929);}

但是发现并不行只能拿到50分

然后我又在计算g(x) 计算d(x)的过程中取余

        for (int i = 2; i <= k; i++){vector<int> temp = g;g.insert(g.begin(), 0);for (int i = 0; i < temp.size(); i++){g[i] = (temp[i] * three) % 929 + g[i] % 929;g[i] % 929;}three = (three * 3);}
……
……for (int i = d.size() - 1; i >= k; i--){int temp = -1 * d[i];d[i] = 0;for (int j = g.size() - 2; j >= 0; j--){d[i - (g.size() - 1 - j)] = (g[j] * temp) % 929 + d[i - (g.size() - 1 - j)] % 929;d[i - (g.size() - 1 - j)] %= 929;}}

然后就拿到了80分

!

之后再对three变量取模才100分

        for (int i = 2; i <= k; i++){vector<int> temp = g;g.insert(g.begin(), 0);for (int i = 0; i < temp.size(); i++){g[i] = (temp[i] * three) % 929 + g[i] % 929;g[i] % 929;}three = (three * 3) % 929;}

完整代码

#include <bits/stdc++.h>
using namespace std;
int s, w;
string init;
vector<int> numbers;
vector<int> code_word;
void convert_state(int &state, char a)
{int to_state = 0;if (a >= '0' && a <= '9')to_state = 2;if (a <= 'Z' && a >= 'A')to_state = 3;if (a <= 'z' && a >= 'a')to_state = 1;if (to_state == state) // 如果当前字母和当前状态一样return;else // 如果不相同{if (state == 1){if (to_state == 2)numbers.push_back(28);if (to_state == 3){numbers.push_back(28);numbers.push_back(28);}}if (state == 2){if (to_state == 1)numbers.push_back(27);if (to_state == 3)numbers.push_back(28);}if (state == 3){if (to_state == 1)numbers.push_back(27);if (to_state == 2)numbers.push_back(28);}}state = to_state;
}
int main()
{cin >> w >> s;cin >> init;const int begin_num[4] = {0, 'a', '0', 'A'};int state = 3; // 如果 state=1 小写 state=2 数字 state=3 大写for (int i = 0; i < init.size(); i++){convert_state(state, init[i]);numbers.push_back(init[i] - begin_num[state]);}if (numbers.size() % 2 == 1) // 如果是奇数{numbers.push_back(29);}code_word.push_back(0); // 先增加一个长度位for (int i = 0; i < numbers.size(); i += 2){code_word.push_back(30 * numbers[i] + numbers[i + 1]);}int k = -1;if (s != -1){k = 1;for (int i = 0; i < s + 1; i++){k *= 2;}}if ((code_word.size() + max(0, k)) % w != 0){int add_num = w - (code_word.size() + max(0, k)) % w;while (add_num > 0){code_word.push_back(900);add_num--;}}code_word[0] = code_word.size();if (s != -1){// 计算校验字// 模拟多项式除法vector<int> g; // g(x)的系数vector<int> d; // d(x)的系数// 初始化g(x)g.push_back(-3);g.push_back(1);int three = -9;for (int i = 2; i <= k; i++){vector<int> temp = g;g.insert(g.begin(), 0);for (int i = 0; i < temp.size(); i++){g[i] = (temp[i] * three) % 929 + g[i] % 929;g[i] % 929;}three = (three * 3) % 929;}// 初始化d(x)// 乘以x^kfor (int i = 0; i < k; i++){d.push_back(0);}for (int i = code_word.size() - 1; i >= 0; i--){d.push_back(code_word[i]);}// 模拟多项式除法// 要把dx的每一项都消除为0for (int i = d.size() - 1; i >= k; i--){int temp = -1 * d[i];d[i] = 0;for (int j = g.size() - 2; j >= 0; j--){d[i - (g.size() - 1 - j)] = (g[j] * temp) % 929 + d[i - (g.size() - 1 - j)] % 929;d[i - (g.size() - 1 - j)] %= 929;}}for (int i = k - 1; i >= 0; i--){int temp = (-1 * d[i]) % 929;code_word.push_back(temp >= 0 ? temp : temp + 929);}}for (int i = 0; i < code_word.size(); i++){cout << code_word[i] << endl;}return 0;
}

这篇关于【CSP】2021-12-3 登机牌条码 大模拟 字符串处理+模拟数学运算（多项式除法）完整代码+思路+遇到问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---