# 30 条题解

• @ 2020-10-29 18:28:00

答案為lowbit(m)，m為題目中的山峰編號

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct ubigint
{
vector<int> num;
int operator == (ubigint b)
{
if (num.size()!=b.num.size())
return 0;
else
{
for (unsigned long long i=0,size=num.size();i<size;i++)
if (num[i]!=b.num[i])
return 0;
return 1;
}
}
int operator != (ubigint b)
{
return ((!(*this==b))?1:0);
}
int operator < (ubigint b)
{
if (num.size()<b.num.size())
return 1;
else if (num.size()>b.num.size())
return 0;
else
{
for (unsigned long long i=0,size=num.size();i<size;i++)
{
if (num[size-1-i]<b.num[size-1-i])
return 1;
else if (num[size-1-i]>b.num[size-1-i])
return 0;
}
return 0;
}
}
int operator > (ubigint b)
{
if (num.size()<b.num.size())
return 0;
else if (num.size()>b.num.size())
return 1;
else
{
for (unsigned long long i=0,size=num.size();i<size;i++)
{
if (num[size-1-i]<b.num[size-1-i])
return 0;
else if (num[size-1-i]>b.num[size-1-i])
return 1;
}
return 0;
}
}
int operator <= (ubigint b)
{
return ((!(*this>b))?1:0);
}
int operator >= (ubigint b)
{
return ((!(*this<b))?1:0);
}
ubigint mov(long long x)
{
ubigint ans;
ans.num.clear();
if (x+num.size()>0)
{
ans.num.resize(num.size()+x,0);
for (long long i=0,size=num.size();i<size;i++)
if (i+x>=0)
ans.num[i+x]=num[i];
}
else
ans=0;
return ans;
}
ubigint operator = (long long b)
{
char s[20+1];
sprintf(s,"%lld",b);
num.clear();
num.resize(strlen(s));
for (unsigned long long i=0,size=num.size();i<size;i++)
num[i]=(s[size-1-i]-'0');
return (*this);
}
ubigint operator = (string b)
{
num.clear();
num.resize(b.size());
for (unsigned long long i=0,size=num.size();i<size;i++)
num[i]=(b[size-1-i]-'0');
return (*this);
}
ubigint operator + (ubigint b)
{
ubigint ans;
ans.num.clear();
ans.num.resize(max(num.size(),b.num.size()));
for (unsigned long long i=0,size=ans.num.size();i<size;i++)
ans.num[i]=((i<num.size())?num[i]:0)+((i<b.num.size())?b.num[i]:0);
for (unsigned long long i=0,size=ans.num.size();i<size;i++)
{
if (ans.num[i]>=10&&i==size-1)
ans.num.resize(++size);
ans.num[i+1]+=(ans.num[i]/10);
ans.num[i]%=10;
}
return ans;
}
ubigint operator += (ubigint b)
{
return (*this=(*this+b));
}
ubigint operator - (ubigint b)
{
ubigint ans;
if ((*this)==b)
{
ans=0;
return ans;
}
ans.num.clear();
ans.num.resize(max(num.size(),b.num.size()));
for (unsigned long long i=0,size=ans.num.size();i<size;i++)
ans.num[i]=((i<num.size())?num[i]:0)-((i<b.num.size())?b.num[i]:0);
for (unsigned long long i=0,size=ans.num.size();i<size;i++)
while (ans.num[i]<0)
ans.num[i]+=10,ans.num[i+1]--;
while (ans.num[ans.num.size()-1]==0)
ans.num.resize(ans.num.size()-1);
return ans;
}
ubigint operator -= (ubigint b)
{
return (*this=(*this-b));
}
ubigint tm (ubigint b,unsigned long long pos)
{
ubigint ans,num_0;
num_0=0;
ans.num.clear();
if (*this!=num_0&&b!=num_0)
{
ans.num.resize(num.size()+pos);
for (unsigned long long i=0,size=num.size();i<size;i++)
ans.num[i+pos]=num[i]*b.num[pos];
for (unsigned long long i=0,size=ans.num.size();i<size;i++)
{
if (ans.num[i]>=10&&i==size-1)
ans.num.resize(++size);
ans.num[i+1]+=(ans.num[i]/10);
ans.num[i]%=10;
}
}
else
ans=0;
return ans;
}
ubigint operator * (ubigint b)
{
ubigint ans,num_0;
ans=0,num_0=0;
ans.num.clear();
if (*this!=num_0&&b!=num_0)
{
for (unsigned long long i=0,size=b.num.size();i<size;i++)
ans+=(*this).tm(b,i);
}
return ans;
}
ubigint operator *= (ubigint b)
{
return (*this=(*this*b));
}
ubigint operator / (ubigint b)
{
ubigint ans,num_0;
num_0=0;
if (*this<b)
return num_0;
if (*this!=num_0&&*this>num_0)
{
ubigint x,y;
x=*this,y=b.mov(num.size()-b.num.size());
ans.num.resize(num.size()-b.num.size()+1,0);
for (long long i=ans.num.size()-1;i>=0;i--,y=y.mov(-1))
while (x>=y)
x-=y,ans.num[i]++;
for (unsigned long long i=0,size=ans.num.size();i<size;i++)
{
if (ans.num[i]>=10&&i==size-1)
ans.num.resize(++size);
ans.num[i+1]+=(ans.num[i]/10);
ans.num[i]%=10;
}
while (ans.num.size()>1&&ans.num[ans.num.size()-1]==0)
ans.num.resize(ans.num.size()-1);
}
else
ans=0;
return ans;
}
ubigint operator /= (ubigint b)
{
return (*this=(*this/b));
}
void print()
{
for (unsigned long long i=0,size=num.size();i<size;i++)
printf("%d",num[size-1-i]);
}
};

