129 条题解
-
22
牧云海 LV 10 @ 2009-06-15 15:49:33
这个题实在是太麻烦了！！高精度+枚举+字符串处理+AC，相当综合的一道题目！！！！！
首先，一种很显然的方法，就是枚举长度，之后枚举首位，之后判断这种情况是否满足。理论上，这个题已经做出来了，但是事实上，这个题99%在与细节！！
先说明一下我的判断方法，假设读入的长度是k，那么最终这个串所在的位置的那个数不会超过k位（除非k位全是0），于是对于确定的开始点和长度，前后扫描把这个数弄出来，之后在判断即可。
关于计算位数，这个也非常的讲究。根据WC2009高逸涵大牛的论文指示，一切从简单做起，分类讨论。详见下面的注意事项。
有以下几点注意：
1． 如果这个数后面的位数不够，比如98999，这个数出现在999处，后面的位数不够，要到前面找，此时得出这个数是998+1=999。但是，如果是99999，那么他会判断成99999+1，无法判断正确！！也就是说，如果后面的位数不够，前面的还全是9的话，就要对后面的数减1在加上前面的。比如99999，就是（9-1）+9999=89999，这个就对了。这一点如果不注意的话就得不出999999999--7988888882的解了。
2． 如果读入的数全是0，就在最前面加一个1，最后输出的时候在加对答案1即可。
3． 如果在判断的时候那个数多了一位，注意循环的次数。比如9991000，第一次是999，第二次是1000，我开始的程序始终是循环3次，就是最开始的长度，于是就有4个点WA。
4． 初始的时候答案设为无穷大，逐渐缩小。这个无穷大一定要大于200位，设成300肯定没问题。我开始设成200位，结果200个0和9的两个点WA了。
5． 关于计算位数。我开始是直接把小于这个位数的所有数的总长度*这一位是几累加的。后来发现，有两个问题。第一，如果是有首位的，这个长度就变了。比如，12345（5位），如果是在10之后的，就是0102030405（10位），这个一定要特殊判断。第二，你不感觉刚才的计算少了什么么？对！就是0！如果正常的这么算，100以上的时候，把100的两个0丢了，200的也没了……于是全盘错误……关于这个问题，是可以跟上一个问题一起解决的，详情就是特殊判断！附录：
提供两组数据：
Test27：200个0，ans：17988……88691.
Test29：200个9，ans：19988……8891。PS：
找我上面的改后，把以下四组过了，基本上就差不多了。
21：15.
78910111：7。
000000000：8888888891.
999999999：7988888882. -
2
看了很多题解不是超时就是WA
```cpp
var s,t,q,p,ans,v,z,da,u:string;
a,b,c,d,e,g,i,j,k,m,n,ji:longint;
h:array[1..200]of boolean;
f:array[1..256]of string;
function qian(l:string):string;
var o,w:longint;r:string;
begin
o:=length(l);
r:=l;
while r[o]='0' do dec(o);
r[o]:=pred(r[o]);
for w:=o+1 to length(r) do r[w]:='9';
if r[1]='0' then delete(r,1,1);
qian:=r;
end;
function hou(l:string):string;
var o,w:longint;r:string;
begin
o:=length(l);
r:=l;
while (r[o]='9')and(o>1) do dec(o);
if (o=1)and(r[1]='9') then
r:='1'+r else r[o]:=succ(r[o]);
for w:=o+1 to length(r) do r[w]:='0';
hou:=r;
end;
function sum(l1,w1:string):string;
var o,r,e1:longint;l,w,x:string;
begin
l:=l1;w:=w1;
x:='';
if length(l)<length(w) then
for o:=length(l)+1 to length(w) do l:='0'+l;
if length(l)>length(w) then
for o:=length(w)+1 to length(l) do w:='0'+w;
e1:=0;
for o:=length(w) downto 1 do
begin
r:=ord(l[o])+ord(w[o])-96+e1;
e1:=r div 10;
r:=r mod 10;
x:=chr(r+48)+x;
end;
if e1>0 then x:=chr(e1+48)+x;
sum:=x;
end;
begin
readln(s);
g:=length(s);
f[1]:='9';v:='9';
for i:=2 to 256 do
begin
v:=sum(v,'9');
f[i]:=v;
for j:=1 to i-1 do f[i]:=f[i]+'0';
end;
ans:='';
for i:=1 to 250 do ans:=ans+'0';
c:=1;
for i:=1 to length(s) do if s[i]<>'0' then begin c:=0;break;end;
if c=1 then begin ji:=1;ans:='1'+s;e:=length(ans)-1;end;
if ji=0 then
for i:=1 to g do
begin
for j:=1 to g-i+1 do
begin
if s[j]='0' then continue;
t:=copy(s,j,i);a:=j-1;b:=j+i;
q:=t;p:=t;
while a>0 do begin q:=qian(q);
if length(q)>a then begin t:=copy(q,length(q)-a+1,a)+t;a:=0;end else
begin t:=q+t;a:=a-length(q);
if q='0' then continue;end;end;
while b<=g do begin p:=hou(p);
if length(p)>g-b+1 then begin t:=t+copy(p,1,g-b+1);b:=g+1;end else
begin t:=t+p;b:=b+length(p);end;end;
if t=s then begin ans:=copy(s,j,i);e:=j+i-1;break;end;
end;
if e>0 then break;
end;if ji=0 then
for i:=2 to g do
begin
for j:=g downto g-i+2 do
if j-i<=0 then
begin
if s[j]='0' then continue;
t:=copy(s,j,g-j+1);
p:=copy(s,g-i+1,j-g+i-1);
q:=hou(p);
if length(q)>length(p) then
begin t:=t+copy(q,2,length(q)-1);end else t:=t+q;
c:=0;
p:=qian(t);
if copy(p,length(p)-j+2,length(p))=copy(s,1,j-1) then c:=1;
if c=0 then continue;
if length(t)<length(ans) then c:=0 else
if length(t)=length(ans) then begin if t<ans then c:=0;end else
continue;
if c=0 then begin ans:=t;e:=j-1+length(t);end;
end;
end;
if ji=0 then begin
da:='0';
ans[1]:=pred(ans[1]);
ans:=sum(ans,'1');
da:=ans;
u:='0';
for i:=1 to length(ans)-1 do u:=sum(u,f[i]);
for i:=1 to length(ans)-1 do
da:=sum(da,ans);
da:=sum(da,u);
end else
begin
da:='0';
for i:=1 to e do da:=sum(da,f[i]);
end;
if ji=0 then begin
if length(da)<6 then
begin z:=da;da:='';end else
begin z:=copy(da,length(da)-5,6);delete(da,length(da)-5,6);end;
val(z,d);
d:=d-e;
str(d,z);
da:=da+z;
end;
da:=sum(da,'1');
if ji=1 then da:=sum(da,'1');
writeln(da);
end.
``` -
1
November (CLH_W) LV 10 @ 2022-04-07 19:18:19
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; typedef unsigned long long ULL; const ULL base=10000; char s[300],c[]={'0','1','2','3','4','5','6','7','8','9'}; char t[1000];int size; ULL Hash,hashh,hasht,dt=1,ans=1,head=1,tail; ULL Tp[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,100000000000000}; int main(){ scanf("%s",s);int len=strlen(s); for(int i=0;i<len;i++) Hash=Hash*base+s[i],dt*=base; ULL num=0;bool first=true; while(true){ while(size<=len){ num++; int pow=0; while(Tp[pow]<=num)pow++; while(pow){ pow--; int n=(num/Tp[pow])%10; tail=(tail+1)%512; t[tail]=c[n];size++; } } if(first){ for(int i=1;i<=len;i++) hasht=hasht*base+t[i]; if(hasht==Hash)break; first=false; } hashh=hashh*base+t[head]; hasht=hasht*base+t[head+len]; head=(head+1)%512;ans++;size--; if(Hash==hasht-hashh*dt)break; } printf("%lld",ans); return 0; } -
1
孙鹤鸣 (sunheming) LV 10 @ 2020-11-26 19:40:52
#include<iostream> #include<string> using namespace std; string s; int a[300][305]={0}; int flag=1; int kk=0; //x[0~(n-m)]=s[n~m] int getNum(int x[],int m,int n){ for(int i=n;i>=m;--i) x[n-i]=s[i]-'0'; } void print(int x[]){ int i; for(i=300;i>=0;i--) if(x[i]!=0) break; while(i>=0) cout<<x[i--]; cout<<endl; } //打印补齐后的第一个数 void print(int l){ for(int i=1;i<=l;++i) cout<<s[i]; cout<<endl; } //x=x+t void add(int x[],int t){ x[0]+=t; int i=0; while(x[i]>=10) { x[i+1]+=x[i]/10; x[i]%=10; i++; } } //x=x-t void sub(int x[],int t){ x[0]-=t; int i=0; while(x[i]<0) { x[i]+=10; x[i-1]-=1; i++; } } //前后数位数都足够 bool check(int i,int j,int m,int n){ if(s[i]=='0'||s[m]=='0') return false; int x[305]={0},y[305]={0}; getNum(x,i,j); getNum(y,m,n); add(x,1); for(int d=0;d<=300;d++) if(x[d]!=y[d]) return false; return true; } //后一个数位数不够，只判断后一个数与前一个数对应的位数是否相等 bool tailCheck(int i,int j,int m,int n){ if(s[i]=='0'||s[m]=='0') return false; int x[305]={0},y[305]={0}; getNum(x,i,j); getNum(y,m,n); add(x,1); int d1=300,d2=300; while(x[d1]==0) d1--; while(y[d2]==0) d2--; while(d1>=0&&d2>=0) { if(x[d1]!=y[d2]) return false; d1--;d2--; } return true; } //判断第一个数的位数是否能为l bool find(int l){ int i,j,m,n; i=1;j=l;m=j+1;n=j+l; if(j==s.size()-1&&s[i]=='0') return false; while(true) { if(j>=s.size()-1) return true; if(n>=s.size()-1) {n=s.size()-1;if(!tailCheck(i,j,m,n)) return false;} else if(!check(i,j,m,n)) //前一个数和后一个数的位数都为l { if(!check(i,j,m,n+1)) //前一个数位数为l,后一个数位数为l+1 return false; else {l+=1;n+=1;} } i=m; j=n; m=j+1; n=j+l; } return true; } void Multiply(int x[],int y){ for(int i=0;i<=300;++i) x[i]*=y; for(int i=0;i<=300;++i) if(x[i]>9) { x[i+1]+=x[i]/10; x[i]%=10; } } void add(int x[],int y[]){ for(int i=0;i<=300;++i) x[i]+=y[i]; int i=0; while(x[i]>=10) { x[i+1]+=x[i]/10; x[i]%=10; i++; } } bool comp(int x[],int y[]){ for(int i=300;i>=0;--i) if(x[i]<y[i]) return true; else if(x[i]>y[i]) return false; return false; } void getAns(int finalAns[],int l,int k){ int x[305]={0},ans[305]={0}; getNum(x,1,l); x[l-1]-=1; Multiply(x,l); for(int i=0;i<=300;++i) ans[i]=a[l-1][i]+x[i]; ans[0]+=1+k+kk; for(int i=0;i<=300;++i) if(ans[i]>9) { ans[i+1]+=ans[i]/10; ans[i]%=10; } if(flag==1||comp(ans,finalAns)) for(int i=0;i<=300;++i) finalAns[i]=ans[i]; } //判断数组是否为1000....0000的形式 bool Equal1000(int x[]){ int tot=0; for(int i=0;i<=300;++i) if(x[i]!=0) tot++; if(tot>1) return false; return true; } //判断字符串是否为全0 bool Equal000(string s1){ for(int i=0;i<s1.size();++i) if(s1[i]!='0') return false; return true; } int main() { //a[i]表示所有位数<=i的字符串长度和 for(int i=1;i<=200;++i) { a[i][i-1]=9; Multiply(a[i],i); add(a[i],a[i-1]); } int finalAns[305]={0}; flag=1; string s1; cin>>s1; //如果字符串=000...0,则在最前面加上0,令kk=1,最后的答案要减去kk if(Equal000(s1)) {s1="1"+s1;kk=1;} //l为字符串中第一个数的位数 //k表示字符串中第一个字符是第一个数的第K+1位，k<l for(int l=1;l<=s1.size();++l) for(int k=0;k<l;++k) { s=" "+s1;string s2=""; if(k==0) { if(find(l)) {getAns(finalAns,l,k);flag=0;} } //如果K!=0,则补齐第一个数的前k位 if(k!=0) { int x[305]={0}; getNum(x,l-k+1,l-k+k); //1.直接把第l-k+1至l-k+k之间的数补齐第一个数的前k位 s2=""; int i=k-1; while(i>=0) s2+=x[i--]+'0'; s=" "+s2+s1; if(find(l)) {getAns(finalAns,l,k);flag=0;} //2.如果第l-k+1至l-k+k之间数的形式是10....000,也可以用99....999补齐第一个数的前k位 if(Equal1000(x)) { s2=""; i=k-1; while(i>=0) {s2+='9';i--;} s=" "+s2+s1; if(find(l)) {getAns(finalAns,l,k);flag=0;} } //3.用第l-k+1至l-k+k之间的数减去1,补齐第一个数的前k位 sub(x,1); i=k-1; s2=""; while(i>=0) s2+=x[i--]+'0'; s=" "+s2+s1; if(find(l)) {getAns(finalAns,l,k);flag=0;} } } print(finalAns); // system("pause"); } -
1
很复杂，基本上都是需要高精度。不明白为什么这样的题老是要搞高精度。我觉得思路更重要些。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void inc(int iArr, int num) {
iArr[1] += num;
if(iArr[0] == 0) iArr[0] = 1;
iArr[iArr[0]+1] = 0;
for(int i=1;i<=iArr[0];i++) {
if(iArr[i] >= 10) {
iArr[i] -= 10;
iArr[i+1]++;
} else break;
}
if(iArr[iArr[0]+1] != 0) iArr[0]++;
}
bool match(char cArr, int cALen, int init_len, int* tArr) {
if(cALen > 0 && cArr[0] == '0') return false;
if(cALen <= init_len) return true;
tArr[0] = init_len;
int i,j;
for(i=1;i<=init_len;i++) tArr[i] = cArr[init_len - i] - '0';
int sIndex = init_len;
do {
inc(tArr, 1);
if(sIndex + tArr[0] <= cALen) {
for(i=1;i<=tArr[0];i++)
if(tArr[i] != cArr[sIndex + tArr[0] - i] - '0') return false;
sIndex += tArr[0];
} else {
if(sIndex < cALen) {
i = tArr[0];
while(sIndex < cALen) {
if(tArr[i] != cArr[sIndex] - '0') return false;
i--;
sIndex++;
}
return true;
} else return true;
}
} while(1);
}
#define MAX 210
int minNum[MAX];
int bestSkip;
int arr1[MAX], arr2[MAX], arr3[MAX], result[MAX];
void time(int a,int num, int b) {// b= a*num
int i;
int len = a[0];
memset(b+len+1,0,sizeof(int) * (MAX - (len+1)));
for(i=1;i<=a[0];i++) {
b[i] = a[i] * num;
}
for(i=1;i<=a[0] || b[i] != 0;i++) {
if(b[i] >= 10) {
b[i+1] += b[i] / 10;
b[i] %= 10;
}
}
b[0] = i-1;
}
void add(int *a,int *b) {
int len = a[0] > b[0] ? a[0] : b[0];
for(int i=1;i<=len;i++)
a[i] += b[i];
for(int i=1;i<=len;i++) {
if(a[i] >= 10) {
a[i] -= 10;
a[i+1]++;
}
}
if(a[len+1] != 0) len++;
a[0] = len;
}
void minus(int *a,int *b) {
for(int i=b[0];i>=1;i--)
a[i] -= b[i];
for(int i=1;i<=a[0];i++) {
if(a[i] < 0) {
a[i] += 10;
a[i+1]--;
}
}
int len = a[0];
while(len>0 && a[len] == 0) len--;
a[0] = len;
}
bool smaller(int a,int b) { // return a < b
if(a[0] < b[0]) return true;
else if(a[0] > b[0]) return false;
int len = a[0];
for(int i=len;i>=1;i--) {
if(a[i] < b[i]) return true;
else if(a[i] > b[i]) return false;
}
return false;
}
void calcFinalResult(int iArr,int oArr,int *tArr1, int tArr2, int tArr3) {
memset(tArr1, 0, sizeof(int) * MAX);
memset(tArr2, 0, sizeof(int) * MAX);
memset(tArr3, 0, sizeof(int) * MAX);
memset(oArr, 0, sizeof(int) * MAX);
tArr2[0] = 1; tArr2[1] = 9;
int len;
for(len = 1;len < iArr[0]; len++) {
time(tArr2, len, tArr3);
add(oArr, tArr3);
time(tArr2, 10, tArr2);
}
iArr[iArr[0]]--;
if(iArr[iArr[0]] == 0) iArr[0]--;
inc(iArr,1);
time(iArr, len, tArr3);
add(oArr, tArr3);
}
void copyNum(int *a, int * b){ // a = b
a[0] = b[0];
for(int i=1;i<=b[0];i++) {
a[i] = b[i];
}
}
void copyNum(char* buf, int *oArr, int len) {
oArr[0] = len;
for(int i=1;i<=len;i++) {
oArr[i] = buf[len-i] - '0';
}
}
void print(int *a) {
if(a[0] == 0) putchar('0');
else {
for(int i=a[0];i>=1;i--) putchar(a[i]+'0');
}
}int* main23(char* buf)
{
memset(arr1, 0, sizeof(int) * MAX);
memset(arr2, 0, sizeof(int) * MAX);
memset(arr3, 0, sizeof(int) * MAX);
memset(minNum, 0, sizeof(int) * MAX);
memset(result, 0, sizeof(int) * MAX);
//char buf[MAX]; gets(buf);
int bLen = strlen(buf);
bool allZero;
bool found = false;
int i;
for(i=0;i<bLen;i++) if(buf[i] != '0') break;
if(i>=bLen) allZero = true;
else allZero = false;if(allZero) {
minNum[0] = bLen+1;
minNum[bLen+1] = 1;
bestSkip = 1;
} else {
for(i=1;i<=bLen;i++) {
if(match(buf, bLen, i, arr1)) {
found = true;
copyNum(buf, minNum, i);
bestSkip = 0;
}
for(int skip=1;skip<i;skip++) {
copyNum(buf, arr1, i-skip);
int sIndex = i-skip;
inc(arr1,1);
int j;
for(j=1;j<=i-skip;j++) {
if(sIndex+i-j < bLen && arr1[j] != buf[sIndex+i-j] - '0') break;
}
if(j>i-skip) {
if(match(buf+sIndex,bLen-sIndex,i,arr2)) {
//copyNum(buf+sIndex, arr1, i);
arr1[0] = i;
for(j=i;j>i-skip;j--) arr1[j] = buf[sIndex + i - j] - '0';
if(arr1[arr1[0]] != 0) {
arr2[0] = 1; arr2[1] = 1;
minus(arr1, arr2);
if(!found || smaller(arr1,minNum)) {
copyNum(minNum, arr1);
bestSkip = minNum[0] - (i-skip);
}
found = true;
}
}
}
}
if(found) break;
}
}//printf("minNum:"); print(minNum); printf("\n");
int minNumLen = minNum[0];
calcFinalResult(minNum, result, arr1, arr2, arr3);
//printf("result:"); print(result); printf("\n");
memset(arr1, 0, sizeof(int) * MAX);
i = 1;
bestSkip = minNumLen - bestSkip-1;
while(bestSkip != 0) {
arr1[i] = bestSkip % 10;
bestSkip /= 10;
i++;
}
arr1[0] = i-1;
minus(result, arr1);
return result;
//print(result);
//return 0;
}char* testArr;
int getPos(char* inC) {
char * p = strstr(testArr, inC);
if(p == NULL) {
return -1;
} else {
return p - testArr + 1;
}
}
int getAns(char* inC) {
int * r = main23(inC);
int sum = 0;
for(int i=r[0];i>=1;i--) {
sum *= 10;
sum += r[i];
}
return sum;
}void non_debug() {
char buf[MAX]; gets(buf);
print(main23(buf));
}
#define DEBUG 0
int main() {
//printf("%d",getAns("01"));
//return 0;
if(DEBUG) {
#define MAX_TEST 100000000
testArr = new char[MAX_TEST];
int* testInt = new int[MAX];
testInt[0] = 1; testInt[1] = 1;
for(int i=0;i<MAX_TEST;) {
for(int j=testInt[0];j>=1;j--)
if(i<MAX_TEST) testArr[i++] = testInt[j] + '0';
inc(testInt, 1);
}
memset(testInt, 0 , sizeof(int) * MAX);
testInt[0] = 10;
char iABuf[MAX]; memset(iABuf, 0, sizeof(iABuf));
for(int wei=1;wei<10;wei++) {
iABuf[wei] = '\0';
while(testInt[wei+1] == 0) {
for(int j=wei;j>=1;j--) iABuf[wei-j] = testInt[j] + '0';
int rightAns = getPos(iABuf);
int leftAns;
if(rightAns != -1 && (leftAns = getAns(iABuf)) != rightAns) {
printf("wrong str:%s\n",iABuf);
printf("l:%d, r:%d",leftAns, rightAns);
getchar();
} else {
printf("%s right.\n", iABuf);
}
inc(testInt, 1);
}
memset(testInt, 0 , sizeof(int) * MAX);
testInt[0] = 10;
}
//printf("%d",getAns("010000001100000021000"));
return 0;
} else {
non_debug();
}return 0;
}Accepted, time = 60 ms, mem = 516 KiB, score = 400
-
1
重发一下刚刚的那个代码，，，为啥不可以删除自己提交的题解呢，，真是郁闷
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<sstream> using namespace std; string hahawodabiao; string inttostring(int a){ string b; stringstream ss; ss << a; ss >> b; return b; } void makestring(){ for(int i = 1;i <= 150000; i++){ hahawodabiao += inttostring(i); } } int main() { makestring(); string a; cin>>a; cout<<hahawodabiao.find(a)+1; return 0; }-
xiaoxiongfan @ 2018-07-24 18:17:19
令人窒息的操作
-
乔彦博 @ 2018-08-18 16:28:10
可以改a
-
SameLin @ 2018-10-26 16:05:02
好像不行了，我开到2e7就超时了，短了又wa
-
上海娄山 @ 2021-07-14 08:22:25
#include<bits/stdc++.h> using namespace std; string szc; string int2str(int a){ string b; stringstream ss; ss<<a; ss>>b; return b; } int main(){ string a; cin>>a; for(int i=1;i<=1e9+10;i++){ szc+=int2str(i); if(scz.find(a)!=string::npos){ cout<<szc.find(a)+1;return 0; } } return 0; }改良版代码
超时18个测试点
-
-
1
import java.io.*; import java.util.*; import java.math.*; public class Main { static final int ms = 250; static BigInteger [] beginValue = new BigInteger[ms]; static final BigInteger negOne = BigInteger.valueOf(-1); static final BigInteger nine = new BigInteger("9"); static BigInteger [] rec = new BigInteger[ms]; static BigInteger minLength = new BigInteger("0"); //--------------------------------------------------------------------------// //取得后面一个数字. public static String getNextInt(String a){ String t = new String(""); int len = a.length(), v, m = 1; for (int i = len - 1; i >= 0; --i){ char c = a.charAt(i); v = (int)(c - 48) + m; m = v / 10; v %= 10; t = (char)(v + 48) + t; } while (m > 0){ v = m % 10; t = (char)(v + 48) + t; m /= 10; } return t; } //取得前一个数字 public static String getFrontInt(String a){ String t = new String(""); int len = a.length(), v, m = 1; for (int i = len - 1; i >= 0; --i){ char c = a.charAt(i); v = (int)(c - 48) - m; if (v < 0){ v += 10; m = 1; } else { m = 0; } if (!(0 == i && v == 0)){ t = (char)(v + 48) + t; } } if (t.length() == 0){ t = "0"; } return t; } //比较两个字符串看看是否相等:相等则返回共长，否则返回-1 public static int isEqualString(String a, String line, int pos){ int i; for (i = 0; i < a.length() && (pos + i) < line.length(); ++i){ if (a.charAt(i) != line.charAt(pos + i)) { return -1; } } return i; } //这里按长度从next的segSize开始比较. public static boolean stringCompareBySegSize(String next, int segSize){ int beginPos = segSize, ret = 0, next_len = next.length(); String head = next.substring(0, segSize); while (beginPos < next_len){ String back = getNextInt(head); ret = isEqualString(back, next, beginPos); if (-1 == ret) { return false; } else { beginPos += ret; head = back; } } return true; } //查看是否有进位 public static boolean isCarryOut(String a){ int len = a.length(); for (int i = 0; i < len; ++i){ if (a.charAt(i) != '9') return false; } return true; } // --------------------------------------------------------------------------// //rec[]数组记录了每种长度的起始位置:比如两位起始于10，一位起始于1 public static void genBeginPos(){ BigInteger [] len = new BigInteger[ms]; BigInteger ten = BigInteger.ONE; len[0] = BigInteger.ZERO; rec[0] = BigInteger.ZERO; rec[1] = BigInteger.ONE; for (int i = 1; i < ms; ++i){ len[i] = nine.multiply(ten); beginValue[i] = ten; ten = ten.multiply(BigInteger.valueOf(10)); } for (int i = 2; i < ms; ++i){ rec[i] = rec[i-1].add(len[i-1].multiply(BigInteger.valueOf(i-1))); } } public static BigInteger getPos(String value){ int len = value.length(); BigInteger bValue = beginValue[len]; BigInteger from = rec[len]; BigInteger ret = (new BigInteger(value)).subtract(bValue); ret = ret.multiply(BigInteger.valueOf(len)); ret = from.add(ret); return ret; } public static void setMinLength(BigInteger a){ if (minLength.compareTo(negOne) == 0 || minLength.compareTo(a) > 0) { minLength = a; } } public static boolean isAllZero(String a){ for (int i = 0; i < a.length(); ++i){ if (a.charAt(i) != '0') return false; } return true; } public static void main(String[] args) throws Exception { genBeginPos(); BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String line; while ((line = cin.readLine()) != null){ if (isAllZero(line)) { line = "1" + line; BigInteger pos = getPos(line); pos = pos.add(BigInteger.ONE); System.out.println(pos.toString()); continue; } final int line_len = line.length(); /** * 分段时有如下考虑：(假设除头部head,余下部分为next). * 注意在分段过程中next的开头不能是以0字符开头。 * 1、每段的长度都比字符串长度(len)要小 * 这里需要分两种情况处理。 * A、头部不能取到分段长度: * 这里又分两种情况： * a、next部分可以取到分段长度，这个易于处理， * b、next部分不可以取到分段长度，这个不易处理。 * B、头部可以取到分段长度：比如111213，当分段长度为2时，头部可以取到11那么后面的数就顺理成章地推导下去了。 * 2、每个分段的长度为len,但是头部与尾部均不足len,拼起来才足够. * 这里需要推导出头部的整个数字，比如99|15,按四位数分的话我们需要推出头部数为14[9915]00。从1499与1500中取了中间四位。 * 3、整数字符串就是一个数(相当于第二种情况中头部长度为len)，不可拆分比如100, 1000, * 这时也不可以以0做为开头。 */ boolean have_find_min_length = false; int segSize = 1; minLength = negOne; for (segSize = 1; segSize < line_len; ++segSize){ String head = new String(""), next = new String(""); int head_len = 0, next_len = 0; minLength = negOne; //Condition 1.A for (int headSize = 1; headSize < segSize; ++headSize){ head = line.substring(0, headSize); head_len = head.length(); next = line.substring(headSize, line_len); next_len = next.length(); if (next_len > 0 && next.charAt(0) == '0') continue; if (next_len >= segSize){ //Condition 1.A.a String value = next.substring(0, segSize); String front = getFrontInt(value); //这里利用next[0~segSize)取得的front值与head进行比较 boolean ret = true; for (int i = head.length() - 1, j = front.length() - 1; i >= 0 && j >= 0; --i, --j){ if (head.charAt(i) != front.charAt(j)){ ret = false; break; } } if (false == ret){ //比较失败，直接进行下轮测试。 continue; } else { //比较成功，那么从next开始，向后比较。 boolean bNextEqualToSegmentSize = stringCompareBySegSize(next, segSize); if (false == bNextEqualToSegmentSize){ continue; } else { //这里需要推出完整的头值。 String beginValue = getFrontInt(value); BigInteger pos = getPos(beginValue); pos = pos.add(BigInteger.valueOf(beginValue.length() - head.length())); setMinLength(pos); //System.out.println("C 1.A.a Next larger than segSize: value = " + beginValue + " pos = " + pos.toString()); //System.out.println("Segment Size = " + segSize); } } } else { //Condition 1.A.b String front_head = next.substring(0, segSize - head_len); boolean bCarryOut = isCarryOut(head); String front_part_value = ""; if (bCarryOut){ front_part_value = getFrontInt(front_head); } else { front_part_value = front_head; } String frontValue = ""; if (front_part_value.compareTo("0") != 0){ frontValue = front_part_value + head; } else { frontValue = head; } String NextValue = getNextInt(frontValue); boolean bIsEqual = true; for (int i = 0, j = 0; i < NextValue.length() && j < next_len; ++i, ++j){ if (NextValue.charAt(i) != next.charAt(j)){ bIsEqual = false; break; } } if (bIsEqual){ String beginValue = frontValue; BigInteger pos = getPos(beginValue); pos = pos.add(BigInteger.valueOf(beginValue.length() - head.length())); setMinLength(pos); //System.out.println("C 1.A.b Next small than segSize: value = " + beginValue + " pos = " + pos.toString()); //System.out.println("Segment Size = " + segSize); } else { continue; } } } //Condition 1.B if (line.charAt(segSize) != '0' && line.charAt(0) != '0'){ boolean bHeadEqualToSegmentSize = stringCompareBySegSize(line, segSize); if (bHeadEqualToSegmentSize){ String beginValue = line.substring(0, segSize); BigInteger pos = getPos(beginValue); setMinLength(pos); //System.out.println("C1.B head equal to segSize: value = " + beginValue + " pos = " + pos.toString()); } } if (minLength.compareTo(negOne) != 0){ have_find_min_length = true; break; } } //Condition 2 if (true == have_find_min_length){ System.out.println(minLength.toString()); continue; } for (int headSize = 1; headSize < line_len && have_find_min_length == false; ++ headSize){ String head = line.substring(0, headSize); final int head_len = head.length(); String next = line.substring(headSize, line_len); final int next_len = next.length(); if (next_len > 0 && next.charAt(0) == '0') continue; boolean bCarryOut = isCarryOut(head); String beginValue = ""; if (bCarryOut) { beginValue = getFrontInt(next) + head; } else { beginValue = next + head; } BigInteger pos = getPos(beginValue); pos = pos.add(BigInteger.valueOf(beginValue.length() - head.length())); setMinLength(pos); //System.out.println("C2 add equal to line_len: value = " + beginValue + " pos = " + pos.toString()); //System.out.println("Segment Size = " + line_len); } //Condition 3 if (line_len > 0 && line.charAt(0) != '0'){ String beginValue = line; BigInteger pos = getPos(beginValue); setMinLength(pos); //System.out.println("C3 hole length: front = " + beginValue + " pos = " + pos.toString()); //System.out.println("Segment Size = " + line_len); } //最后的输出 if (minLength.compareTo(negOne) != 0){ //System.out.println("Find min length"); System.out.println(minLength.toString()); continue; } } } } -
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<sstream>using namespace std;
string hahawodabiao;
string inttostring(int a){
string b;
stringstream ss;
ss << a;
ss >> b;
return b;
}void makestring(){
for(int i = 1;i <= 150000; i++){
hahawodabiao += inttostring(i);
}
}int main()
{
makestring();
string a;
cin>>a;
cout<<hahawodabiao.find(a)+1;
return 0;
} -
0
感觉没几个好的
```cpp
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
class BigNum{
private:
enum {blen=4,MAX=53,base=10000};
int len;
int a[MAX];
public:
explicit BigNum(int num=0);
BigNum(const BigNum& b);
BigNum(int x,int b);
explicit BigNum(string num);
BigNum operator+ (const BigNum& b)const;
BigNum operator+ (const int b)const;
BigNum operator- (const BigNum& b)const;
BigNum operator- (const int b)const;
BigNum operator* (const BigNum& b)const;
BigNum operator* (const int b)const;
const int& operatorconst;
int& operator;
bool operator< (const BigNum& b)const;
bool operator> (const BigNum& b)const;
bool operator== (const BigNum& b)const;
bool operator!= (const BigNum& b)const;
string toString()const;
friend ostream& operator<< (ostream& os,const BigNum& a);
};
BigNum::BigNum(int num){
if (num==0){
len=0;
memset(a,0,sizeof(a));
return;
}
len=0;
memset(a,0,sizeof(a));
while (num>0){
a[len++]=num%base;
num/=base;
}
}
BigNum::BigNum(int x,int b){ // x*10^b
if (x==0){
len=0;
memset(a,0,sizeof(a));
return;
}
len=(b+1)/blen+1;
if ((b+1)%blen==0) len--;
memset(a,0,sizeof(a));
int i=b%blen,j=1;
while (i>0){
j*=10;
i--;
}
a[len-1]=x*j;
}
BigNum::BigNum(string num){
const int nn[blen]={1,10,100,1000};
if (num==string(num.size(),'0')){
len=0;
memset(a,0,sizeof(a));
return;
}
memset(a,0,sizeof(a));
len=0;
for (int i=0;i<int(num.size());i++){
if (i%blen==0) len++;
a[len-1]+=(num[num.size()-i-1]-'0')*nn[i%blen];
}
}
BigNum::BigNum(const BigNum& b){
len=b.len;
memcpy(a,b.a,sizeof(b.a));
}
int& BigNum::operator[](int i){
return a[i];
}
const int& BigNum::operator[](int i)const{
return a[i];
}
BigNum BigNum::operator+(const BigNum& b)const{
BigNum c=BigNum();
int k=0;
c.len=max(len,b.len);
for (int i=0;i<c.len;i++){
c[i]=(a[i]+b[i]+k)%base;
k=(a[i]+b[i]+k)/base;
}
while (k>0){
c[c.len++]=k%base;
k/=base;
}
return c;
}
BigNum BigNum::operator+(const int b)const{
BigNum c=*this;
int i=0;
c[0]+=b;
while (c[i]>=base){
c[i+1]+=c[i]/base;
c[i]%=base;
i++;
}
while (c[c.len]>0) c.len++;
return c;
}
BigNum BigNum::operator-(const BigNum& b)const{ //ensure that a>b
BigNum c=BigNum();
c.len=max(len,b.len);
int k=0;
for (int i=0;i<len;i++)
if (a[i]-b[i]-k>=0)
c[i]=a[i]-b[i]-k;
else{
k++;
c[i]=a[i]-b[i]+base;
}
while (c.len>0 && c[c.len-1]==0) c.len--;
return c;
}
BigNum BigNum::operator-(const int b)const{
BigNum c=*this;
int i=0;
c[i]-=b;
while (c[i]<0){
c[i+1]--;
c[i]+=base;
i++;
}
while (c.len>0 && c[c.len-1]==0) c.len--;
return c;
}
BigNum BigNum::operator*(const BigNum& b)const{
BigNum c=BigNum();
c.len=0;
int t;
for (int j=0;j<b.len;j++)
for (int i=0;i<len;i++){
t=c[i+j]+a[i]*b[j];
c[i+j]=t%base;
c[i+j+1]+=t/base;
if (c[i+j]>0) c.len=max(c.len,i+j);
if (c[i+j+1]>0) c.len=max(c.len,i+j+1);
}
c.len++;
return c;
}
BigNum BigNum::operator*(const int b)const{
BigNum c=BigNum();
c.len=len;
int k=0;
for (int i=0;i<len;i++){
c[i]=(a[i]*b+k)%base;
k=(a[i]*b+k)/base;
}
while (k>0){
c[c.len++]=k%base;
k/=base;
}
return c;
}
bool BigNum::operator< (const BigNum& b)const{
if (len<b.len) return true;
if (len>b.len) return false;
for (int i=len-1;i>=0;i--)
if (a[i]<b[i]) return true;
else if (a[i]>b[i]) return false;
return false;
}
bool BigNum::operator> (const BigNum& b)const{
if (len>b.len) return true;
if (len<b.len) return false;
for (int i=len-1;i>=0;i--)
if (a[i]>b[i]) return true;
else if (a[i]<b[i]) return false;
return false;
}
bool BigNum::operator== (const BigNum& b)const{
if (len!=b.len) return false;
for (int i=0;i<len;i++)
if (a[i]!=b[i]) return false;
return true;
}
bool BigNum::operator!= (const BigNum& b)const{
return !(*this==b);
}
ostream& operator<< (ostream& os,const BigNum& a){
int i=a.len-1;
os << a[i];
for (i-=1;i>=0;i--){
if (a[i]<a.base/10) os << '0';
if (a[i]<a.base/100) os << '0';
if (a[i]<a.base/1000) os << '0';
os << a[i];
}
return os;
}
string BigNum::toString()const{
int i=len-1;
char s[MAX*blen+1];
sprintf(s,"%d",a[i]);
for (i-=1;i>=0;i--)
{
if (a[i]<base/10) sprintf(s+strlen(s),"%d",0);
if (a[i]<base/100) sprintf(s+strlen(s),"%d",0);
if (a[i]<base/1000) sprintf(s+strlen(s),"%d",0);
sprintf(s+strlen(s),"%d",a[i]);
}
return string(s,s+strlen(s));
}
BigNum cal(BigNum a){
string s=a.toString();
int x=s[0]-'0';
int b=s.size();
if (b==1) return BigNum(x);
BigNum tmp;
for (int i=0;i<b-1;i++)
tmp=tmp+BigNum(9,i)*(i+1);
tmp=tmp+(a-BigNum(1,b-1)+1)*b;
return tmp;
}
int get(string s1,string s2){
int i,ans=0;
for (i=1;i<=int(min(s1.size(),s2.size()));i++){
string ss1=s1.substr(0,i);
string ss2=s2.substr(s2.size()-i,i);
if (ss1==ss2) ans=i;
}
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,len,n,k,slen;
bool ff;
BigNum ans,tmp;
string s,ss,st,sp,s1,s2;
cin >> s;
n=s.size();
if (s==string(n,'0')){
ans=cal(BigNum(1,n))-n+1;
cout << ans << endl;
return 0;
}
if (n==1){
cout << s << endl;
return 0;
}
for (len=1;len<n;len++)
for (i=0;i+len-1<n;i++){
j=i+len-1;
if (j>=n) continue;
ff=true;
st=s.substr(i,len);
if (st[0]=='0') continue;
if (i>0){
sp=(BigNum(st)-1).toString();
ss=s.substr(0,i);
if (ss.size()>sp.size()) continue;
if (sp.rfind(ss)!=sp.size()-ss.size()) ff=false;
}
if (!ff) continue;
slen=len;
for (k=j+1;k+slen-1<n;k+=slen){
st=(BigNum(st)+1).toString();
slen=st.size();
if (k+slen-1>=n) break;
if (st!=s.substr(k,slen)){
ff=false;
break;
}
}
if (!ff) continue;
if (k<n){
st=(BigNum(st)+1).toString();
ss=s.substr(k,n-k);
if (st.find(ss)!=0) ff=false;
}
if (ff){
st=s.substr(i,len);
ans=cal(BigNum(st))-i-st.size()+1;
goto ppp;
}
}
ppp:
for (i=0;i<n;i++){
st=s.substr(0,i);
st=(BigNum("1"+st)+1).toString();
st=st.substr(1,st.size()-1);
s2=s.substr(i,n-i);
k=get(st,s2);
if (k>=int(s2.size())) continue;
st=s.substr(i,n-i-k)+st;
if (st[0]=='0') continue;
tmp=cal(BigNum(st)-1)-i+1;
if (ans==BigNum(0)) ans=tmp;
else if (tmp<ans) ans=tmp;
}
if (s[0]>'0'){
tmp=cal(BigNum(s))-n+1;
if (ans==BigNum(0)) ans=tmp;
else if (tmp<ans) ans=tmp;
}
else{
s="1"+s;
tmp=cal(BigNum(s))-n;
if (ans==BigNum(0)) ans=tmp;
else if (tmp<ans) ans=tmp;
}
cout<< ans << endl;
} -
0
var a:string;
s:array[1..1700000000] of char;
b,c,d,e:longint;
procedure fty(b:longint);
var zh:string;
begin
str(b,zh);
for c:=1+d to d+length(zh) do
s[c]:=zh[c-d];
d:=d+length(zh);
end;begin
readln(a);
for b:=1 to 1000100 do fty(b);
for b:=1 to length(s)-length(a)+1 do
if s[b]=a[1] then
for c:=b to length(a)+b-1 do
begin
if s[c]<>a[c-b+1] then break;
if (c=length(a)+b-1) and (s[c]=a[c-b+1]) then begin
writeln(b);exit;end;
end;
end.230分。。。烦。。。
-
0
把第一个数根据后面的数分情况补齐，然后判断整个字符串是否合法
#include<iostream> #include<string> using namespace std; string s; int a[300][305]={0}; int flag=1; int kk=0; //x[0~(n-m)]=s[n~m] int getNum(int x[],int m,int n){ for(int i=n;i>=m;--i) x[n-i]=s[i]-'0'; } void print(int x[]){ int i; for(i=300;i>=0;i--) if(x[i]!=0) break; while(i>=0) cout<<x[i--]; cout<<endl; } //打印补齐后的第一个数 void print(int l){ for(int i=1;i<=l;++i) cout<<s[i]; cout<<endl; } //x=x+t void add(int x[],int t){ x[0]+=t; int i=0; while(x[i]>=10) { x[i+1]+=x[i]/10; x[i]%=10; i++; } } //x=x-t void sub(int x[],int t){ x[0]-=t; int i=0; while(x[i]<0) { x[i]+=10; x[i-1]-=1; i++; } } //前后数位数都足够 bool check(int i,int j,int m,int n){ if(s[i]=='0'||s[m]=='0') return false; int x[305]={0},y[305]={0}; getNum(x,i,j); getNum(y,m,n); add(x,1); for(int d=0;d<=300;d++) if(x[d]!=y[d]) return false; return true; } //后一个数位数不够，只判断后一个数与前一个数对应的位数是否相等 bool tailCheck(int i,int j,int m,int n){ if(s[i]=='0'||s[m]=='0') return false; int x[305]={0},y[305]={0}; getNum(x,i,j); getNum(y,m,n); add(x,1); int d1=300,d2=300; while(x[d1]==0) d1--; while(y[d2]==0) d2--; while(d1>=0&&d2>=0) { if(x[d1]!=y[d2]) return false; d1--;d2--; } return true; } //判断第一个数的位数是否能为l bool find(int l){ int i,j,m,n; i=1;j=l;m=j+1;n=j+l; if(j==s.size()-1&&s[i]=='0') return false; while(true) { if(j>=s.size()-1) return true; if(n>=s.size()-1) {n=s.size()-1;if(!tailCheck(i,j,m,n)) return false;} else if(!check(i,j,m,n)) //前一个数和后一个数的位数都为l { if(!check(i,j,m,n+1)) //前一个数位数为l,后一个数位数为l+1 return false; else {l+=1;n+=1;} } i=m; j=n; m=j+1; n=j+l; } return true; } void Multiply(int x[],int y){ for(int i=0;i<=300;++i) x[i]*=y; for(int i=0;i<=300;++i) if(x[i]>9) { x[i+1]+=x[i]/10; x[i]%=10; } } void add(int x[],int y[]){ for(int i=0;i<=300;++i) x[i]+=y[i]; int i=0; while(x[i]>=10) { x[i+1]+=x[i]/10; x[i]%=10; i++; } } bool comp(int x[],int y[]){ for(int i=300;i>=0;--i) if(x[i]<y[i]) return true; else if(x[i]>y[i]) return false; return false; } void getAns(int finalAns[],int l,int k){ int x[305]={0},ans[305]={0}; getNum(x,1,l); x[l-1]-=1; Multiply(x,l); for(int i=0;i<=300;++i) ans[i]=a[l-1][i]+x[i]; ans[0]+=1+k+kk; for(int i=0;i<=300;++i) if(ans[i]>9) { ans[i+1]+=ans[i]/10; ans[i]%=10; } if(flag==1||comp(ans,finalAns)) for(int i=0;i<=300;++i) finalAns[i]=ans[i]; } //判断数组是否为1000....0000的形式 bool Equal1000(int x[]){ int tot=0; for(int i=0;i<=300;++i) if(x[i]!=0) tot++; if(tot>1) return false; return true; } //判断字符串是否为全0 bool Equal000(string s1){ for(int i=0;i<s1.size();++i) if(s1[i]!='0') return false; return true; } int main() { //a[i]表示所有位数<=i的字符串长度和 for(int i=1;i<=200;++i) { a[i][i-1]=9; Multiply(a[i],i); add(a[i],a[i-1]); } int finalAns[305]={0}; flag=1; string s1; cin>>s1; //如果字符串=000...0,则在最前面加上0,令kk=1,最后的答案要减去kk if(Equal000(s1)) {s1="1"+s1;kk=1;} //l为字符串中第一个数的位数 //k表示字符串中第一个字符是第一个数的第K+1位，k<l for(int l=1;l<=s1.size();++l) for(int k=0;k<l;++k) { s=" "+s1;string s2=""; if(k==0) { if(find(l)) {getAns(finalAns,l,k);flag=0;} } //如果K!=0,则补齐第一个数的前k位 if(k!=0) { int x[305]={0}; getNum(x,l-k+1,l-k+k); //1.直接把第l-k+1至l-k+k之间的数补齐第一个数的前k位 s2=""; int i=k-1; while(i>=0) s2+=x[i--]+'0'; s=" "+s2+s1; if(find(l)) {getAns(finalAns,l,k);flag=0;} //2.如果第l-k+1至l-k+k之间数的形式是10....000,也可以用99....999补齐第一个数的前k位 if(Equal1000(x)) { s2=""; i=k-1; while(i>=0) {s2+='9';i--;} s=" "+s2+s1; if(find(l)) {getAns(finalAns,l,k);flag=0;} } //3.用第l-k+1至l-k+k之间的数减去1,补齐第一个数的前k位 sub(x,1); i=k-1; s2=""; while(i>=0) s2+=x[i--]+'0'; s=" "+s2+s1; if(find(l)) {getAns(finalAns,l,k);flag=0;} } } print(finalAns); // system("pause"); } -
0
非常复杂的一道题……强行AC
```c++
#include <string>
#include <iostream>
#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
struct BigInt
{
static const int Base = 100000000;
static const int Width = 8;
vector <int> s;
BigInt(long long num = 0)
{
*this = num;
}
BigInt(const string &b)
{
*this = b;
}
BigInt operator = (long long num)
{
s.clear();
do
{
s.push_back(num % Base);
num /= Base;
} while (num > 0);
return *this;
}
BigInt operator = (const string& str)
{
s.clear();
int x, len = (str.length() - 1) / Width + 1;
for (int i = 0; i < len; i++)
{
int end = str.length() - i * Width;
int start = max(0, end - Width);
sscanf(str.substr(start, end - start).c_str(), "%d", &x);
s.push_back(x);
}
return *this;
}
BigInt operator + (const BigInt &b) const
{
BigInt res;
res.s.clear();
for (int i = 0, count = 0;; i++)
{
if (count == 0 && i >= s.size() && i >= b.s.size()) break;
int x = count;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
res.s.push_back(x % Base);
count = x / Base;
}
return res;
}
BigInt operator * (const int times) const
{
BigInt res;
res.s.clear();
for (int i = 0, carry = 0; ; i++)
{
if (carry == 0 && i >= s.size()) break;
long long x = carry;
if (i < s.size()) x += (long long)times * s[i];
res.s.push_back(x % Base);
carry = x / Base;
}
return res;
}friend ostream& operator << (ostream &out, const BigInt& x)
{
out << x.s.back();
for (int i = x.s.size() - 2; i >= 0; i--)
{
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for (int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
};void find_bit(string num,int blank)
{
int size = num.size();
BigInt ans = 1, count = 9;
for (int i = 1; i < size; i++)
{
ans = ans + (count * i);
count = count * 10;
}if (num[0] > '0')num[0]--;
if (num[0]=='0' && num !="0") num.erase(num.begin());ans = ans + BigInt(num) * size;
ans = ans + BigInt(blank);
cout << ans << endl;
}
struct node
{
string num;
int blank;
node(string num, int blank):num(num),blank(blank){
}
bool operator < (const node &b)const
{
if (num.size() < b.num.size()) return true;
if (num.size() > b.num.size()) return false;
if (num < b.num) return true;
if (num > b.num) return false;
if (blank < b.blank) return true;
return false;
}
};set <node> ansSet;
string& operator ++ (string &a)
{
int size = a.size();
int carry = 1;
for (int i = size - 1; i>=0; i--)
{
int x = carry + a[i] - '0';
a[i] = x % 10 + '0';
carry = x/10;
}
if (carry > 0)
{
a = "1";
for (int i=0; i < size; i++) a+="0";
}
return a;
}string& operator -- (string &a)
{
int size = a.size();
int carry = -1;
for (int i = size - 1; i >= 0; i--)
{
int x = carry + a[i] - '0';
carry = 0;
if (x < 0)
{
carry = -1;
x += 10;
}
a[i] = x + '0';
}
if (a[0] == '0' && a.size()!=1) a.erase(0,1);
return a;
}bool check(string &a, string &b,int pos = 0, int blank = 0)
{
for (int i = 0, j = pos + blank;i < a.size() && j < b.size(); i++,j++)
{
if (a[i] != b[j]) return false;
}
return true;
}bool check_through(string a,string &b, int pos)
{
for (;pos < b.size(); pos += a.size())
{
++a;
if (!check(a,b,pos)) return false;
}
return true;
}bool all(string &a,char c)
{
for (int i = 0; i < a.size(); i++)
if (a[i]!=c) return false;
return true;
}
int main()
{
string s;
cin >> s;
if (all(s,'0'))
{
s = "1" +s;
find_bit(s,1);
}
else for (int len = 1; len <= s.size(); len++)
{
ansSet.clear();
for (int blank = 0; blank < len; blank++)
{
string a,num="";
a.assign(s,0,len-blank);
int p = len - blank;
if (all(a,'9'))
{
string zero;
zero.assign(len - blank, '0');
string temp = "1";//1000000000
temp.append(len, '0');
if (check(temp,s,p))
{
num.assign(len, '9');
}
else if (s[p]!='0'&&check(zero,s,p,blank))
{
num.assign(s,p,blank);
--num;
num += a;
}
}
else
{
string temp = a;
++temp;
if (s[p]!='0'&&check(temp,s,p,blank))
{
num.assign(s,p,blank);
num += a;
}
}
/* test
printf("len = %d, blank = %d, p = %d, num=",len,blank,p);
cout << num << endl;
// test*/if (num != "" && num[0]!='0'&& check_through(num,s,p))
ansSet.insert(node(num,blank));
}
if (!ansSet.empty())
{
// cout << ansSet.begin()->num << endl;
string num = ansSet.begin()->num;
int blank = ansSet.begin()->blank;
if (all(num,'0')){
num = "1" +num;
blank = 1;
}
find_bit(num,blank);break;
}
}
}
``` -
0
测试数据 #0: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 3388 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #8: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
测试数据 #9: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #10: Accepted, time = 15 ms, mem = 3396 KiB, score = 10
测试数据 #11: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #12: WrongAnswer, time = 15 ms, mem = 3392 KiB, score = 0
测试数据 #13: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #14: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #15: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #16: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
测试数据 #17: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #18: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #19: Accepted, time = 0 ms, mem = 3396 KiB, score = 10
测试数据 #20: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #21: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
测试数据 #22: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
测试数据 #23: WrongAnswer, time = 15 ms, mem = 3392 KiB, score = 0
测试数据 #24: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #25: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
测试数据 #26: WrongAnswer, time = 15 ms, mem = 3384 KiB, score = 0
测试数据 #27: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
测试数据 #28: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
测试数据 #29: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
测试数据 #30: WrongAnswer, time = 15 ms, mem = 3384 KiB, score = 0
测试数据 #31: Accepted, time = 0 ms, mem = 3392 KiB, score = 10
测试数据 #32: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
测试数据 #33: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
测试数据 #34: WrongAnswer, time = 15 ms, mem = 3392 KiB, score = 0
测试数据 #35: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
测试数据 #36: WrongAnswer, time = 0 ms, mem = 3384 KiB, score = 0
测试数据 #37: WrongAnswer, time = 15 ms, mem = 3388 KiB, score = 0
测试数据 #38: WrongAnswer, time = 0 ms, mem = 3388 KiB, score = 0
测试数据 #39: Accepted, time = 15 ms, mem = 3392 KiB, score = 10
WrongAnswer, time = 375 ms, mem = 3396 KiB, score = 220
代码
#include<bits/stdc++.h>
using namespace std;
char a[200001],b[200];
string s;
int i,p[200],j,n,m;
int makea(int num,int x) {
string s1;
int k,t,i;
t=0;
k=num;
while (k>0) {
t++;
s1[t]=k%10+'0';
k=k/10;
}
for (i=t; i>0; i--)
a[x+t-i]=s1[i];
n=x+t;
if (n<200000)
makea(num+1,n);
}
int main() {
cin>>s;
for (i=1; i<=s.length(); i++)
b[i]=s[i-1];
m=s.length();
n=1;
makea(1,n);
j=0;
p[1]=0;
for (i=2; i<=m; i++) {
while (j>0&&b[j+1]!=b[i]) j=p[j];
if (b[j+1]==b[i]) j++;
p[i]=j;
}
j=0;
for (i=1; i<=n; i++) {
while (j>0&&b[j+1]!=a[i]) j=p[j];
if (b[j+1]==a[i]) j++;
if (j==m) {
cout<<i-m+1<<endl;
break;
}
}
}
这就是裸地KMP的死法。。。22个点，不然就爆了。。。 -
0
//算是打表吧！
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
using namespace std;void makenext(const char p[],int next[])//不理解就自己代一代
{
int q,k;
int m=strlen(p);
next[0]=0;
for(q=1,k=0;q<m;++q)
{
while(k>0&&p[q]!=p[k])
k=next[k-1];
if(p[q]==p[k])
{
k++;//查找与前面有相同的，即前后缀有相同的元素，于是就加1
}
next[q]=k;
}
}int kmp(const char t[],const char p[],int next[])
{
int n,m;
int i,q;
n=strlen(t);
m=strlen(p);
makenext(p,next);
for(i=0,q=0;i<n;++i)
{
while(q>0&&p[q]!=t[i])
q=next[q-1];
if(p[q]==t[i])
{
q++;
}
if(q==m)
printf("%d\n",(i-m+2));
}
}int main()
{
int next[20]={0};
char T[300]={
49,50,51,52,53,54,55,56,57,49,48,49,49,49,50,49,51,49,52,
49,53,49,54,49,55,49,56,49,57,50,48,50,49,50,50,50,51,50,
52,50,53,50,54,50,55,50,56,50,57,51,48,51,49,51,50,51,51,
51,52,51,53,51,54,51,55,51,56,51,57,
52,48,52,49,52,50,52,51,52,52,52,53,52,54,52,55,52,56,52,57,
53,48,53,49,53,50,53,51,53,52,53,53,53,54,53,55,53,56,53,57,
54,48,54,49,54,50,54,51,54,52,54,53,54,54,54,55,54,56,54,57,
55,48,55,49,55,50,55,51,55,52,55,53,55,54,55,55,55,56,53,57,
};
char P[30];
cin.getline(P,30);
int l=strlen(P);
//for(int i=0;i<l;i++)printf("%d ",P[i]);
kmp(T,P,next);
return 0;
} -
0
tootal (hzq) LV 9 @ 2016-07-13 14:26:14
暴力做法：只能过22个点
~~~
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
string A,s,t;
int main(){
for(int i=1;i<=10000;i++){
stringstream ss;
ss<<i;ss>>t;s+=t;
}
getline(cin,A);
cout<<s.find(A)+1<<endl;
return 0;
}
发几个c++的参考代码膜拜一下。Orz。
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; class BigNum{ private: enum {blen=4,MAX=53,base=10000}; int len; int a[MAX]; public: explicit BigNum(int num=0); BigNum(const BigNum& b); BigNum(int x,int b); explicit BigNum(string num); BigNum operator+ (const BigNum& b)const; BigNum operator+ (const int b)const; BigNum operator- (const BigNum& b)const; BigNum operator- (const int b)const; BigNum operator* (const BigNum& b)const; BigNum operator* (const int b)const; const int& operator[] (int i)const; int& operator[] (int i); bool operator< (const BigNum& b)const; bool operator> (const BigNum& b)const; bool operator== (const BigNum& b)const; bool operator!= (const BigNum& b)const; string toString()const; friend ostream& operator<< (ostream& os,const BigNum& a); }; BigNum::BigNum(int num){ if (num==0){ len=0; memset(a,0,sizeof(a)); return; } len=0; memset(a,0,sizeof(a)); while (num>0){ a[len++]=num%base; num/=base; } } BigNum::BigNum(int x,int b){ // x*10^b if (x==0){ len=0; memset(a,0,sizeof(a)); return; } len=(b+1)/blen+1; if ((b+1)%blen==0) len--; memset(a,0,sizeof(a)); int i=b%blen,j=1; while (i>0){ j*=10; i--; } a[len-1]=x*j; } BigNum::BigNum(string num){ const int nn[blen]={1,10,100,1000}; if (num==string(num.size(),'0')){ len=0; memset(a,0,sizeof(a)); return; } memset(a,0,sizeof(a)); len=0; for (int i=0;i<int(num.size());i++){ if (i%blen==0) len++; a[len-1]+=(num[num.size()-i-1]-'0')*nn[i%blen]; } } BigNum::BigNum(const BigNum& b){ len=b.len; memcpy(a,b.a,sizeof(b.a)); } int& BigNum::operator[](int i){ return a[i]; } const int& BigNum::operator[](int i)const{ return a[i]; } BigNum BigNum::operator+(const BigNum& b)const{ BigNum c=BigNum(); int k=0; c.len=max(len,b.len); for (int i=0;i<c.len;i++){ c[i]=(a[i]+b[i]+k)%base; k=(a[i]+b[i]+k)/base; } while (k>0){ c[c.len++]=k%base; k/=base; } return c; } BigNum BigNum::operator+(const int b)const{ BigNum c=*this; int i=0; c[0]+=b; while (c[i]>=base){ c[i+1]+=c[i]/base; c[i]%=base; i++; } while (c[c.len]>0) c.len++; return c; } BigNum BigNum::operator-(const BigNum& b)const{ //ensure that a>b BigNum c=BigNum(); c.len=max(len,b.len); int k=0; for (int i=0;i<len;i++) if (a[i]-b[i]-k>=0) c[i]=a[i]-b[i]-k; else{ k++; c[i]=a[i]-b[i]+base; } while (c.len>0 && c[c.len-1]==0) c.len--; return c; } BigNum BigNum::operator-(const int b)const{ BigNum c=*this; int i=0; c[i]-=b; while (c[i]<0){ c[i+1]--; c[i]+=base; i++; } while (c.len>0 && c[c.len-1]==0) c.len--; return c; } BigNum BigNum::operator*(const BigNum& b)const{ BigNum c=BigNum(); c.len=0; int t; for (int j=0;j<b.len;j++) for (int i=0;i<len;i++){ t=c[i+j]+a[i]*b[j]; c[i+j]=t%base; c[i+j+1]+=t/base; if (c[i+j]>0) c.len=max(c.len,i+j); if (c[i+j+1]>0) c.len=max(c.len,i+j+1); } c.len++; return c; } BigNum BigNum::operator*(const int b)const{ BigNum c=BigNum(); c.len=len; int k=0; for (int i=0;i<len;i++){ c[i]=(a[i]*b+k)%base; k=(a[i]*b+k)/base; } while (k>0){ c[c.len++]=k%base; k/=base; } return c; } bool BigNum::operator< (const BigNum& b)const{ if (len<b.len) return true; if (len>b.len) return false; for (int i=len-1;i>=0;i--) if (a[i]<b[i]) return true; else if (a[i]>b[i]) return false; return false; } bool BigNum::operator> (const BigNum& b)const{ if (len>b.len) return true; if (len<b.len) return false; for (int i=len-1;i>=0;i--) if (a[i]>b[i]) return true; else if (a[i]<b[i]) return false; return false; } bool BigNum::operator== (const BigNum& b)const{ if (len!=b.len) return false; for (int i=0;i<len;i++) if (a[i]!=b[i]) return false; return true; } bool BigNum::operator!= (const BigNum& b)const{ return !(*this==b); } ostream& operator<< (ostream& os,const BigNum& a){ int i=a.len-1; os << a[i]; for (i-=1;i>=0;i--){ if (a[i]<a.base/10) os << '0'; if (a[i]<a.base/100) os << '0'; if (a[i]<a.base/1000) os << '0'; os << a[i]; } return os; } string BigNum::toString()const{ int i=len-1; char s[MAX*blen+1]; sprintf(s,"%d",a[i]); for (i-=1;i>=0;i--) { if (a[i]<base/10) sprintf(s+strlen(s),"%d",0); if (a[i]<base/100) sprintf(s+strlen(s),"%d",0); if (a[i]<base/1000) sprintf(s+strlen(s),"%d",0); sprintf(s+strlen(s),"%d",a[i]); } return string(s,s+strlen(s)); } BigNum cal(BigNum a){ string s=a.toString(); int x=s[0]-'0'; int b=s.size(); if (b==1) return BigNum(x); BigNum tmp; for (int i=0;i<b-1;i++) tmp=tmp+BigNum(9,i)*(i+1); tmp=tmp+(a-BigNum(1,b-1)+1)*b; return tmp; } int get(string s1,string s2){ int i,ans=0; for (i=1;i<=int(min(s1.size(),s2.size()));i++){ string ss1=s1.substr(0,i); string ss2=s2.substr(s2.size()-i,i); if (ss1==ss2) ans=i; } return ans; } int main(){ //freopen("in.txt","r",stdin); int i,j,len,n,k,slen; bool ff; BigNum ans,tmp; string s,ss,st,sp,s1,s2; cin >> s; n=s.size(); if (s==string(n,'0')){ ans=cal(BigNum(1,n))-n+1; cout << ans << endl; return 0; } if (n==1){ cout << s << endl; return 0; } for (len=1;len<n;len++) for (i=0;i+len-1<n;i++){ j=i+len-1; if (j>=n) continue; ff=true; st=s.substr(i,len); if (st[0]=='0') continue; if (i>0){ sp=(BigNum(st)-1).toString(); ss=s.substr(0,i); if (ss.size()>sp.size()) continue; if (sp.rfind(ss)!=sp.size()-ss.size()) ff=false; } if (!ff) continue; slen=len; for (k=j+1;k+slen-1<n;k+=slen){ st=(BigNum(st)+1).toString(); slen=st.size(); if (k+slen-1>=n) break; if (st!=s.substr(k,slen)){ ff=false; break; } } if (!ff) continue; if (k<n){ st=(BigNum(st)+1).toString(); ss=s.substr(k,n-k); if (st.find(ss)!=0) ff=false; } if (ff){ st=s.substr(i,len); ans=cal(BigNum(st))-i-st.size()+1; goto ppp; } } ppp: for (i=0;i<n;i++){ st=s.substr(0,i); st=(BigNum("1"+st)+1).toString(); st=st.substr(1,st.size()-1); s2=s.substr(i,n-i); k=get(st,s2); if (k>=int(s2.size())) continue; st=s.substr(i,n-i-k)+st; if (st[0]=='0') continue; tmp=cal(BigNum(st)-1)-i+1; if (ans==BigNum(0)) ans=tmp; else if (tmp<ans) ans=tmp; } if (s[0]>'0'){ tmp=cal(BigNum(s))-n+1; if (ans==BigNum(0)) ans=tmp; else if (tmp<ans) ans=tmp; } else{ s="1"+s; tmp=cal(BigNum(s))-n; if (ans==BigNum(0)) ans=tmp; else if (tmp<ans) ans=tmp; } cout<< ans << endl; }#include<cstdio> #include<cstring> class BigNum{ public: BigNum(char *str,int _len){ memset(a,0,sizeof(a)); len=_len; for(int i=len-1;i>=0;i--) a[i]=(*str++)-'0'; } BigNum(int n){ memset(a,0,sizeof(a)); for(len=0;n;n/=10,len++) a[len]=n%10; } operator bool() { return len>0; } BigNum operator++(){ a[0]++; int i; for(i=0;i<len && a[i]>9;i++) { a[i]-=10; a[i+1]++; } if(i==len) { a[i]=1; len++; } return *this; } void inc() { a[0]++; for(int i=0;i<len && a[i]>9;i++) { a[i]-=10; a[i+1]++; } } friend BigNum operator+(BigNum a,BigNum b) { if(a.len<b.len) a.len=b.len; for(int i=0;i<a.len;i++) a.a[i]+=b.a[i]; a.ceil(); return a; } friend BigNum operator+(BigNum a,int b) { return a+(BigNum)b; } friend BigNum operator-(BigNum a,BigNum b) { for(int i=a.len-1;i>0;i--) { a.a[i]-=b.a[i]; a.a[i]--; a.a[i-1]+=10; } a.a[0]-=b.a[0]; a.ceil(); return a; } friend BigNum operator-(BigNum a,int b) { return a-(BigNum)b; } friend BigNum operator*(BigNum a,BigNum b) { BigNum c=0; c.len=a.len+b.len; for(int i=0;i<a.len;i++) for(int j=0;j<b.len;j++) c.a[i+j]+=a.a[i]*b.a[j]; c.ceil(); return c; } friend BigNum operator*(BigNum a,int b) { return a*(BigNum)b; } friend bool operator<(BigNum a,BigNum b) { if(a.len==b.len) { int i; for(i=a.len-1;i>0 && a.a[i]==b.a[i];i--); return a.a[i]<b.a[i]; } else return a.len<b.len; } friend bool find(BigNum a,char *str) { for(int i=a.len-1;i>=0 && *str;i--) if(a.a[i]!=(*str++)-'0') return false; return true; } void print() { for(int i=len-1;i>=0;i--) printf("%d",a[i]); printf("\n"); } int a[300],len; private: void ceil() { for(int i=0;i<len;i++) { a[i+1]+=a[i]/10; a[i]%=10; } len++; while(len && !a[len-1]) len--; } }; bool pd(char *a) { BigNum t=9,now=0; for(char *p=a;*p;p++,t=t*10+9) { if(*p!='0') return false; now=now*10+t; } now=now+2; now.print(); return true; } char a[210]; void work() { int len=strlen(a); BigNum t=0,now=0; if(pd(a)) return; for(int i=1;i<=len;i++,t=t*10+9) { now=now+t; BigNum ans=0; for(int j=0;j<i;j++) { if(a[j]=='0') continue; BigNum prev(a,j); prev.inc(); if(j>0 && !find(prev,a+i)) continue; char nn[210]; int k; for(k=0;k<i && a[j+k];k++) nn[k]=a[j+k]; for(;k<i;k++) nn[k]=prev.a[i-k-1]+'0'; BigNum n(nn,i),temp=n; int p; for(p=j+i;p<len && find(++n,a+p);p+=n.len); if(p>=len) { temp=(temp-1)*i-now-j+1; if(!ans || temp<ans) ans=temp; } } if(ans) { ans.print(); break; } } } int main() { while (scanf("%s",a) != EOF) { work(); } return 0; } -
0
Kenny10001 LV 7 @ 2016-05-19 16:58:13
-
0
测试数据 #0: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
测试数据 #1: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
测试数据 #2: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
测试数据 #3: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
测试数据 #4: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
测试数据 #5: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
测试数据 #6: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
测试数据 #7: Accepted, time = 828 ms, mem = 2628 KiB, score = 10
测试数据 #8: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
测试数据 #9: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
测试数据 #10: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
测试数据 #11: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
测试数据 #12: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
测试数据 #13: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
测试数据 #14: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
测试数据 #15: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
测试数据 #16: WrongAnswer, time = 796 ms, mem = 2632 KiB, score = 0
测试数据 #17: Accepted, time = 765 ms, mem = 2632 KiB, score = 10
测试数据 #18: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
测试数据 #19: Accepted, time = 796 ms, mem = 2632 KiB, score = 10
测试数据 #20: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
测试数据 #21: WrongAnswer, time = 765 ms, mem = 2628 KiB, score = 0
测试数据 #22: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
测试数据 #23: WrongAnswer, time = 781 ms, mem = 2628 KiB, score = 0
测试数据 #24: Accepted, time = 781 ms, mem = 2628 KiB, score = 10
测试数据 #25: WrongAnswer, time = 906 ms, mem = 2628 KiB, score = 0
测试数据 #26: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
测试数据 #27: WrongAnswer, time = 796 ms, mem = 2632 KiB, score = 0
测试数据 #28: WrongAnswer, time = 796 ms, mem = 2628 KiB, score = 0
测试数据 #29: WrongAnswer, time = 812 ms, mem = 2632 KiB, score = 0
测试数据 #30: WrongAnswer, time = 828 ms, mem = 2632 KiB, score = 0
测试数据 #31: Accepted, time = 843 ms, mem = 2632 KiB, score = 10
测试数据 #32: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
测试数据 #33: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
测试数据 #34: WrongAnswer, time = 781 ms, mem = 2632 KiB, score = 0
测试数据 #35: Accepted, time = 765 ms, mem = 2628 KiB, score = 10
测试数据 #36: WrongAnswer, time = 812 ms, mem = 2628 KiB, score = 0
测试数据 #37: WrongAnswer, time = 765 ms, mem = 2632 KiB, score = 0
测试数据 #38: WrongAnswer, time = 765 ms, mem = 2632 KiB, score = 0
测试数据 #39: Accepted, time = 781 ms, mem = 2632 KiB, score = 10
WrongAnswer, time = 31540 ms, mem = 2632 KiB, score = 220用的c++的string的.find()，，
生成一个字符串，，然后直接输出就好了，，
但是只有220，并不知道为什么
'''
c++#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<sstream>using namespace std;
string hahawodabiao;
string inttostring(int a){
string b;
stringstream ss;
ss << a;
ss >> b;
return b;
}void makestring(){
for(int i = 1;i <= 150000; i++){
hahawodabiao += inttostring(i);
}
}int main()
{
makestring();
string a;
cin>>a;
cout<<hahawodabiao.find(a)+1;
return 0;
}'''
-
0
const maxl = 2000; type bitnode = array[0..maxl+1]of longint; var len, c,n: longint; t : array[1..maxl]of shortint; best, a, b : bitnode; procedure init; var st : string[200]; i : longint; begin readln(st); len := length(st); for i := 1 to len do begin t[i] := ord(st[i])-48; end; end; procedure dec1(var a : bitnode); var i : longint; begin i := 1; while a[i] = 0 do begin a[i] := 9; inc(i); end; dec(a[i]); if (a[0] > 1) and (a[a[0]] = 0) then dec(a[0]); end; procedure inc1(var a : bitnode); var i : longint; begin i := 1; inc(a[i]); while a[i] = 10 do begin a[i] := 0; inc(i); inc(a[i]); end; if a[a[0]+1] <> 0 then inc(a[0]); end; function match(i : longint) : boolean; var j : longint; begin if a[0] < i then begin if t[1] <> 8 then exit(false); for j := 1 to a[0] do begin if t <> a[j] then exit(false); end; exit(true); end else begin for j := 1 to i do if t <> a[j] then exit(false); exit(true); end; end; function can(i : longint) : boolean; var j : longint; begin while i < len do begin inc1(b); j := i+1; while (j <= len) and (j-i <= b[0]) do begin if b[b[0]-j+i+1] <> t[j] then exit(false); inc(j); end; inc(i, b[0]); end; exit(true); end; procedure printnum(var a : bitnode); var i : longint; begin for i := a[0] downto 1 do write(a[i]); writeln; end; procedure mul(var a : bitnode); var b, i : longint; begin b := a[0]; for i := 1 to a[0] do a[i] := a[i]*b; for i := 1 to a[0] do begin inc(a, a[i] div 10); a[i] := a[i] mod 10; end; while a <> 0 do begin inc(i); a := a[i] div 10; a[i] := a[i] mod 10; end; a[0] := i; end; procedure minus(var a, b : bitnode); var i : longint; begin for i := 1 to a[0] do begin if a[i]-b[i] < 0 then begin dec(a); inc(a[i], 10); end; dec(a[i], b[i]); end; while (a[0] > 1) and (a[a[0]] = 0) do dec(a[0]); end; procedure print; var i : longint; tem : bitnode; begin dec1(best); i := best[0]-1; mul(best); fillchar(tem, sizeof(tem), 0); while tem[0] < i do begin inc(tem[0]); tem[tem[0]] := 9; minus(best, tem); end; inc1(best); for i := 1 to c do inc1(best); printnum(best); halt; end; function bigger(var a, b : bitnode): boolean; var i : longint; begin if a[0] > b[0] then exit(true); if a[0] < b[0] then exit(false); for i := a[0] downto 1 do begin if a[i] > b[i] then exit(true); if a[i] < b[i] then exit(false); end; exit(false); end; procedure main; var l, i, j, tem : longint; flag : boolean; begin flag := true; for i := 1 to len do if t[i] <> 0 then begin flag := false; break; end; if flag then begin best[0] := len+1; best[best[0]] := 1; c := 1; print; end; for i := 1 to len do best[i] := t[len-i+1]; best[0] := len; if t[1] = 0 then begin inc(best[0]); best[best[0]] := 1; end; for i := len-len shr 1-1 downto 0 do begin flag := true; for j := 1 to i do if t[j] <> t[len-i+j] then begin flag := false; break; end; if flag then begin a[0] := len-i; tem := 0; for j := 1 to a[0] do a[j] := t[a[0]-j+1]; for j := 1 to a[0]-i do begin if (a[a[0]] <> 0) and ((i = 0) or (a[1] <> 9) or (t <> 9)) then if bigger(best, a) then begin best := a; c := tem; end; a[a[0]+1] := a[1]; for l := 1 to a[0] do a[l] := a[l+1]; a[a[0]+1] := 0; inc(tem); end; end; end; for l := 1 to best[0] do begin for i := l downto 1 do if (i < len) and (t <> 0) then begin fillchar(b, sizeof(b), 0); b[0] := l; for j := l downto 1 do begin if i+l-j+1 > len then break; b[j] := t; end; if (b[0] = 1) and (b[1] = 1) then continue; a := b; dec1(a); if match(i) and can(i+l) then begin if bigger(best, a) then begin c := a[0]-i; best := a; end; end; end; end; print; end; begin init; main; end. -
0
#include<cstdio>
#include<cstring>
int n,fp,ansp;
char str[210],minf[210],fir[210],ans[210],temp[210],next[210],ret[210];
void swap(char&a,char&b)
{
char tmp=a;
a=b;
b=tmp;
}
void get_Adjacent(char t[],int x)
{
char s[210];
int i,flag=0,len=strlen(t);
for(i=0;i<=len;i++)
s[i]=t[i];
if(x==-1)
{
for(i=len-1;i>=0&&s[i]=='0';i--);
if(i>=0)
s[i]--;
if(len>1&&s[0]=='0')
flag=-1;
for(i=i+1;i<len;i++)
s[i]='9';
}
else
{
for(i=len-1;i>=0&&s[i]=='9';i--);
if(i>=0)
s[i]++;
else
flag=1;
for(i++;i<len;i++)
s[i]='0';
}
i=0;
if(flag==1)
next[i++]='1';
for(;i<len+flag;i++)
next[i]=s[i-flag];
next[i]='\0';
}
bool judgment(int p,int len)
{
int i ;
if(str[p]!='1')
return 0;
for(i=1;i<p;i++)
if(str[i]!='9')
return 0;
for(i=1;i+p<=n&&i<len;i++)
if(str[i+p]!='0')
return 0;
return 1;
}
void getMin(char s[],char t[])
{
int i,ls=strlen(s),lt=strlen(t);
if(t[0]=='0'||lt>ls)
return;
if(lt<ls)
{
strcpy(s,t);
ansp=fp;
return;
}
for(i=0;i<ls;i++)
{
if(s[i]>t[i])
break;
else
if(s[i]<t[i])
return;
}
strcpy(s,t);
ansp=fp;
}
void find_FirstNumber()
{
int i,j,k,l,len,cnt;
for(i=0;i<208;i++)
minf[i]='A';
minf[210-1]='\0';
for(l=1;l<=n;l++)
for(len=l,i=2;i<=len+1;i++)
{
fp=i;
if(str[i]=='0')
continue;
if(n-i+1<len)
{
if(judgment(i,len+1))
{
for(j=0;j<len;j++)
fir[j]='9';
fir[j]='\0';
getMin(minf,fir);
continue;
}
for(j=1;j<i&&str[j]=='9';j++);
if(j==i)
{
for(j=0;j+i<=n;j++)
temp[j]=str[i+j];
temp[j]='\0';
get_Adjacent(temp,-1);
k=j;
cnt=1;
while(next[j-1]=='9'&&cnt<i)
{
k--;
j--;
cnt++;
}
for(j=0;j<k;j++)
fir[j]=next[j];
for(j=1;j<i;j++)
fir[k+j-1]=str[j];
fir[k+j-1]='\0';
getMin(minf,fir);
continue;
}
for(j=1;j<i;j++)
fir[len-j]=str[i-j];
fir[len]='\0';
for(j=0;j<=len-i;j++)
fir[j]=str[i+j];
get_Adjacent(fir,1);
for(j=0;j<len&&i+j<=n;j++)
if(next[j]!=str[i+j])
break;
if(j<len&&i+j<=n)
continue;
else
{
getMin(minf,fir);
continue;
}
}
if(judgment(i,len+1))
{
len++;
for(j=1;j<len;j++)
temp[j]='0';
temp[0]='1';
temp[j]='\0';
for(j=0;j<len-1;j++)
fir[j]='9';
fir[j]='\0';
}
else
{
for(j=0;j<len;j++)
temp[j]=str[j+i];
temp[j]='\0';
get_Adjacent(temp,-1);
for(j=1;j<i;j++)
if(next[len-j]!=str[i-j])
break;
if(j<i)
continue;
strcpy(fir,next);
}
k=i+len;
while(k<=n)
{
get_Adjacent(temp,1);
len=strlen(next);
for(j=0;k+j<=n&&j<len;j++)
if(next[j]!=str[k+j])
break;
if(k+j<=n&&j<len)
break;
strcpy(temp,next);
k+=len;
}
if(k>n)
getMin(minf,fir);
}
}
void bigAdd(char a[],char b[])
{
int la=strlen(a),lb=strlen(b),i,j,carrt=0,tmp,cnt=0;
for(i=la-1,j=lb-1;i>=0&&j>=0;i--,j--)
{
tmp=a[i]+b[j]-'0'-'0'+carrt;
carrt=tmp/10;
ret[cnt++]=tmp%10+'0';
}
for(;i>=0;i--)
{
tmp=a[i]-'0'+carrt;
carrt=tmp/10;
ret[cnt++]=tmp%10+'0';
}
for(;j>=0;j--)
{
tmp=b[j]-'0'+carrt;
carrt=tmp/10;
ret[cnt++]=tmp%10+'0';
}
while(carrt)
{
ret[cnt++]=carrt%10+'0';
carrt/=10;
}
ret[cnt++]='\0';
for(i=0;i<cnt/2;i++)
swap(ret[i],ret[cnt-i-2]);
strcpy(a,ret);
}
void bigMutil(char a[],int b)
{
int i,len=strlen(a);
for(i=0;i<=len;i++)
next[i]=a[i];
for(i=1;i<b;i++)
bigAdd(a,next);
}
void cal_Temp()
{
int i,j,len=strlen(minf);
for(i=1;i<len&&minf[i]=='0';i++);
if(i==len&&minf[0]=='1')
{
temp[0]='0';
temp[1]='\0';
return;
}
j=i=1;
temp[0]=minf[0]-1;
if(temp[0]=='0')
i=0;
for(;i<=len;i++,j++)
temp[i]=minf[j];
}
void solve()
{
char a[210];
int i,j,cnt,t,len=strlen(minf);
ans[0]='0';
ans[1]='\0';
for(i=1;i<len;i++)
{
t=i*9;
cnt=0;
while(t)
{
a[++cnt]=t%10+'0';
t/=10;
}
for(j=0;j<cnt;j++)
temp[j]=a[cnt-j];
cnt=j;
for(j=0;j<i-1;j++)
temp[cnt++]='0';
temp[cnt]='\0';
bigAdd(ans,temp);
}
cal_Temp();
bigMutil(temp,len);
bigAdd(ans,temp);
for(i=-1;i<=len-ansp;i++)
{
get_Adjacent(ans,1);
strcpy(ans,next);
}
}
bool special_Judge()
{
int i,j;
n--;
for(i=1;i<=n&&str[i]=='0';i++);
if(i<=n/2+1)
return 0;
ansp=i;
if(i>n)
{
minf[0]='1';
for(j=1;j<=n;j++)
minf[j]='0';
minf[j]='\0';
}
else
{
for(j=0;i+j<=n;j++)
minf[j]=str[i+j];
for(;j<n;j++)
minf[j]='0';
minf[j]='\0';
}
return 1;
}
main()
{
str[0]='0';
scanf("%s",str+1);
n=strlen(str);
if(!special_Judge())
find_FirstNumber();
solve();
printf("%s",ans);
}
牧云海
LV 10
@ 2009-06-15 15:49:33
信息
- ID
- 1005
- 难度
- 8
- 分类
- 字符串 | KMP 点击显示
- 标签
- (无)
- 递交数
- 6710
- 已通过
- 634
- 通过率
- 9%
- 被复制
- 33
- 上传者
-
xiaomengxian
