递归+前缀和
直接按照上下限递归的话解答树规模可能达到 2k。
所以考虑 cal(k,i) 表示第 k 个小时前 i 行的红气球个数。这样答案可以表示为 cal(k,b)−cal(k,a−1) ，分两类：i≤2k−1 和 i>2k−1，第二种情况可以预处理出满的时候气球数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
int T, k, a, b;
ll p[35];
ll power(int a, int b) {
ll ans = 1;
while (b) {
if (b & 1)ans *= a;
b >>= 1;
a *= a;
}
return ans;
}
ll cal(int k, ll a) {
if (a == 0)return 0;
if (k == 0)return 1;
ll nxt = power(2, k - 1);
if (a <= nxt)return 2 * cal(k - 1, a);
else return cal(k - 1, a - nxt) + 2 * p[k - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
p[0] = 1;
for (int i = 1; i <= 30; i++) {
p[i] = p[i - 1] * 3;
}
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> k >> a >> b;
ll ans = cal(k, b) - cal(k, a - 1);
cout << "Case " << t << ": ";
cout << ans << endl;
}
return 0;
}
|
