P1942 词编码题解

风中の菜鸡 · 2022-09-15 16:26:09 · 题解

题目大意：给你若干个只含 01 的字符串，让你对每个字符串进行删掉一个 0 或删掉一个 1 或添加一个 0 或添加一个 1 或将一个 1 变成 0 或不变的操作，使这个字符串变成长度为 n 且有 1 的位置号的总和是 0 或者是 n+1 的倍数。无解输出 -1。

思路：模拟。若该字符串长度比 n 小，就进行加字符的操作；若该字符串长度比 n 大，就进行减字符的操作；若该字符串长度等于 n，就不操作或是进行改字符的操作。但要注意操作顺序，这些部分再此不再赘述，代码里有体现。

代码（非常易读）

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0,anss=0,aa,bj;
int k=0,ww=-1,www=-1;
int main(){
    cin>>n;
    string s;
    while(cin>>s){
        ans=0,anss=0,bj=0;
        k=0,ww=-1,www=-1,aa=0;
        if(s.size()==n){//进行操作1或4 
            for(int i=0;i<s.size();i++){
                if(s[i]=='1'){
                    ans=ans+i+1;
                }
            }
            if(ans%(n+1)==0&&bj==0){//操作4 
                for(int i=0;i<s.size();i++){
                    cout<<s[i];
                }   
                bj=1;
            }
            else{//操作1 
                int wz=-1;
                for(int i=s.size()-1;i>=0;i--){
                    if(s[i]=='1'){
                        int aa=ans-(i+1);
                        if(aa%(n+1)==0){
                            wz=i;
                        }
                    }
                }
                if(wz!=-1){

                    for(int i=0;i<wz;i++){
                        cout<<s[i];
                    }
                    cout<<'0';
                    for(int i=wz+1;i<=s.size();i++)
                        cout<<s[i];
                    bj=1;
                }
            }
            if(bj==1)
                cout<<endl;
        }
        else if(s.size()<n){//进行操作2了 
            for(int i=0;i<s.size();i++){
                if(s[i]=='1'){
                    ans++;
                    anss=anss+i+1;
                }
            }       
        //  cout<<anss;
            for(int i=0;i<=s.size();i++){//1被删了 
                int aa=ans-k+anss;  
                if(aa%(n+1)==0){
                    ww=i;
                    break;
                }
                if(s[i]=='1')
                    k++;
            }
            k=0;
            for(int i=0;i<=s.size();i++){//0被删了 
                int aa=ans-k+anss;  
                if((aa+i+1)%(n+1)==0){
                    www=i;
                    break;
                } 
                if(s[i]=='1')
                    k++;
                //cout<<aa<<endl;
            }
            if(ww!=-1){
                for(int i=0;i<ww;i++){
                    cout<<s[i];
                }
                cout<<'0';
                for(int i=ww;i<s.size();i++){
                    cout<<s[i];
                }
                bj=1;
            }
            else if(www!=-1){
                for(int i=0;i<www;i++){
                    cout<<s[i];
                }
                cout<<'1';
                for(int i=www;i<s.size();i++){
                    cout<<s[i];
                }
                bj=1;
            } 
            if(bj==1)
                cout<<endl;
        }
        else if(s.size()>n){//进行操作3了 
            for(int i=0;i<s.size();i++){
                if(s[i]=='1'){
                    ans++;
                    anss=anss+i+1;
                }
            }
            //cout<<anss;
            for(int i=0;i<=s.size();i++){//枚举要删的数 
                if(s[i]=='1'){ 
                    aa=anss-i-1;
                    k++;
                    aa-=(ans-k);
                    if(aa%(n+1)==0){
                    //  cout<<anss<<' '<<ans<<' '<<k<<endl;
                        ww=i;
                        break;
                    }
                }
                else{
                    aa=anss-(ans-k);
                    if(aa%(n+1)==0){
                        ww=i;
                    //  cout<<aa<<endl;
                        break;
                    }
                }

            }
            //cout<<ww;
            if(ww!=-1){
                for(int i=0;i<ww;i++){
                    cout<<s[i];
                }
                for(int i=ww+1;i<s.size();i++){
                    cout<<s[i];
                } 
                cout<<endl;
                bj=1;
            }
        }
        if(bj==0){//无解 
            cout<<"-1"<<endl;
        }
    } 
    return 0;
} 
/*
5
101101
*/