数字删除

Author Avatar
Axell 1月 08, 2019
  • 在其它设备中阅读本文章

【问题描述】

小明最近在研究一个数字删除游戏，正要考考佳佳。游戏规则如下
给定一个正整数，去掉其中若干个数字后剩下的数字按原左右次序将组成一个新的正整数。请问最少删去几个数字，能够使得这个新的正整数合法（不含前导 0）且是 3 的倍数。
小明写下的数字太大，佳佳一时处理不了。请你帮他写一个程序处理出结果吧！

【输入】

第一行一个整数 n，表示小明写下了 n 个正整数
第 2~n+1 行每行一个正整数 Ai

【输出】

共 n 行，每行一个整数，表示最少删去的数字的个数。如果没有合法的方案，请输出“ERR”（不含引号）。

【样例 1】

3
1234
1000
2

1
3
ERR

【样例 1 解释】

第一组删除 1 个留下的整数为 234 或 123。
第二组删除 3 个留下的整数为 0。

【数据范围】

对于 30%的数据，n≤5，Ai≤109 且不含有数字 0。
对于 60%的数据，n≤5，Ai≤10100000 且不含有数字 0。
对于 100%的数据，n≤5，Ai≤10100000。（数字的长度可能达到 100001 位）

思路

  1. 贪心做法:如果总和SUM%3==0,答案为0;如果SUM%3==1,可以删去2个2或1个1,同时最优方案是从后向前删除,取两种方案较小值即可;SUM%3==2时,可以删去2个1或1个2
  2. DP做法:F[i][j]表示从最高位到第i位,总和%3==j时需要删去的最小个数
    F[i][j]=min(F[i+1][j]+1,F[i+1][j-a[i]%3]) (删掉这一位/不删)

最终答案为 $max(F[i][0]+i-1)(1<=i<n)$

代码

贪心

#include <bits/stdc++.h>
using namespace std;

int n,a[100005],b[100005],ans,Tans,sum;
char s[100005];

void solve(){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    sum=0;
    scanf("%s",s+1);
    int len=strlen(s+1);
    for (int i=1;i<=len;++i){
        a[i]=b[i]=s[i]-'0';
        sum+=a[i];
    }
    if (sum%3==0){
        cout<<0<<endl;
        return;
    }else if(sum%3==1){
        ans=Tans=1e8;
        for (int i=len;i>=1;--i){
            if (a[i]%3==1){
                a[i]=-1;
                Tans=1;
                break;
            }
        }
        if (a[1]==-1){
            for (int i=2;i<len;++i){
                if (a[i]==-1) continue;
                if (a[i]!=0) break;
                else{
                    a[i]=-1;
                    Tans++;
                }
            }
        }
        for (int i=1;i<=len;++i){
            if (a[i]!=-1) break;
            if (i==len) Tans=1e8;
        }
        ans=min(ans,Tans);
        Tans=1e8;
        for (int i=1;i<=len;++i) a[i]=b[i];
        for (int i=len;i>=1;--i){
            if (a[i]%3==2){
                a[i]=-1;
                if (Tans==1e8) Tans=9999999;
                else{
                    Tans=2;
                    break;
                }
            }
        }
        if (a[1]==-1){
            for (int i=2;i<len;++i){
                if (a[i]==-1) continue;
                if (a[i]!=0) break;
                else{
                    a[i]=-1;
                    Tans++;
                }
            }
        }
        for (int i=1;i<=len;++i){
            if (a[i]!=-1) break;
            if (i==len) Tans=1e8;
        }
        ans=min(ans,Tans);
        if (ans>=len){
            cout<<"ERR"<<endl;
        }else{
            cout<<ans<<endl;
        }
    }else if(sum%3==2){
        ans=Tans=1e8;
        for (int i=len;i>=1;--i){
            if (a[i]%3==2){
                a[i]=-1;
                Tans=1;
                break;
            }
        }
        if (a[1]==-1){
            for (int i=2;i<len;++i){
                if (a[i]==-1) continue;
                if (a[i]!=0) break;
                else{
                    a[i]=-1;
                    Tans++;
                }
            }
        }
        for (int i=1;i<=len;++i){
            if (a[i]!=-1) break;
            if (i==len) Tans=1e8;
        }
        ans=min(ans,Tans);
        Tans=1e8;
        for (int i=1;i<=len;++i) a[i]=b[i];
        for (int i=len;i>=1;--i){
            if (a[i]%3==1){
                a[i]=-1;
                if (Tans==1e8) Tans=9999999;
                else{
                    Tans=2;
                    break;
                }
            }
        }
        if (a[1]==-1){
            for (int i=2;i<len;++i){
                if (a[i]==-1) continue;
                if (a[i]!=0) break;
                else{
                    a[i]=-1;
                    Tans++;
                }
            }
        }
        for (int i=1;i<=len;++i){
            if (a[i]!=-1) break;
            if (i==len) Tans=1e8;
        }
        ans=min(ans,Tans);
        if (ans>=len){
            cout<<"ERR"<<endl;
        }else{
            cout<<ans<<endl;
        }
    }
}

int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;++i) solve();
    return 0;
}

DP

#include <bits/stdc++.h>
using namespace std;

char s[100005];
int a[100005],m[100005],f[100005][3],sum;

void solve(){
    memset(s,0,sizeof(s));
    memset(f,0,sizeof(f));
    scanf("%s",s+1);
    sum=0;
    int len=strlen(s+1);
    for (int i=len;i>=1;--i){
        a[i]=s[i]-'0';
        sum+=a[i];
        m[i]=a[i]%3;
    }
    memset(f,0x3f,sizeof(f));
    f[len][0]=1;
    f[len][m[len]]=0;
    for (int i=len-1;i>=1;--i){
        for (int j=0;j<=2;++j){
            f[i][j]=min(f[i+1][j]+1,f[i+1][(j-m[i]+3)%3]);
        }
    }
    int ans=1e8;
    for (int i=len;i>=1;--i){
        if (a[i]!=0 && i<=len-1){
            ans=min(ans,i-1+f[i+1][(3-m[i])%3]);
        }else if(m[i]==0) ans=min(ans,len-1);
    }
    if (ans<len) printf("%d\n",ans);
    else printf("ERR\n");
}

int main(){
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/47/