P6080-Cow Patterns G

· · 题解

前言

我看题解中一个是用的 Z 函数，另一个是 set，所以决定将链表解法分享出来。

这道题的思路与 P4696 差不多，都是记录前驱与后继。

解法

在这道题目中，我们只需要记录出模式串的大小关系，使用树状数组显然处理具有相等关系时更具有优势，但是本题解想另寻思路，利用链表的形式储存。

我们发现 1 \leq K \leq 25000 ，所以不妨 sort 完之后进行离散化，并暴力解决前驱后继。这里需要注意的就是要确保是稳定排序，因为顺序也会对答案产生影响。

然后就对于模式串算出 next 数组（没学过的同学可以了解一下），更改一下判断两个位置是否匹配的函数，注意取等的情况：

bool check1(int n1,int n2)
{
    bool flag=true;
    if(les[n1])
    {
        int xi=n2-(n1-les[n1]);
        if(val[les[n1]]==val[n1])
        {
            if(val[xi]!=val[n2])flag=false;
        }
        else
        {
            if(val[xi]>=val[n2])flag=false;
        }
    }
    if(mor[n1])
    {
        int xi=n2-(n1-mor[n1]);
        if(val[mor[n1]]==val[n1])
        {
            if(val[xi]!=val[n2])flag=false;
        }
        else
        {
            if(val[xi]<=val[n2])flag=false;
        }
    }
    return flag;
}
bool check2(int n1,int n2)
{
    bool flag=true;
    if(les[n1])
    {
        int xi=n2-(n1-les[n1]);
        if(val[les[n1]]==val[n1])
        {
            if(h[xi]!=h[n2])flag=false;
        }
        else
        {
            if(h[xi]>=h[n2])flag=false;
        }
    }
    if(mor[n1])
    {
        int xi=n2-(n1-mor[n1]);
        if(val[mor[n1]]==val[n1])
        {
            if(h[xi]!=h[n2])flag=false;
        }
        else
        {
            if(h[xi]<=h[n2])flag=false;
        }
    }
    return flag;
}

整体代码如下：

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,S;
int p[1000001],h[1000001];
int pos[1000001],val[1000001];
int les[1000001],mor[1000001];
int nex[1000001];
int ans,ge[1000001];
struct Node
{
    int val,pos,ls;
    int next,prev;
}node[1000001];
bool check1(int n1,int n2)
{
    bool flag=true;
    if(les[n1])
    {
        int xi=n2-(n1-les[n1]);
        if(val[les[n1]]==val[n1])
        {
            if(val[xi]!=val[n2])flag=false;
        }
        else
        {
            if(val[xi]>=val[n2])flag=false;
        }
    }
    if(mor[n1])
    {
        int xi=n2-(n1-mor[n1]);
        if(val[mor[n1]]==val[n1])
        {
            if(val[xi]!=val[n2])flag=false;
        }
        else
        {
            if(val[xi]<=val[n2])flag=false;
        }
    }
    return flag;
}
bool check2(int n1,int n2)
{
    bool flag=true;
    if(les[n1])
    {
        int xi=n2-(n1-les[n1]);
        if(val[les[n1]]==val[n1])
        {
            if(h[xi]!=h[n2])flag=false;
        }
        else
        {
            if(h[xi]>=h[n2])flag=false;
        }
    }
    if(mor[n1])
    {
        int xi=n2-(n1-mor[n1]);
        if(val[mor[n1]]==val[n1])
        {
            if(h[xi]!=h[n2])flag=false;
        }
        else
        {
            if(h[xi]<=h[n2])flag=false;
        }
    }
    return flag;
}
bool cmp(Node a,Node b)
{
    if(a.val==b.val)return a.pos<b.pos;
    return a.val<b.val;
}
bool tmp(Node a,Node b)
{
    return a.pos<b.pos;
}
void pre()
{
    for(int i=1;i<=n;i++)
    {
        node[i].val=val[i];
        node[i].pos=i;
    }
    sort(node+1,node+n+1,cmp);
    int g=0;
    for(int i=1;i<=n;i++)
    {
        if(i==1||node[i].val>node[i-1].val)g++;
        node[i].ls=g;
    }
    for(int i=1;i<=n;i++)
    {
        node[i].prev=node[i-1].pos;
        node[i].next=node[i+1].pos;
    }
    node[1].prev=0;
    node[n].next=0;
    sort(node+1,node+n+1,tmp);
}
int main()
{
    scanf("%d%d%d",&m,&n,&S);
    for(int i=1;i<=m;i++)scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=1;i<=n;i++)pos[val[i]]=i;
    pre();
    for(int i=n;i>=1;i--)
    {
        les[i]=node[i].prev;
        mor[i]=node[i].next;
        node[node[i].next].prev=node[i].prev;
        node[node[i].prev].next=node[i].next;
    }
    for(int i=2;i<=n;i++)
    {
        int j=nex[i-1];
        while(j>0&&check1(j+1,i)==false)j=nex[j];
        if(check1(j+1,i)==true)j++;
        nex[i]=j;
    }
//  for(int i=1;i<=n;i++)cout<<nex[i]<<" ";
//  cout<<endl;
    int j=0;
    for(int i=1;i<=m;i++)
    {
        while(j>0&&check2(j+1,i)==false)j=nex[j];
        if(check2(j+1,i)==true)j++;
        if(j==n)
        {
            j=nex[j];
            ge[++ans]=i-n+1;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)printf("%d\n",ge[i]);
    return 0;
}