uva 12627 - Erratic Expansion（递归求解）

递归的边界条件写的多了……不是必需写呢么多的。。

不明确可共同探讨~

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

long long dp(int kk,int pos)

{

    int n=kk;int temp=(int)pow(2,n);

//    printf("%d %d\n",kk,pos);

    if(kk==0&&pos==1) return 1;

    if(kk==0&&pos==0) return 0;

    if(kk==1&&pos==0) return 0;

    if(kk==1&&pos==1) return 2;

    if(kk==1&&pos==2) return 3;

//    if(kk==2&&pos==0) return 0;

//    if(kk==2&&pos==1) return 4;

//    if(kk==2&&pos==2) return 3;

    if(pos<temp/2)

        return 2*dp(kk-1,pos);

    if(pos==temp/2)

        return 2*(long long)pow(3.0,kk-1);

    if(pos>temp/2)

        return 2*(long long)pow(3.0,kk-1)+dp(kk-1,pos-temp/2);

}

int main()

{

    int k,a,b;

    int t;

    int kase=0;

    scanf("%d",&t);

    while(t--)

    {

        kase++;

        scanf("%d%d%d",&k,&a,&b);

        long long ans1,ans2,ans;

        ans1=dp(k,b);ans2=dp(k,a-1);

        ans=ans1-ans2;

//        printf("ans1 = %I64d ans2 = %I64d\n",ans1,ans2);

        printf("Case %d: %lld\n",kase,ans);

    }

    return 0;

}