首页 > 其他分享 >P7167 [eJOI2020 Day1] Fountain-st表

P7167 [eJOI2020 Day1] Fountain-st表

时间:2024-02-17 20:58:36浏览次数:30  
标签:eJOI2020 个盘 int sum st lft tail now P7167

这个题目,可以看出每一个盘里的水往下流出的路径会是一样的,而且没有修改操作,所以我们可以预处理出每个盘里往下的路径,已经要下去所需要的水。

那么首先需要寻找每个盘往下的第一个盘是那个。对于盘 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

相关文章

  • 初识st表-P2880
    首先讲讲st表。这个东西呢,就是一种利用了倍增思想的预处理数据从而达到快速查询的功能。for(inti=1;i<=n;++i)scanf("%d",&f[i][0]);for(inti=1;i<21;++i){intt1=1<<i-1,t2;t2=t1<<1;for(intj......
  • 100 行代码实现用户登录注册与 RESTful 接口 - 手把手教程附 Python 源码
    在开发大多数应用时,用户系统都是必不可少的部分,而我们总是需要开发围绕用户的登录,注册,获取,更新等接口。在这篇文章将带你用一百多行代码简洁地实现一套这样的用户鉴权与RESTful接口,并使用Session来处理用户的登录登出我们将使用UtilMeta框架完成接口开发,这是一个开源的Py......
  • [ARC165C] Social Distance on Graph
    转化题意,对图进行黑白染色,求最大的\(X\)满足所有\(u,v\)间最短路径小于\(X\)的\(u,v\)异色。很明显是二分答案,假设现在二分到\(mid\),转化为判定型问题。直接\(n^2\)枚举点肯定不对。发现性质:如果\(u,v\)的最短路径长度小于\(X\)且最短路径上经过的边数大于\(......
  • 第二十三天:MYSQL集群Cluster
    一、MySQL主从复制 1、主从复制架构和原理读写分离复制:每个节点都有相同的数据集,向外扩展,基于二进制日志的单向复制2、复制架构(1)一主一从复制架构 (2)一主多从复制架构3、主从复制原理  主从复制相关线程主节点:dumpThread:为每个Slave的I/OThread启动一个dump线......
  • [ARC067F] Yakiniku Restaurants
    首先考虑暴力。\(\mathcalO(n^2m)\)枚举左右两个端点,再贪心地选其中\(M\)张票的美味度最大那一家餐馆。复杂度不可接受,但是不难感觉到正解应该是\(\mathcalO(n^2)\)的。考虑枚举左端点\(i\),对于当前左端点,记每一个右端点\(j\)的答案为\(now_j\),若暂时不考虑距离,大部分......
  • Angular 17+ 高级教程 – Prettier, ESLint, Stylelint
    前言不熟悉 Prettier,ESLint,Stylelint的朋友可以先看这篇 工具–Prettier、ESLint、Stylelint。本篇主要是教如何在Angular项目引入 Prettier、ESLint、Stylelint。 ESLint       目录上一篇 TODO下一篇TODO想查看目录,请移步 Angular17+高......
  • Qt实用技巧:QCustomPlot做北斗GPS显示绝对位置运动轨迹和相对位置运动轨迹图的时,使图按
    需求  使用QCustomPlot绘制多个目标的北斗运行轨迹图,包括累计绝对位置图和记录时刻的相对位置图。  当前绘制存在问题:    交付客户前,公司内部自测流程发现的问题。  实际预期效果为:   原因  QCustomPlot加入数据是按照x轴排列,也可以按照y轴排列,使用图层......
  • CF1540E Tasty Dishes
    Description初始有\(n\)个数\(a_i\),以及若干条有向边\((u_i,v_i)\),保证\(u_i<v_i\)。一轮操作会形如下面两个过程:首先\(\foralli,a_i:=\max(a_i,ia_i)\)。然后\(\foralli,a'_i:=a_i+\sum\limits_{(i,j)\inE}\max(a_j,0)\),最后\(\foralli,a_i:=a'_i\)。......
  • PostgreSQL
    PostgreSQL安装后Navicat连不上报错Theauthenticationtype10isnotsupported.Checkthatyouhaveconfiguredthesys_hba.conf解决方案:找到启动数据库的data目录vim打开sys_hba.conf文件,把METHDD列全部改成trust执行结果:在vim命令模式下输入%s/替换的内容/要替换的内容/回......
  • Unity Audio System概要
    Unity的AudioSystem给我们提供了一整套的游戏音频处理解决方案,接下来我们对UnityAudioSystem进行简单的讲解。首先让我们来了解一下UnityAudioSystem包含了哪些重要的组成部分。AudioClip:这个是Unity存放外部音频资源的容器,可以根据我们的需要将外部导入的音频资源进行粗处......