欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 12627:Erratic Expansion(递归)

程序员文章站 2022-03-11 23:47:44
...

I Can Guess the Data Structure!

Time limit:1000 ms OS:Linux

点击查看题目内容


UVA 12627:Erratic Expansion(递归)

题意:

其实没必要看题目里面啰嗦的描述,直接看图就知道了,从图上我们可以看到,假设第i个图形是Ai,把下一个图形由中间水平切割垂直切割成四块,可以看到第Ai+1个图形的左上,右上,左下三块都和Ai相同,右下块则全为蓝球。题目要我们统计第K个(从0开始)图形的第a行到第b行的红球个数。

解题思路:

规律是很容易看出来,上半部分是两个Ai-1,下半部分是一个Ai-1,第k个图形的第i行的红球数列出来:

  • 第0个:1
  • 第1个:2 1
  • 第2个:4 2 2 1
  • 第3个:8 4 4 2 4 2 2 1
  • ……

很容易写出递归式:

    if(n<=pow(2,k-1))
        return 2*dp(k-1,n);
    else
        return dp(k-1,n-pow(2,k-1));

但是靠这个公式必定超时。
正确的方法是对前 i 行红球的总数进行递归,同样可以得到

    if(i>pow(2,k-1))
        return 2*dp(k-1,pow(2,k-1))+dp(k-1,i-pow(2,k-1));
    else
        return 2*dp(k-1,i);

但是这么写还是会超时。看了大神的博客之后才发现,dp(k-1,pow(2,k-1))这部分的值代表第K-1个图形上所有的红球数,就是3k,把这个存起来,直接用来访问就可以了。


Code:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long LL;

LL c[35]={1};

LL dp(int k,int i)
{
    if(i==0)
        return 0;
    if(k==0)
        return 1;
    if(i>pow(2,k-1))
        return 2*c[k-1]+dp(k-1,i-pow(2,k-1));
    else
        return 2*dp(k-1,i);

}


int main()
{
    for(int i=1;i<=30;i++)
        c[i]=3*c[i-1];

    int T,ca=1;
    cin>>T;
    while(T--)
    {
        int k;
        LL a,b;
        scanf("%d%I64d%I64d",&k,&a,&b);

        cout<<"Case "<<ca++<<": "<<dp(k,b)-dp(k,a-1)<<endl;
    }
    return 0;
}