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

Erratic Expansion UVA - 12627 解题报告

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

这道题目大体的意思就是让你求K个小时后X----Y行红球的个数。 

Erratic Expansion UVA - 12627 解题报告

思路:我们仔细观察这幅图,发现这幅图是有规律可循的,K+1时刻的左上左下右上又是第K时刻的原图,而右下全部是蓝色的气球。所以我们不妨根据这幅图的特点来找一下规律。

过程。。。没啥好过程的就是枚举数据,从中找出规律。这道题的主要思想还是想让我们分治吧,虽然规律也不好找。

下面给出AC代码:

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<deque>
#include<functional>

typedef long long ll;
using namespace std;
const int maxn=1e6+1000;
const int INF=0x3f3f3f3f;
const ll mod=1e10;
ll c[maxn];

void init()
{
    c[0]=1;
    for(int i=1;i<=30;i++) c[i]=3*c[i-1];
}

ll fn(int k,ll i)
{
    if(i<=0) return 0;
    if(k==0) return 1;
    if(i<1<<(k-1))
    {
        return 2*fn(k-1,i);
    }
    else
    {
        return fn(k-1,i-(1<<(k-1)))+2*c[k-1];
    }
}

int main()
{
    init();
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        int k; ll l,r;
        scanf("%d %lld %lld",&k,&l,&r);

        printf("Case %d: %lld\n",kase,fn(k,r)-fn(k,l-1));
    }
    return 0;

}