递推/前缀和/Uva 12627
程序员文章站
2022-06-03 14:42:24
...
- 这题需要发现前一个时间段的图会成为后一个时间段的左上、右上、左下部分,而右下全是蓝色。
- 假如题目需要的是在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;
}
下一篇: 当年在大公司实习的你实力如何?