22 条题解

  • 1
    @ 2018-08-02 09:00:28

    n个盘子从第一根柱子完全移动到最后一根柱子的步数为h[i]
    可推出 h[i]=3*h[i-1]+2

    如果给出的状态中最大的盘子在第一根柱子,那么其实我们一直没有移动过它,相当于只移动n-1个盘子的情况,否则如果它在第二根柱子,那么我们一定是先将前n-1个盘子移动到第三根柱子然后再把最大的盘子移动到第二根柱子,这样可以算出这部分移动的步数,接下来最大的盘子不再动了,又相当于接下来只移动n-1个盘子的情况,因此可以这样不断转化为子问题。

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7777777;
    const double eps=1e-8;
    
    int n;
    string s;
    int a[201];
    struct bignum {
        int len;
        int a[201];
        bignum() {
            len=0;
            memset(a,0,sizeof a);
        }
        void operator=(bignum x) {
            len=x.len;
            FOR(i,len) a[i]=x.a[i];
        }
        bignum operator+(bignum x) {
            bignum res;
            res.len=max(len,x.len);
            FOR(i,res.len) {
                res.a[i]+=x.a[i]+a[i];
                if (res.a[i]>9) {
                    res.a[i+1]+=res.a[i]/10;
                    res.a[i]%=10;
                }
            }
            if (res.a[res.len+1]) res.len++;
            return res;
        }
        bignum operator*(bignum x) {
            bignum res;
            res.len=len+x.len-1;
            FOR(i,len) FOR(j,x.len) {
                res.a[i+j-1]+=a[i]*x.a[j];
            }
            FOR(i,res.len) {
                res.a[i+1]+=res.a[i]/10;
                res.a[i]%=10;
            }
            if (res.a[res.len+1]) res.len++;
            return res;
        }
    } h[201];
    bignum zero,one,two,three;
    bignum ans;
    bignum work(int x,int from,int to) {
        if (x==1) {
            if (a[n]==from) return zero;
            else if (a[n]==to) return two;
            else return one;
        }
        bignum res=zero;
        if (a[n+1-x]==from) {
            return work(x-1,from,to);
        } else if (a[n+1-x]!=to) {
            res=res+h[x-1];
            res=res+one;
            res=res+work(x-1,to,from);
            return res;
        } else {
            res=res+h[x-1];
            res=res+one;
            res=res+h[x-1];
            res=res+one;
            res=res+work(x-1,from,to);
            return res;
        }
    }
    void print(bignum x) {
        for (int i=x.len;i>=1;i--) {
            cout<<x.a[i];
        }
        cout<<endl;
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        zero.len=1;
        one.len=1,one.a[1]=1;
        two.len=1,two.a[1]=2;
        three.len=1,three.a[1]=3;
        h[1]=two;
        REP(i,2,200) {
            h[i]=h[i-1]*three+two;
        }
        
        while (cin>>n) {
            if (!n) break;
            cin>>s;
            for (int i=0;i<n;i++) {
                a[i+1]=s[i]-'A'+1;
            }
            ans=work(n,1,3);
            print(ans);
        }
        return 0;
    }
    
  • 1
    @ 2006-03-26 07:40:27

    1:2

    2:8

    3:26

    ……

    a[i]=a*3+2

    但是要高精度

  • 0
    @ 2021-07-25 20:37:52

    高精度啊

    int main
    eresting
        zero.len=1;
        one.len=1,one.a[1]=1;
        two.len=1,two.a[1]=2;
        three.len=1,three.a[1]=3;
        h[1]=two;
        REP(i,2,200) {
            h[i]=h[i-1]*three+two;
    
  • 0
    @ 2009-11-09 11:15:40

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    终于过了!

    要考虑答案为0的情况!

  • 0
    @ 2009-11-09 08:50:10

    编译通过...

    ├ 测试数据 01:答案正确... 119ms

    ├ 测试数据 02:答案正确... 197ms

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

    ├ 测试数据 04:答案正确... 103ms

    ├ 测试数据 05:答案正确... 134ms

    ├ 测试数据 06:答案正确... 181ms

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

    ├ 测试数据 08:答案正确... 228ms

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

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

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

    Accepted 有效得分:100 有效耗时:962ms

    时间好难看

  • 0
    @ 2009-09-04 14:29:51

    var f:array[0..201,1..10000] of longint;

    c:array[1..200] of char;

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

    begin

    n:=maxlongint;

    while n0 do

    begin

    fillchar(f,sizeof(f),0);

    readln(n);

    for i:=1 to n do

    read(c[i]);

    k:=1;

    for i:=1 to n do

    if c[i]='B' then

    begin

    for j:=1 to k do

    f:=3*f;

    for j:=1 to k do

    begin

    f:=f div 10000 +f;

    f:=fmod 10000;

    end;

    inc(f);

    for j:=1 to k do

    begin

    f:=f+f div 10000;

    f:=f mod 10000;

    end;

    if f0 then inc(k);

    end

    else

    begin

    if c[i]='A' then

    begin

    if f mod 2 = 0

    then

    begin

    for j:=1 to k do

    f:=3*f;

    for j:=1 to k do

    begin

    f:=f div 10000 +f;

    f:=fmod 10000;

    end;

    end

    else

    begin

    for j:=1 to k do

    f:=3*f;

    for j:=1 to k do

    begin

    f:=f div 10000+f;

    f:=fmod 10000;

    end;

    inc(f,2);

    for j:=1 to k do

    begin

    f:=f + f div 10000;

    f:=f mod 10000;

    end;

    end;

    if f0 then inc(k);

    end

    else

    begin

    if c[i]='C' then

    if f mod 2 = 1

    then

    begin

    for j:=1 to k do

    f:=3*f;

    for j:=1 to k do

    begin

    f:=f div 10000 +f;

    f:=fmod 10000;

    end;

    end

    else

    begin

    for j:=1 to k do

    f:=3*f;

    for j:=1 to k do

    begin

    f:=f div 10000 +f;

    f:=fmod 10000;

    end;

    inc(f,2);

    for j:=1 to k do

    begin

    f:=f+f div 10000;

    f:=f mod 10000;

    end;

    end;

    if f0 then inc(k);

    end;

    end;

    if n0 then

    begin

    write(f[n,k]);

    for i:=k-1 downto 1 do

    begin

    if f[n,i] div 1000=0 then write(0);

    if f[n,i] div 100=0 then write(0);

    if f[n,i] div 10=0 then write(0);

    write(f[n,i]);

    end;

    writeln;

    end;

    end;

    end.

    最后一个为什么超时啊???哪位大牛可以告诉我为什么啊???

  • 0
    @ 2009-08-02 22:34:50

    第k个表示半径第k大的圆盘

  • 0
    @ 2009-08-02 19:24:29

    谁能解释下样例

  • 0
    @ 2009-07-30 23:47:30

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

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

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

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

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

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

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

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

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

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

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

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

    递推式f[n]=3*f[n-1]+2,更重要的是弄清每一步怎么走,然后根据分解出来的“模拟”。

  • 0
    @ 2009-07-21 23:38:37

    为什么样例会是2??

  • 0
    @ 2008-11-06 11:49:58

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    Flag   Accepted

    题号   P1084

    类型(?)   数论 / 数值

    通过   102人

    提交   310次

    通过率   33%

    难度   2

    我来迟了

  • 0
    @ 2008-11-04 09:19:30

    Oops!!

    编译通过...

    ├ 测试数据 01:答案正确... 150ms

    ├ 测试数据 02:答案正确... 196ms

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

    ├ 测试数据 04:答案正确... 134ms

    ├ 测试数据 05:答案正确... 134ms

    ├ 测试数据 06:答案正确... 212ms

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

    ├ 测试数据 08:答案正确... 212ms

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

    ├ 测试数据 10:答案正确... 40ms

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

    Accepted 有效得分:100 有效耗时:1078ms

  • 0
    @ 2008-10-14 22:04:31

    感谢IVORY

    把inc(a[1],p)打成了inc(a[i],p)刚好交3次才A掉

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    好快啊,我用的是10进制呀!

  • 0
    @ 2008-10-13 22:08:51

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    归纳一下 可以发现规律的

    从前往后递推:

    f(0)=0;

    f(i+1)=f(i)*3+m;

    {if a[i]='B' then m:=1 else if (a[i]='A')and(f(i)mod 2=0) or (a[i]='C')and(f(i)mod 2=1) then m:=0 else m:=2;}

    注意:要高精度的!

  • 0
    @ 2008-09-13 00:21:22

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    感谢maolaoda大牛

  • 0
    @ 2008-07-16 16:29:32

    不能 A==>C....

    因此wa了2次...

  • 0
    @ 2007-10-02 18:15:07

    thanks to dejiyu

  • 0
    @ 2007-09-29 17:01:30

    比汉诺塔难想一些,还要高精度。

    分解每步的走法。

    比较快吧

    编译通过...

    ├ 测试数据 01:答案正确... 9ms

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 9ms

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

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

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

    Accepted 有效得分:100 有效耗时:18ms

  • 0
    @ 2007-05-22 19:33:24

    编译通过...

    ├ 测试数据 01:答案正确... 775ms

    ├ 测试数据 02:答案正确... 994ms

    ├ 测试数据 03:答案正确... 166ms

    ├ 测试数据 04:答案正确... 666ms

    ├ 测试数据 05:答案正确... 775ms

    ├ 测试数据 06:答案正确... 994ms

    ├ 测试数据 07:答案正确... 228ms

    ├ 测试数据 08:答案正确... 1056ms

    ├ 测试数据 09:答案正确... 197ms

    ├ 测试数据 10:答案正确... 634ms

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

    Accepted 有效得分:100 有效耗时:6485ms

    因为怕麻烦所以编了一个超猥琐的高精度..没想到..

信息

ID
1084
难度
6
分类
其他 | 数学 点击显示
标签
递交数
237
已通过
70
通过率
30%
被复制
2
上传者