luogu P1311 选择客栈题解

小咪咪 2023-06-01 15:54 6阅读 0赞

### \\(luogu\\) P1311 选择客栈 题解 ###

[题目链接][Link 1]

看到这道题目首先很茫然，一看统计方案数，肯定要什么数论或者数学知识吧，然后就打了个暴力，发现答案不对。于是就看了一下样例解释，发现统计方案数只需要选客栈的方案数，不需要管咖啡厅的方案数。然后改了改，交了上去，成功拿了\\(60\\)分还多拿了10分。

#include<iostream> #include<climits> #include<cstdio> #define ll long long using namespace std; const int N=1e3+100; int n,k,p; int color[N],cost[N]; int minn[N][N]; ll ans; inline void pre() { for (int i=1;i<=n;i++) { int minx=INT_MAX; for (int j=i;j<=n;j++) { minx=min(minx,cost[j]); minn[i][j]=minx; } } return ; } int main() { scanf("%d%d%d",&n,&k,&p); for (int i=1;i<=n;i++) scanf("%d%d",color+i,cost+i); pre(); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (color[i]==color[j]&&minn[i][j]<=p) ans++; printf("%lld\n",ans); return 0; }

教训:写一些函数或变量一定要看头文件，还是万能头好用

发现如果题意是这样，这道题就比较简单，对于\\(\[l,r\]\\)只需要查询区间最小值是否满足就可以了。然后就想到了\\(ST\\)表，其实对于每一个固定的\\(l\\)，\\(r\\)是否合法是满足单调性的，如果\\(\[l,r\]\\)合法，\\(\[l,\[r,n\]\]\\)就也一定合法。所以我们就可以二分出最小的\\(r\\)，然后用后缀和或前缀和维护\\(\[r,n\]\\)一共有多少合法解，累加就是答案。

// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+100; int f[21][N],color[N],sum[N][52]; int n,k,p; ll ans; inline void RMQ() { for (int j=1;(1<<j)<=n;j++) for (int i=1;i+(1<<j)-1<=n;i++) f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]); return ; } inline int query(int l,int r) { int k=log2(r-l+1); return min(f[k][l],f[k][r-(1<<k)+1]); } inline int midfind(int x) { int l=x+1,r=n,mid=(l+r)>>1,ans=n+1; while (l<=r) { if (query(x,mid)<=p) { ans=mid; r=mid-1; } else l=mid+1; mid=(l+r)>>1; } return ans; } int main() { scanf("%d%d%d",&n,&k,&p); for (int i=1;i<=n;i++) { scanf("%d%d",&color[i],&f[0][i]); color[i]++; for (int j=1;j<=51;j++) if (j==color[i]) sum[i][j]=sum[i-1][j]+1; else sum[i][j]=sum[i-1][j]; } RMQ(); for (int i=1;i<=n-1;i++) { int now=midfind(i)-1; ans+=sum[n][color[i]]-sum[now][color[i]]; } printf("%lld\n",ans); return 0; }

教训:二分开始的\\(\[l,r\]\\)一定要确定好，\\(ans\\)的实际意义也要确定好，二分到\\(r\\)和无合法解\\(ans\\)的赋值要处理好。

转载于:https://www.cnblogs.com/last-diary/p/11454811.html

[Link 1]: https://www.luogu.org/problem/P1311