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

递推/前缀和/Uva 12627

程序员文章站 2022-06-03 14:42:24
...

递推/前缀和/Uva 12627

  • 这题需要发现前一个时间段的图会成为后一个时间段的左上、右上、左下部分,而右下全是蓝色。
  • 假如题目需要的是在2k-1行前面的气球数,直接用上一张图这么多行的气球数×2就可以了。而如果需要2k-1行后面的,就需要上一张图里的前i-2k-1的,因为后面一张图的后半部分的气球数和以前一张图的是一样的(右下角都是蓝色)。
  • 这题还需要用到前缀和的思想,r1~r2的气球数,就用f(k,r2)-f(k,r1-1)来递推。
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

int kth,r1,r2;

int f(int kth,int r){
    if(r == 0) return 0;
    if(kth == 0) return 1;
    if(r > pow(2,kth - 1)) return (2 * pow(3,kth-1) + f(kth - 1,r - pow(2,kth-1)) );
    else return f(kth - 1,r) * 2;
}

int main(void){
    scanf("%d%d%d",&kth,&r1,&r2);
    cout << f(kth,r2) - f(kth,r1 - 1);
    return 0;
}
相关标签: Recursive 算法