题解 P1311 【选择客栈】

YuRuiH_ · 2019-11-14 09:14:01 · 题解

广告：博客地址

60Pts

这个题先考虑暴力吧，直接n^2枚举，可以直接拿到60pts的分数。

int main()
{
    read(n),read(k),read(p);
    for(rg int i=1;i<=n;i++)
        read(a[i]),read(val[i]);
    for(rg int i=1;i<=n;i++)
        for(rg int j=i+1;j<=n;j++)
        {
            if(a[i]==a[j])
            {
                for(rg int k=i;k<=j;k++)
                {
                    if(val[k]<=p)
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
    std::cout<<ans;
}

60Pts Round 2

考虑维护一个前缀和，这个前缀和是关于合法客栈数的前缀和，然后依然是n^2枚举。虽然还是60Pts，但是这个思路可以在接下来继续应用！

int main()
{
    read(n),read(k),read(p);
    for(rg int i=1;i<=n;i++)
    {
        read(a[i]),read(val[i]);
        if(val[i]<=p)
            sum[i]=sum[i-1]+1;
        else
            sum[i]=sum[i-1];
    }
    for(rg int i=1;i<n;i++)
        for(rg int j=i+1;j<=n;j++)
        {
            if(a[i]==a[j])
            {
                if(sum[j]-sum[i-1]>=1)
                    ans++;
            }
        }
    std::cout<<ans;
}

80Pts

看到题目中给到了k这个变量，就考虑直接枚举颜色数，然后计算，可以拿到80Pts

int main()
{
    read(n),read(k),read(p);
    for(rg int i=1;i<=n;i++)
    {
        read(a),read(val);
        if(val<=p)
            sum[i]=sum[i-1]+1;
        else
            sum[i]=sum[i-1];
        cnt[a]++;
        belog[a][cnt[a]]=i;
    }
    for(rg int i=0;i<k;i++)
    {
        for(rg int j=1;j<cnt[i];j++)
        {
            for(rg int f=j+1;f<=cnt[i];f++)
            {
                if(sum[belog[i][f]]-sum[belog[i][j]-1]>=1)
                    ans++;
            }
        }
    }
    std::cout<<ans;
}

100Pts

继续在80Pts上拓展，可以考虑直接枚举同类的颜色和他的位置，然后进行一些操作：

因为如果一个区间内有合法的客栈，那么他与后面的客栈都可以构成一个合法的区间（此处合法的区间意思是：区间内有答案！）

所以如果扫到一个合法的客栈的时候,ans直接 ans+=(cnt[i]-f+1) 此处cnt[i]是指第i种颜色的客栈数，f是这个合法客栈的位置，+1为啥大家都应该知道！

    read(n),read(k),read(p);
    for(rg int i=1;i<=n;i++)
    {
        read(a),read(val);
        if(val<=p)
            sum[i]=sum[i-1]+1; // 维护前缀和
        else
            sum[i]=sum[i-1];
        cnt[a]++;
        belog[a][cnt[a]]=i; // 维护颜色出现的位置
    }
    for(rg int i=0;i<k;i++) // 枚举颜色
    {
        for(rg int j=1;j<cnt[i];j++)
        {
            for(rg int f=j+1;f<=cnt[i];f++)
            {
                if(sum[belog[i][f]]-sum[belog[i][j]-1]>=1)// 如果他们之间有合法的情况
                {
                    ans+=cnt[i]-f+1;// 直接统计
                    break;
                }
            }
        }
    }
    std::cout<<ans;

满分代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define LL long long
#define rg register

template<class T>
inline void read(T &x)
{
    x=0;
    bool f=0;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        f^c=='-';
    for(;isdigit(c);c=getchar())
        x=x*10+(c^48);
    x=f?-x:x;
}

const int MAXN=2e5+100;

int n,k,p,a,val,ans,sum[MAXN],belog[60][MAXN],cnt[MAXN];

int main()
{
    read(n),read(k),read(p);
    for(rg int i=1;i<=n;i++)
    {
        read(a),read(val);
        if(val<=p)
            sum[i]=sum[i-1]+1;
        else
            sum[i]=sum[i-1];
        cnt[a]++;
        belog[a][cnt[a]]=i;
    }
    for(rg int i=0;i<k;i++)
    {
        for(rg int j=1;j<cnt[i];j++)
        {
            for(rg int f=j+1;f<=cnt[i];f++)
            {
                if(sum[belog[i][f]]-sum[belog[i][j]-1]>=1)
                {
                    ans+=cnt[i]-f+1;
                    break;
                }
            }
        }
    }
    std::cout<<ans;
}