题解 P1311 【选择客栈】

· · 题解

NOIP考前刷题，求各路大神保佑！！！ 听说多发题解可以RP++？？？

正题:

这个题目首先n^3是常好像的撒，n^2枚举,n判断。 好，接着,和大家一起一步一步优化 首先，我们发现，用一个cnt数组来表示从1号到当前多少费用小于p的客栈，那么两个客栈之间的合法客栈数量就是cnt[j]-cnt[i-1]（记住要-1!!!被坑哭了,我太弱了，诶) 然后有了：

#include <iostream>
using namespace std;
#define R register
int n,k,p;
int co[200000+5],mo[200000+5],cnt[200000+5];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    for(R int i=1;i<=n;i++) cin>>co[i]>>mo[i];
    for(R int i=1;i<=n;i++) cnt[i]=(mo[i]<=p)?cnt[i-1]+1:cnt[i-1];
    int sum=0;
    for(R int i=1;i<=n;i++)
        for(R int j=i+1;j<=n;j++) sum+=co[i]==co[j]&&cnt[j]-cnt[i-1];
        cout<<sum<<endl;
        return 0;
}

于是我们获得了60分的好成绩（=v=) 考虑继续优化，我们发现，只有当两个边界点的颜色相同的时候，我们才会记录答案，所以j在枚举的时候不必要一步一步走，而是直接跳到下一个颜色点去，（可以优化常数？还是啥，反正好像挺快的？？？）我们预处理实现即可；

#include <iostream>
#include <cstdio>
using namespace std;
#define R register
int n,k,p;
int co[200000+5],mo[200000+5],cnt[200000+5];
int mp[51],nxt[200000+5];
inline int read()
{
    #define C getchar()
    R int x=0;char a=C;
    for(;a>'9'||a<'0';a=C) ;
    for(;a>='0'&&a<='9';a=C) x=(x<<1)+(x<<3)+(a^48);
    return x;
}
int main()
{
    n=read(),k=read(),p=read();
    for(R int i=1;i<=n;i++) co[i]=read(),mo[i]=read();
    for(R int i=1;i<=n;i++) cnt[i]=(mo[i]<=p)?cnt[i-1]+1:cnt[i-1];
    for(R int i=n;i>=1;i--) 
        if(mp[co[i]]==0) mp[co[i]]=i;
        else nxt[i]=mp[co[i]],mp[co[i]]=i;
    R int sum=0;
    for(R int i=1;i<=n;i++)
    for(R int j=nxt[i];j;j=nxt[j]) sum+=cnt[j]-cnt[i-1]?1:0;
    printf("%d\n",sum);
    return 0;
}

于是我们获得了80分的好成绩（数据好水，大雾） 我们发现，当只有一种颜色的时候，上面的做法仍然是n^2的。我们发现慢就慢在了答案统计上，一个一个加实在太慢了，所以我们考虑(多加几个???) 我们枚举右边的那个点，然后用刚刚的思想预处理出这个点前面的第一个合法的点（注意，此处和上面是反方向的！！!）如果合法，那么他左边的和他同一个颜色的点都是合法的，然后一次性加好就可以了，同理，这个也是可以预处理的（就是代码里的cnc数组），统计答案就可以了。

#include <iostream>
#include <cstdio>
using namespace std;
#define R register
#define MAXN 200000+5
int n,k,p,sum;
int co[MAXN],mo[MAXN],cnt[MAXN];
int mp[51],nxt[MAXN],cnc[MAXN],cntc[51];
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(R int i=1;i<=n;i++) scanf("%d%d",&co[i],&mo[i]),cntc[co[i]]++,cnc[i]=cntc[co[i]];
    for(R int i=1;i<=n;i++) cnt[i]=mo[i]<=p?cnt[i-1]+1:cnt[i-1];
    for(R int i=1;i<=n;i++) !mp[co[i]]? mp[co[i]]=i : nxt[i]=mp[co[i]],mp[co[i]]=i;
    for(R int i=1;i<=n;i++)
        for(R int j=nxt[i];j;j=nxt[j]) if(cnt[i]-cnt[j-1]) {sum+=cnc[j];break;}
    printf("%d\n",sum);
    return 0;
}

（感觉好短有木有）