这个题目,可以看出每一个盘里的水往下流出的路径会是一样的,而且没有修改操作,所以我们可以预处理出每个盘里往下的路径,已经要下去所需要的水。
那么首先需要寻找每个盘往下的第一个盘是那个。对于盘 i 来说,第一个盘 j 应满足 $j>i &&D_j>D_i$,所以就可以想到用单调栈处理每个盘下第一盘。
对于每个盘来说,往下走 k 个盘所需的水为路过的 k 个盘的容量。
所以初值定为:
- $f_{i,j}$ 定为盘 i 往下走 $2^j$ 个盘到达的盘。初值 $f_{i,0}$ 为盘 i 下方第一个可以接到的盘。
- $sum_{i,j}$ 定位盘 i 往下走 $2^j$ 个盘所需要的水(注意需要大于该水量才可以下去)。初值 $sum_{i,0}=C_i$。
然后再用倍增打出 st 表。
预处理结束后就开始回答问题,假设当前所在盘为 now,剩余可用水量为 lft。我们就找到第一个小于(注意不能等于) lft 的 $sum_{now,j}$ 后令 lft -= sum[now][j];now=f[now][j];
。不断重复,直到 $lft\le sum_{now,0}$ 为止,答案即为 now。
再来考虑简化写法,显而易见,当一个盘能往下 $2^i$ 个盘却不能往下 $2^{i+1}$ 个盘时,下次所找到的往下 $2^k$ 中 $k < i$。所以我们只要每次都从 20 循环到 0,见一个能跳的就跳,全部过完后的所在盘即为最终的答案。至此,本题就可以解决了。
简化代码小技巧(个人认为):因为如果进入水池输出 0,所以我们可以把水池看作一个垫在最下面的盘并使其编号为 0,直径和容量均为 $10^9+7$。
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int stk[N], tail;
int n, Q;
int D[N], C[N];
int f[N][21], sum[N][21];
int main() {
scanf ("%d%d", &n, &Q);
for (int i = 1;i <= n; ++ i)
scanf ("%d%d", D + i, C + i);
D[0] = 1e9 + 7;
stk[tail = 1] = 0;
for (int i = n;i >= 1; -- i) {
while (tail && D[stk[tail]] <= D[i]) -- tail;
f[i][0] = stk[tail];
sum[i][0] = C[i];
stk[++ tail] = i;
}
for (int i = 1;i < 21; ++ i)
for (int j = 1;j <= n; ++ j) {
sum[j][i] = sum[j][i - 1] + sum[f[j][i - 1]][i - 1];
f[j][i] = f[f[j][i - 1]][i - 1];
}
for (int i = 0;i < 21; ++ i) sum[0][i] = 1e9 + 7;
while (Q --) {
int R, V;
scanf ("%d%d", &R, &V);
for (int i = 20;i >= 0; -- i) {
if (sum[R][i] < V) {
V -= sum[R][i];
R = f[R][i];
}
}
printf ("%d\n", R);
}
return 0;
}
标签:eJOI2020,个盘,int,sum,st,lft,tail,now,P7167
From: https://www.cnblogs.com/Assassins-Creed/p/18018371