202112 CSP认证 | 登机牌条码

登机牌条码

这个题的难度相比于神经脉冲网络感觉是往两个方向，该题没有太多的注重时间和空间的优化，重难点在于实现矩阵除法，也就是算法逻辑。

借鉴了这个链接实现：登机牌条码 详细图解

链接详细讲述了如何实现矩阵除法以及矩阵乘法，感觉在今后的算法题中都是很好的借鉴！！
本题代码中为了方便我用了deque双端队列，实现在两端的存储和删除操作（主要针对于乘法操作的地位补0更加方便）；感觉在理解了矩阵除法的计算机思维后要如何实现以后代码就变得很容易了

这里补充一个点，在算padding填充的时候我的代码本来是：padding = w - (1 + 有效数据长度 + 填充数据长度) % w，导致只有90分，这里没有考虑一个情况，也就是刚好数据长度 + 填充码字长度刚好可以被整除的时候，此时无需填充，因此修改代码为：
padding = (1 + sz + k ) % w == 0 ? 0 : w - (1 + sz + k) % w，此时满分。
满分代码如下：

#include<bits/stdc++.h>
using namespace std;
int w, s, k;
vector<int> res;
void dataCoding(string line)
{
    int mode = 1;  //编码模式初始为大写
    vector<int> temp;

    for(int i = 0;i < line.size();i ++){
        if(line[i] >= 'A' && line[i] <= 'Z'){  //'A'-0 = 65
            if(mode == 2){
                temp.push_back(28); temp.push_back(28);
            }else if(mode == 3){
                temp.push_back(28);
            }
            mode = 1;
            temp.push_back(line[i] - 65);
        }
        else if(line[i] >= 'a' && line[i] <= 'z'){ //'a'- 0=97
            if(mode != 2){
                temp.push_back(27);
                mode = 2;
            }
            temp.push_back(line[i] - 97);
        }else {  //'0'- 0 = 48
            if(mode != 3) temp.push_back(28);
            mode = 3;
            temp.push_back(line[i] - 48);
        }
    }
    if(temp.size() % 2) temp.push_back(29);
    int sz = temp.size(); sz /= 2; //sz为有效数据码字个数

    //先计算长度码字
    int padding = (k + sz + 1) % w == 0 ? 0 : w - (k + sz + 1) % w;
    int len = 1 + sz + padding;
    res.push_back(len);
    for(int i = 0;i < temp.size(); i += 2){
        int x = 30 * temp[i] + temp[i + 1];
        res.push_back(x);
    }
    for(int i = 0;i < padding;i ++){
        res.push_back(900);
    }
}

//计算gx
deque<int> calgx()
{
    deque<int> gx;
    int mul = -9;
    gx.push_back(-3); gx.push_back(1);  //初始时为x-3,向量表示为(-3,1)
    for(int j = 0;j < k - 1;j ++){
        //先计算与常数相乘
        vector<int> temp;
        for(int i = 0;i < gx.size();i ++){
            int x = (mul * gx[i]) % 929;
            temp.push_back(x);
        }
        gx.push_front(0);  //乘x

        for(int i = 0;i < temp.size();i ++){  //相加操作
            gx[i] = (gx[i] + temp[i]) % 929;
        }
        mul = (mul * 3) % 929;
    }
    return gx;
    /*
    for(int i = 0;i < gx.size();i ++){
        cout << gx[i] << " ";
    }
    cout << "\n";*/
}
deque<int> calkdx()
{
    deque<int> dq;
    for(int i = 0;i < k;i ++){   //直接补零
        dq.push_back(0);
    }
    for(int i = res.size() - 1;i >= 0;i --){
        dq.push_back(res[i]);
    }
    return dq;
}
void checkCoding()
{

    deque<int> gx = calgx();
    deque<int> kdx = calkdx();
    //r(x)为kdx与gx的余数部分
    int n = res[0];
    for(int t = 1; t <= n;t ++) {  //kdx > gx , gx 不变被用作除数; 最后rx为余数的位次比除数少一, 也就是k - 1次, 计算可得需要消n次
        deque<int> mul = gx;
        int sz = kdx.size();
        for(int i = 0;i < sz - gx.size();i ++){   //补零到最高位对齐, 从高位向低位消
            mul.push_front(0);
        }
        int delta = kdx[sz - 1] / (mul[sz - 1]);
        for(int i = 0;i < sz;i ++){
            mul[i] = (mul[i] * delta) % 929;
            kdx[i] = (kdx[i] - mul[i]) % 929;

        }
        kdx.pop_back();
    }
    for(int i = kdx.size() - 1;i >= 0;i --){
        kdx[i] = -1 * kdx[i];   //-r(x) = 余数
        if(kdx[i] < 0) kdx[i] += 929;
        res.push_back(kdx[i]);
        //cout<<kdx[i] << ' ';
    }
    //cout << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> w >> s;
    k = s != -1 ? pow(2, s + 1) : 0;
    string line; cin >> line;
    dataCoding(line);
    if(k){
        checkCoding();
    }
    for(int i = 0;i < res.size();i ++){
        cout << res[i] << "\n";
    }
    return 0;
}

哦对了，最最重要的一点，通常在最后需要取模的情况下，在中间运算结果中就可以开始取模防止溢出了（这个是取模操作的运算律）！！！感觉是后面很多涉及对结果取模操作的常规操作了。