题目Luogu-P1311 选择客栈
2022/7/24 23:22:43
本文主要是介绍题目Luogu-P1311 选择客栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目很好理解
1.暴力 60分
根据题面不难想到O(n2)的暴力,对b数组做一个最小值st表,然后暴力枚举两个端点,看区间最小值是否小于等于p即可
// Problem: P1311 [NOIP2011 提高组] 选择客栈 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P1311 // Memory Limit: 125 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define INF 0x7fffffff #define MAXN 200050 #define MAXM 10003 using namespace std; int n,k,p; int a[MAXN],b[MAXN],st[MAXN][21]; int ask(int l,int r){ int k=log2(r-l+1); return min(st[l][k],st[r-(1<<k)+1][k]); } int main(){ cin>>n>>k>>p; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; st[i][0]=b[i]; } for(int j=1;j<=20;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } int ans=0; for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ if(a[i]!=a[j]) continue; if(ask(i,j)>p) continue; ans++; } } cout<<ans; return 0; }
2.玄学优化 ?分(写挂了)
观察暴力,发现有许多时候,枚举的右端点与左端点的a值不一样,所以想到用Map映射色调,然后用vector挂载,每个vector都是色调相同的客栈,无奈很难写,而且出题人可以用一组一个色调只有两个客栈的数据把它卡回O(n2)
程序略
3.递推 100分
可以从前往后依次加入客栈,考虑一下新加入一个客栈,对答案会有什么贡献
第一种情况,如果加入的客栈,b>p,那么这个客栈必须与它之前a值相同,且之间有b<p客栈的客栈组对贡献一对答案
第二种情况,如果加入的客栈,b<=p,那么这个客栈本身满足要求,所以与它之前任意a值相同的客栈,均可以组对贡献一对答案
一开始,想初始化出每一个点前面每一个色调的数量,但这样数组会开到105*105,开不下
其实没有必要存下所有的数量
我们设数组f[i]表示前i个客栈内的答案个数
用一个变量near,来表示在已经使用过的客栈过中,离i最近的一个b<=p的客栈的下标。(可以是自己)
用一个数组num[i],表示色调i,在前near个客栈中出现的次数。
这样,在从f[i-1]更新f[i]的时候,如果 客栈i 本身bi<=p,那么先把从near到i所有的色调计入num数组,然后near=i,完成对near的维护
怎么计算f[i]呢?仔细思考,发现在更新完near之后,客栈i 一定能与客栈near前的客栈(包括客栈near配对),因为它们之间有符合bi<=p的客栈near,所以必定符合条件,而num的数量正是我们想要的,加上num[客栈i 的色调]即可
但是,如果 客栈i 自己符合条件,此时near已经被更新成 i ,加num之后还要减一,因为每个客栈是不能与自己配对的
程序很简单
// Problem: P1311 [NOIP2011 提高组] 选择客栈 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P1311 // Memory Limit: 125 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define INF 0x7fffffff #define MAXN 200050 #define MAXM 10003 using namespace std; int n,k,p; int a[MAXN],b[MAXN],st[MAXN][21]; int f[MAXN]; int num[MAXN]; int main(){ cin>>n>>k>>p; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } int near=b[1]<=p?++num[a[1]]:0; for(int i=2;i<=n;i++){ if(b[i]<=p){ for(int j=near+1;j<=i;j++){ num[a[j]]++; } near=i; f[i]=f[i-1]+num[a[i]]-1; }else{ f[i]=f[i-1]+num[a[i]]; } } cout<<f[n]; return 0; }
AC
这篇关于题目Luogu-P1311 选择客栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?