题解 P1311 【选择客栈】

· · 题解

为什么我每次有清奇脑回路时题解绝对多的一批

咳咳我来了

我发现题解里好像没有我的这种思路哎，那不抓紧撸一篇出来

O(kn)做法 报道！

建链 缩点！！（雾）

其实不是常规意义上的缩点啦...... 我们分颜色讨论，前缀和统计每两个（x，y）相同颜色之间有多少满足条件的酒吧（可看作把x，y连一条边，权值为f[y]-f[x-1]）

我们这时已经不需要考虑中间有多少个点了，于是我们得到一条链。

当链上某边权为0时，缩点！！

把这条边左右的点合成一个，然后得到一个每个边权都不为0的链。

此时方案数为：

链上点（n个）的n*（n-1）/2

加上被缩掉的点*（链上其他点+其他被缩掉的点）。

O（kn）的时间复杂度，算是能过。

大体是这个意思，具体结合代码理解吧

管理大大求过！

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,k,p1,c[200010],p[200010],f[200010],co[200010],ans,now[200010];
int main()
{
    scanf("%d%d%d",&n,&k,&p1);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&c[i],&p[i]);
    }
    for(int i=1;i<=n;i++){
        if(p[i]<=p1)f[i]=f[i-1]+1;
        else f[i]=f[i-1];
    }
    for(int i=0;i<k;i++){
        int cnt=0;
        memset(co,0,sizeof(co));
        memset(now,0,sizeof(now));
        for(int j=1;j<=n;j++){
            if(c[j]==i)co[++cnt]=j;
        }
        int bnt=cnt,f_k=1;
        for(int j=2;j<=cnt;j++){
            if( f[co[j]] - f[co[j-1]-1] == 0){
                bnt--;
                now[f_k]++;
            }
            else{
                f_k++;
            }
        }
        int a_k=cnt;
        for(int j=1;j<=f_k;j++){
            if(now[j]!=0)   ans+=(now[j])*(a_k-now[j]-1);
            a_k=a_k-now[j];
            if(a_k<0)a_k=0;
        }
        ans+=(bnt*(bnt-1))/2;
    }
    cout<<ans;
    return 0;
}