题解 P1311 【选择客栈】
主要是给自己复习用的...
首先，看到题目，你首先想的是什么呢？
虽然我不知道你想的是什么，但是我想的就是一个区间最值查询问题（RMQ），所以我写了ST表,如下是代码:
#include<cstdio>
inline int read(){
int r=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){r=(r<<3)+(r<<1)+(c-48);c=getchar();}
return r*f;
}
int f[21][200001],Log[200001],mi[30],a[200001],c[200001],q[50][200001];
inline int min(int a,int b){
return a<b?a:b;
}
inline void init(int n){//初始化ST表
int i,j;
Log[0]=-1;
for(i=1;i<=n;i++)Log[i]=Log[i/2]+1;
mi[0]=1;
for(i=1;i<=30;i++)mi[i]=2*mi[i-1];
for(i=1;i<=n;i++)f[0][i]=a[i];
for(i=1;i<=Log[n];i++)
for(j=1;j+mi[i]-1<=n;j++)
f[i][j]=min(f[i-1][j],f[i-1][j+mi[i-1]]);
}
inline int query(int l,int r){//查询
int k=Log[r-l+1];
return min(f[k][l],f[k][r-mi[k]+1]);
}
int main(){
int n=read(),K=read(),p=read(),i,j,k,ans=0;
for(i=1;i<=n;i++){
c[i]=read();
a[i]=read();
q[c[i]][++q[c[i]][0]]=i;
}
init(n);
for(i=0;i<K;i++)//暴力枚举...
for(j=1;j<q[i][0];j++)
for(k=j+1;k<=q[i][0];k++)
if(query(q[i][j],q[i][k])<=p)ans++;
printf("%d",ans);
return 0;
}果断提交，然而3个TLE...
这时我就想，如何优化呢？
因为如果query(i,j)<=p那么query(i,j+1)(j<n)肯定也行！
所以代码就变成这样:
#include<cstdio>
inline int read(){
int r=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){r=(r<<3)+(r<<1)+(c-48);c=getchar();}
return r*f;
}
int f[21][200001],Log[200001],mi[31],a[200001],c[200001],q[50][200001];
inline int min(int a,int b){
return a<b?a:b;
}
inline void init(int n){
Log[0]=-1;
for(register int i=1;i<=n;i++)Log[i]=Log[i/2]+1;
mi[0]=1;
for(register int i=1;i<=30;i++)mi[i]=2*mi[i-1];
for(register int i=1;i<=n;i++)f[0][i]=a[i];
for(register int i=1;i<=Log[n];i++)
for(register int j=1;j+mi[i]-1<=n;j++)
f[i][j]=min(f[i-1][j],f[i-1][j+mi[i-1]]);
}
inline int query(int l,int r){
int k=Log[r-l+1];
return min(f[k][l],f[k][r-mi[k]+1]);
}
int main(){
int n=read(),K=read(),p=read(),b,ans=0,ans1=0;
for(register int i=1;i<=n;i++){
c[i]=read();
a[i]=read();
q[c[i]][++q[c[i]][0]]=i;
}
init(n);
for(register int i=0;i<K;i++){
b=2;
ans1=ans;
for(register int j=1;j<q[i][0];j++)
for(register int k=b;k<=q[i][0];k++)
if(query(q[i][j],q[i][k])<=p){
ans+=q[i][0]-k+1;//可以就一次加
b=k;//记录位置
break;
}
if(ans1==ans)break;//如果不行了，就换颜色
}
printf("%d",ans);
return 0;
}然而更奇怪的,变得只有一个点AC了。
突然看到当b==j+1（b!=2）时，下一次枚举就重复，所以经过修改，终于AC了！
AC代码：
#include<cstdio>
inline int read(){
int r=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){r=(r<<3)+(r<<1)+(c-48);c=getchar();}
return r*f;
}
int f[21][200001],Log[200001],mi[31],a[200001],c[200001],q[50][200001];
inline int min(int a,int b){
return a<b?a:b;
}
inline void init(int n){
Log[0]=-1;
for(register int i=1;i<=n;i++)Log[i]=Log[i/2]+1;
mi[0]=1;
for(register int i=1;i<=30;i++)mi[i]=2*mi[i-1];
for(register int i=1;i<=n;i++)f[0][i]=a[i];
for(register int i=1;i<=Log[n];i++)
for(register int j=1;j+mi[i]-1<=n;j++)
f[i][j]=min(f[i-1][j],f[i-1][j+mi[i-1]]);
}
inline int query(int l,int r){
int k=Log[r-l+1];
return min(f[k][l],f[k][r-mi[k]+1]);
}
int main(){
freopen("1.in","r",stdin);
int n=read(),K=read(),p=read(),b,ans=0,ans1=0;
for(register int i=1;i<=n;i++){
c[i]=read();
a[i]=read();
q[c[i]][++q[c[i]][0]]=i;
}
init(n);
for(register int i=0;i<K;i++){
b=2;
ans1=ans;
for(register int j=1;j<q[i][0];j++){
for(register int k=b;k<=q[i][0];k++)
if(query(q[i][j],q[i][k])<=p){
ans+=q[i][0]-k+1;
b=k;
break;
}
if(ans1==ans)break;
if(b<=j+1)b=j+2;
}
}
printf("%d",ans);
return 0;
}