NOI2018湖北省队集训Day2 T1 number
程序员文章站
2022-07-14 15:19:23
...
题面:
得分情况:
在1到n形成的子串上跑KMP,拿到10分。
正解:
对于每个正整数,答案有三种情况:
1.ans为n
2.在n的字符串中至少完整地出现了一个正整数,枚举位数和开头解决
3.n由i的一个后缀和i+1的一个前缀构成,枚举分割位置和位数解决
总复杂度
代码:
#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;
}