题解

30 条题解

  • 1
    @ 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;
                        goto answer;
                    }
            }
            else
                ans+=64;
        answer:
        printf("%llu\n",ans);
    }
    
  • 0
    @ 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类效率略高

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

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

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

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

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

    记住!!

    要用ansistring!!!!!!

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

    数学归纳法+高精度

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

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

  • 0
    @ 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~

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

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

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

    第100个AC!Yeah!

    如此水题竟然没发现……

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

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

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

    Flag   Accepted

    题号   P1558

    类型(?)   数论 / 数值

    通过   2147483647人

    提交   2147483647次

    通过率   100%

    难度   2

  • 0
    @ 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

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

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

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

    Orz tan89.771度下取整 神牛。

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

    小于等于10^1000(注意等于!!!!)

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

    (一开始我们只要求相邻两数不相等)

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

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

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

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

    冯牛审了道水题

  • 0
    @ 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

    readln(s);

    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.

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

    用进制转换 要超时

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

信息

ID
1558
难度
4
分类
其他 | 数学 点击显示
标签
(无)
递交数
422
已通过
167
通过率
40%
被复制
1
上传者