char s[1<<10];
string ss;
ubigint m;
unsigned long long asize,a[1<<14],ans;

int main()
{
ubigint num0,num1,num2,num10,key;
num0=0,num1=1,num2=2,num10=10,key=(numeric_limits<long long>::max)();
key+=num1,key*=num2;
memset(s,0,sizeof(s));
scanf("%s",s);
ss=s;
m=ss;
memset(a,0,sizeof(a));
for (asize=0;m>num0;asize++)
{
ubigint s,y;
s=m/key;
y=m-s*key;
m=s;
for (long long i=y.num.size()-1;i>=0;i--)
a[asize]=a[asize]*10+y.num[i];
}
ans=1;
for (unsigned long long i=0;i<asize;i++)
if (a[i])
{
for (unsigned long long j=0;j<64;j++)
if (a[i]&((unsigned long long)1<<j))
{
ans+=j;
}
}
else
ans+=64;
printf("%llu\n",ans);
}
``````
• @ 2016-08-20 17:35:10
``````#include <cstdio>
#include <cstring>
char str[1005];
int start[10005],ans[10005],res[10005];
void change()
{
int i,len = strlen(str);
start[0] = len;
for(i=1;i<= len;i++)
{
if(str[i-1] >= '0' && str[i-1] <= '9')
{
start[i] = str[i-1] - '0';
}
}
}

void solve(int oldBase,int newBase)
{
memset(res,0,sizeof(res));
int y,i,j;
while(start[0] >= 1)
{
y=0;
i=1;
ans[0]=start[0];
while(i <= start[0])
{
y = y * oldBase + start[i];
ans[i++] = y/newBase;
y %= newBase;
}
res[++res[0]] = y;
i = 1;
while((i<=ans[0]) && (ans[i]==0)) i++;
memset(start,0,sizeof(start));
for(j = i;j <= ans[0];j++)
start[++start[0]] = ans[j];
memset(ans,0,sizeof(ans));
}
}

int main()
{
int ans=1;
scanf("%s",str);
change();
solve(10,2);
for (int i=1;i<=res[0];i++) if (res[i]==0) ans++;
else break;
printf("%d",ans);
return 0;
}
``````

char数组比string类效率略高

• @ 2013-04-03 23:37:42
• @ 2013-04-03 23:37:24

我有语，1ce，1wa，1tle，此后才ac

• @ 2009-11-03 13:57:36

我沙茶了........两遍才过.......

• @ 2009-09-05 15:08:56

记住！！

要用ansistring！！！！！！

• @ 2009-08-29 13:09:47

数学归纳法+高精度

• @ 2009-08-21 19:33:59

啦啦啦，我不会高精度除法啊.....

• @ 2009-08-20 17:17:11

第一次：ans初值没赋成1——0分

第二次结果如下：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行超时...

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

RP啊~

第三次：同第二次~

第四次：终于AC~

• @ 2009-08-13 18:04:10

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

• @ 2009-08-05 21:45:23

第100个AC！Yeah!

如此水题竟然没发现……

• @ 2009-08-05 19:33:04

囧rz，以前竟然一直没检查出来用了string，郁闷啊

• @ 2009-07-28 10:08:16

Flag 　　Accepted

题号 　　P1558

类型(?) 　　数论 / 数值

通过 　　2147483647人

提交 　　2147483647次

通过率 　　100%

难度 　　2

• @ 2009-07-15 02:45:59

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

p.s. 此题甚好

#include

#include

char a[1200];

int s[1200]={0},c[1200]={0},len,i,h;

void chu(int s[])

{

int y;

y=0;

for(i=s[0];i>=1;i--)

{

if((s[i]+y*10)>1)

{

c[i]=(s[i]+y*10)/2;

y=(s[i]+y*10)%2;

}

else

{

c[i]=0;

y=s[i];

}

}

if(c[s[0]]==0)

c[0]=s[0]-1;

else

c[0]=s[0];

for(i=1;i

• @ 2009-06-30 21:58:25

我是神牛！大家来膜拜我！！！！！

• @ 2009-06-29 20:36:22

Orz tan89.771度下取整 神牛。

• @ 2009-06-29 20:38:33

小于等于10^1000（注意等于！！！！）

对于这个方法正确性的解释：

（一开始我们只要求相邻两数不相等）

因为相邻两个数不能相等，又要最小，所以第1位应该为1，第二位为2。

然后第三位又要最小，所以第三位为1，我们先不管第4位为多少，可以得出显然奇数位上要为1。

最后将奇数位上的数去掉，化归成了一开始的问题（相邻两数要求不等）。

• @ 2009-07-02 10:51:04

冯牛审了道水题

• @ 2009-06-28 20:13:42

type

arr=array[0..1000] of integer;

var

i,j,k,l,n,m:longint;

s:ansistring;

a,c:arr;

procedure chu(var a:arr);

var

t,y,u:longint;

begin

y:=0;

for i:=a[0] downto 1 do

begin

if a[i]+y*10>1 then

begin

c[i]:=(a[i]+y*10) div 2;

y:=(a[i]+y*10) mod 2;

end

else

begin

c[i]:=0;

y:=a[i];

end;

end;

if c[a[0]]=0 then

c[0]:=a[0]-1

else

c[0]:=a[0];

a:=c;

end;

begin

m:=1;

a[0]:=length(s);

for i:=1 to length(s) do

a[i]:=ord(s[length(s)-i+1])-ord('0');

while not odd(a[1]) do

begin

chu(a);

m:=m+1;

end;

writeln(m);

end.

• @ 2009-06-29 14:59:05

用进制转换 要超时

只要判断尾数就可以选择停止了

ID
1558

4

(无)

423

168

40%

1