洛谷P7167 [eJOI 2020 Day1] Fountain (单调栈+ST)
2022/4/22 23:45:30
本文主要是介绍洛谷P7167 [eJOI 2020 Day1] Fountain (单调栈+ST),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
开两个数组:to[i][j]表示从i这个位置向下的第2j个圆盘是哪个,f[i][j]表示流满从i这个位置向下的 2j 个圆盘需要多少体积的水。
详情见代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 int d[N],c[N],r,v; 5 int n,q,f[N][20],to[N][20]; 6 int top,s[N]; 7 8 int read(){ 9 int x=0,f=1;char c=getchar(); 10 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} 11 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); 12 return x*f; 13 } 14 15 int main(){ 16 n=read(),q=read(); 17 int sz=log2(n); 18 for(int i=1;i<=n;i++) d[i]=read(),c[i]=read(); 19 for(int i=n;i;i--){//用单调栈初始化出to[i][0],f[i][0] 20 while(top && d[i]>=d[s[top]]) top--; 21 to[i][0]=s[top],f[i][0]=c[i],s[++top]=i; 22 } 23 for(int j=1;j<=sz+1;j++)//ST的思想求出其他to和f 24 for(int i=1;i<=n;i++) 25 to[i][j]=to[to[i][j-1]][j-1],f[i][j]=f[i][j-1]+f[to[i][j-1]][j-1]; 26 while(q--){ 27 r=read(),v=read();//类似找LCA的做法 28 for(int j=sz+1;~j;j--) if(v>f[r][j]) v-=f[r][j],r=to[r][j]; 29 cout<<r<<endl; 30 } 31 }
这篇关于洛谷P7167 [eJOI 2020 Day1] Fountain (单调栈+ST)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-14让创意在幻觉中肆虐: 认识Illusion Diffusion AI
- 2024-05-08Sora从入门到入门-白话版1
- 2024-05-082024年github开源top100中文
- 2024-05-083、最大池化maxinmum pooling
- 2024-05-08动态规划基础思想
- 2024-05-08Kimi:文本解析利器,你相信光么?
- 2024-05-08在Windows电脑上快速运行AI大语言模型-Llama3
- 2024-05-08MoneyPrinterTurbo:一键生成短视频的AI神器
- 2024-05-08阶跃星辰:探索智能科技的星辰大海
- 2024-05-08一分钟部署 Llama3 中文大模型,没别的,就是快