【CCF-CSP】202112-3 登机牌条码

202112-3 登机牌条码

#include
using namespace std;
const int N = 100010;

int main()
{
    int mode = 0;
    int w,s;
    cin>>w>>s;
    string in;
    int code[N];
    int res[N];
    cin>>in;
    int j=0;
    for(int i=0; i
        if(in[i]>= 'A' && in[i]<='Z'){
            if(mode==0){
                code[j]=in[i]-'A'; j++;
            }
            else if(mode == 1){
                code[j] = 28; j++;
                code[j] = 28; j++;
                code[j]=in[i]-'A'; j++;
                mode = 0;
            }
            else{
                code[j] = 28; j++;
                code[j]=in[i]-'A'; j++;
                mode = 0;
            }
        }
        else if(in[i]>='a' && in[i]<='z'){
            if(mode ==0){
                code[j] = 27; j++;
                code[j]=in[i]-'a'; j++;
                mode = 1;
            }
            else if(mode==1){
                code[j]=in[i]-'a'; j++;
            }
            else{
                code[j] = 27; j++;
                code[j]=in[i]-'a'; j++;
                mode = 1;
            }
        }
        else{
            if(mode == 0){
                code[j] = 28; j++;
                code[j]=in[i]-'0'; j++;
                mode = 2;
            }
            else if(mode == 1){
                code[j] = 28; j++;
                code[j]=in[i]-'0'; j++;
                mode = 2;
            }
            else{
                code[j]=in[i]-'0'; j++;
            }

        }
    }
    if(j%2 != 0){
        code[j] = 29;j++;
    }
    int index = 0;
    for(int k=0; k
        res[index] = code[k]*30+code[k+1];
        index++;
    }
    //index is the num of data
    //cout<<"index1:"<
        k = 0;
    }else{
        k = pow(2,s+1);
    }
    while((index+1+k)% w != 0){
        res[index] = 900;
        index++;
    }
    //cout<<"index2:"<
        cout<=0; i--){
        g[i] = g[i+1]%929;
        a=(a*3)%929;
        for(int j=i+1; j
            g[j] = (g[j+1] - g[j]*a)%929;
        }
        g[g_size-1] = (-g[g_size-1]*a)%929;
    }
    

    d[0] = n;
    for(int i=1; i<=n; i++){
        d[i] = res[i-1];
    }
    for(int i=n+1; i
        d[i] = 0;
    }
    

    for(int i=0; i
        int temp = d[i]/g[0];
        for(int j=0; j<=k; j++){
            //cout<<"i:"<
        cout<<(-d[i]%929+929)%929< 
 
 
参考文章思路：link
 自己做出来了50分，有两个方面没有考虑到：
 
 
在求r(x)多项式时，自己一直想的是通过找规律来解决，通过各种拆多项式，写了密密麻麻几页纸，做的都是些无用功。将思路转换为求余是最关键的一步。这种没办法，只能多练。
没有考虑到数据爆炸的问题，如果有考虑到这个问题，或许也不会naive到只弄个int，好歹会搞个long long示意一下。自己对数据空间和时间的复杂度太不敏感了，很明显，光一个int大小也就
      
       
        
         
          
           2
          
          
           31
          
         
        
        
         2^{31}
        
       
      231，而本题k的范围[1，512]，只需要k为32时，
      
       
        
         
          
           3
          
          
           32
          
         
        
        
         3^{32}
        
       
      332就足以撑爆小小的int。long long在
      
       
        
         
          
           3
          
          
           512
          
         
        
        
         3^{512}
        
       
      3512面前也跟个小朋友似的。但是自己却丝毫没有考虑到这个问题，甚至在第一遍程序正确的情况下（只是未考虑数据爆掉的情况）又写了第二遍，还一直以为时程序逻辑的错误。
 这个毛病也体现在边界问题上，时常没有仔细考虑边界问题，思考不清楚。经常示例过了，但一提交就完蛋，自己还检查不出来。以后得刻意留意一下数据爆炸、边界条件、时间和空间复杂度的问题。
 
 
附c++数据范围：
 int 32位：不能超过
    
     
      
       
        2
       
       
        ∗
       
       
        1
       
       
        
         0
        
        
         10
        
       
      
      
       2*10^{10}
      
     
    2∗1010，一般在
    
     
      
       
        1
       
       
        
         0
        
        
         9
        
       
      
      
       10^9
      
     
    109以内int都不会超，但到了
    
     
      
       
        1
       
       
        
         0
        
        
         10
        
       
      
      
       10^{10}
      
     
    1010且有加法操作，就得考虑用long long。
 long long 64位：不能超过
    
     
      
       
        9
       
       
        ∗
       
       
        1
       
       
        
         0
        
        
         19
        
       
      
      
       9*10^{19}
      
     
    9∗1019。
 
int                        [-2^31,2^31-1] 
				十进制：[-2147483648,+2147483647]
unsigned                   [0,2^32-1]
long long                  [-2^63,2^63-1]
			十进制：[-9223372036854775808,9223372036854775807]
unsigned long long         [0,2^64-1]
char                       [-128,127]