题解 P1311 【选择客栈】

拿到这道题的一般思路就是直接暴力枚举每一对l,r，再拿l与r的每一个数与p比较，这样就可以O(n^3)（不满）的复杂度获得60分 ``` #include<bits/stdc++.h> using namespace std; int n,k,p,ans; struct edge { int c,m; }a[200005]; inline int read(){ int x=0,k=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*k; } #define inf 123456789 int main() { n=read(),k=read(),p=read(); for(int i=1;i<=n;i++) { a[i].c=read(); a[i].m=read(); } for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { //枚举每一对l和r if(a[i].c==a[j].c) { //如果颜色相等就枚举l，r中的每一个点，小于p就让ans++。 int minn=inf; for(int k=i;k<=j;k++) { minn=min(minn,a[k].m); } //只需要比较最小值与p的大小即可 if(minn<=p) { ans++; } } } } printf("%d",ans); return 0; } ``` 接着我们再来看看三重循环中的第三重，不难发现，这一冲循环的目的就是维护区间最小值，我们自然的想到了线段树对线段树不了解的同学可以看看我的Blog： ## [线段树详解](https://tbr-blog.blog.luogu.org/solution-p3372) 代码并没有什么区别，~~就是加上了线段树~~，由于线段树较大的常数，所以还是60分 ``` // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; int n,k,p,ans; struct edge { int c,m; }a[200005]; inline int read(){ int x=0,k=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*k; } #define ls (k)<<1 #define rs (k)<<1|1 int mi[800005]; //建树 inline void build(int k,int l,int r) { if(l==r) { mi[k]=a[l].m; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); mi[k]=min(mi[ls],mi[rs]); } #define inf 123456789 //查询区间最小值 inline int find(int k,int l,int r,int ll,int rr) { if(ll<=l&&rr>=r) { return mi[k]; } int a=inf,b=inf,mid=(l+r)>>1; if(mid>=ll) { a=find(ls,l,mid,ll,rr); } if(mid<rr) { b=find(rs,mid+1,r,ll,rr); } return min(a,b); } int main() { n=read(),k=read(),p=read(); for(int i=1;i<=n;i++) { a[i].c=read(),a[i].m=read(); } build(1,1,n); for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { if(a[i].c==a[j].c) { //讲l到r这个区间的最小值与p比较 if(find(1,1,n,i,j)<=p) { ans++; } } } } printf("%d",ans); return 0; } ``` 那我们怎么拿到100分呢？ 我们不难发现，对于一个l，只要找到一个r与其之间有一个小于p的数，那么其他在这个r右侧且与l同色的点肯定都符合要求。那么我们可以进一步的进行优化：先用邻接表处理出每一个颜色的个数，在枚举每个颜色，将所有的颜色都更新，我们只需要找到一个符合条件的r，那我们便可以结束这一层循环。 ``` #include<bits/stdc++.h> using namespace std; int n,k,p,ans,c,m[200005],cnt[55]; inline int read(){ int x=0,k=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*k; } #define ls (k)<<1 #define rs (k)<<1|1 int mi[800005]; inline void build(int k,int l,int r) { if(l==r) { mi[k]=m[l]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); mi[k]=min(mi[ls],mi[rs]); } #define inf 123456789 inline int find(int k,int l,int r,int ll,int rr) { if(ll<=l&&rr>=r) { return mi[k]; } int a=inf,b=inf,mid=(l+r)>>1; if(mid>=ll) { a=find(ls,l,mid,ll,rr); } if(mid<rr) { b=find(rs,mid+1,r,ll,rr); } return min(a,b); } vector<int> q[50005];//用邻接表存储每一个颜色的数量 int main() { n=read(),k=read(),p=read(); for(int i=1;i<=n;i++) { c=read(),m[i]=read(); q[c].push_back(i); } build(1,1,n); //枚举每一个颜色 for(int i=0;i<k;i++) { //找到该色所有的节点 for(int l=0;l<q[i].size();l++) { for(int j=l+1;j<q[i].size();j++) { int a=q[i][l],b=q[i][j]; if(a>b) { swap(a,b); } //需要保证a比b小才能进行线段树的查询 if(find(1,1,n,a,b)<=p) { //找到了r就可以将右侧全部加入答案 ans+=q[i].size()-j; //q[i].size()表示改颜色所有节点个数，-j表示减去前面不合法的r break; } } } } printf("%d",ans); return 0; } ```