欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOI2018湖北省队集训Day2 T1 number

程序员文章站 2022-07-14 15:19:23
...

题面:
NOI2018湖北省队集训Day2 T1 number


得分情况:
在1到n形成的子串上跑KMP,拿到10分。


正解:
对于每个正整数,答案有三种情况:
1.ans为n
2.在n的字符串中至少完整地出现了一个正整数,枚举位数和开头解决
3.n由i的一个后缀和i+1的一个前缀构成,枚举分割位置和位数解决
总复杂度O(n3)


代码:

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

int now[20],t[20],s[20];
int T,lenx;
long long tenpow[20];
long long ans,x;

int main()
{
    tenpow[0]=1;
    for(int i=1;i<=18;i++) tenpow[i]=tenpow[i-1]*10;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&x);
        ans=x;//情况一
        long long x1=x;
        lenx=0;
        while(x1)
        {
            t[++lenx]=x1%10;
            x1/=10;
        }
        for(int i=1;i<=lenx;i++) s[i]=t[lenx-i+1];
        //情况二
        for(int len=1;len<=lenx;len++)
        {
            for(int i=1;i+len-1<=lenx&&i<=len;i++)
            {
                if(s[i]==0) continue;
                bool flag=1;
                int j=i-1;
                x1=0;
                for(int k=i;k<=i+len-1;k++) x1=x1*10+s[k];
                long long nowans=x1;
                while(j>=1&&flag)
                {
                    x1--;
                    long long x2=x1;
                    int tlen=0;
                    while(x2)
                    {
                        t[++tlen]=x2%10;
                        x2/=10;
                    }
                    for(int i=1;i<=tlen;i++) now[i]=t[tlen-i+1];
                    int kkk=tlen;
                    for(int k=j;k>=1&&k>=j-tlen+1;k--) if(s[k]!=now[kkk--]) { flag=0;break; }
                    j=j-tlen;
                }
                j=i+len;
                x1=nowans;
                while(j<=lenx&&flag)
                {
                    x1++;
                    long long x2=x1;
                    int tlen=0;
                    while(x2)
                    {
                        t[++tlen]=x2%10;
                        x2/=10;
                    }
                    for(int i=1;i<=tlen;i++) now[i]=t[tlen-i+1];
                    int kkk=1;
                    for(int k=j;k<=lenx&&k<=j+tlen-1;k++) if(s[k]!=now[kkk++]) { flag=0;break; }
                    j=j+tlen;
                }
                if(flag) ans=min(ans,x1);
            }
        }
        //情况三
        for(int i=1;i<lenx;i++)
        {
            long long num1=0,num2=0;
            int len1,len2;
            for(int j=1;j<=i;j++) num1=num1*10+s[j];
            len1=i;
            if(s[i+1]==0) continue;
            for(int j=i+1;j<=lenx;j++) num2=num2*10+s[j];
            if(num2==0) continue;
            len2=lenx-i;
            num1++;
            int qq=0;
            long long num11=num1;
            while(num11)
            {
                num11/=10;
                qq++;
            }
            if(qq!=len1) num1=0;
            for(int j=min(len1,len2);j<=lenx;j++)
            {
                int rep=min(min(len1,len2),lenx-j);
                long long k1=num1,k2=num2;
                for(int k=1;k<=len1-rep;k++) k1/=10;
                k2%=tenpow[rep];
                if(k1==k2)
                {
                    ans=min(ans,(num2-k2)*tenpow[len1-rep]+num1);
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
相关标签: 分类讨论