题目Luogu-P1311 选择客栈

题目链接

题目很好理解

1.暴力 60分

根据题面不难想到O(n²)的暴力，对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(n²)

程序略

3.递推 100分

可以从前往后依次加入客栈，考虑一下新加入一个客栈，对答案会有什么贡献

第一种情况，如果加入的客栈，b>p，那么这个客栈必须与它之前a值相同，且之间有b<p客栈的客栈组对贡献一对答案

第二种情况，如果加入的客栈，b<=p，那么这个客栈本身满足要求，所以与它之前任意a值相同的客栈，均可以组对贡献一对答案

一开始，想初始化出每一个点前面每一个色调的数量，但这样数组会开到10⁵*10⁵，开不下

其实没有必要存下所有的数量

我们设数组f[i]表示前i个客栈内的答案个数

用一个变量near，来表示在已经使用过的客栈过中，离i最近的一个b<=p的客栈的下标。（可以是自己）

用一个数组num[i]，表示色调i，在前near个客栈中出现的次数。

这样，在从f[i-1]更新f[i]的时候，如果 客栈_i 本身b_i<=p，那么先把从near到i所有的色调计入num数组，然后near=i，完成对near的维护

怎么计算f[i]呢？仔细思考，发现在更新完near之后，客栈_i 一定能与客栈_near前的客栈（包括客栈_near配对），因为它们之间有符合b_i<=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