雪人 部分分算法【双哈希】【差分】【二分答案】

作者: wjyyy 分类: 二分,二进制,双哈希,哈希,差分,快速乘,解题报告 发布时间: 2018-11-05 20:36

点击量:24

 

    感觉这个题挺有价值的(正解SAM就不管啦

 

题目背景

WZY AK NOIP 2018 后,决定去冰天雪地的 Y 城堆雪人。

题目描述

WZY堆了\(N\)个雪人,每个雪人都有一个可爱度\(X_i\),WZY认为两串雪人\(a_1,a_2,\dots ,a_n\)与\(b_1,b_2,\dots b_m\)和谐当且仅当

  1. \(n=m\)
  2. \(a_1-b_1=a_2-b_2=\dots =a_n-b_n\)

WZY现在要从一堆雪人中选择两串雪人\(A=[l_1,r_1],B=[l_2,r_2]\)( 两串可以重叠, 即若\(l_1\le l_2\),\(l_2\)可以小于等于\(r_1\)),使得\(A\)和\(B\)和谐,现在WZY想知道对于所有的方案中,\(\min(|l_1-l_2|,len(A))\)的最大值。\(len(A)\)为\(A\)中所含雪人的个数。

因为WZY还要准备AK JSOI 2019,所以他把这个问题交给了你。

输入输出格式

输入格式:

输入文件名为snowman.in

输入文件第一行为一个正整数\(N\),表示雪人的个数。

输入文件第二行为\(N\)个整数:\(X_1,X_2,\dots X_N\)。

输出格式:

输出文件名为snowman.out

输出文件仅一行一个整数,为\(\min(|l_1-l_2|,len(A))\)的最大值。

输入输出样例

输入样例#1:

10
1 2 3 4 5 6 7 8 9 10

输出样例#1:

5

输入输出样例1说明

应选\(A=[1,5],B=[6,10]\),此时,\(\min(|6-1|,5)=5\)。

数据规模与约定

\(\text{Subtask 1 10}\%:N\le 500;\\\text{Subtask 2 20}\%:N\le 5000;\\\text{Subtask 3 50}\%:N\le 100000;\\\text{Subtask 4 20}\%:N\le 500000,0\le X_i\le 100000000\)

题解:

    首先,这个题中的和谐实际上是指差分数组中的一段相等,当时联想的是CF471D MUH and Cube Walls这个题,同时也立即想到了KMP。但是这个题无法确定模式串,并且把相同长度的串全部放入AC自动机也不是很现实,可以考虑哈希。

\(O(n^3)\)解法

    这个做法可以不用哈希。枚举两个起点\(s_1,s_2\),然后增加长度,直到找到\(a_{s_1+i}-b_{s_1+i}\ne a_{s_1+i-1}-b_{s_2+i-1}\)为止,比较\(ans\)和\(\min(i,|s_1-s_2|)\),更新答案。期望得分\(10pts\)。

\(O(n^2\log n)\)解法

    同样枚举两个区间起点,然后用哈希二分两个串右端不同的位置。时间复杂度得到明显的优化,但是由于第二档\(n\le 5000\),所以期望得分仍然是\(10\)分。

哈希注意事项

    对于每一位,哈希所乘的基数是不一样的,根据进制不同,第\(i\)位乘上\(bs^{i-1}\),然后求前缀和。当两段哈希不在相同的位置时,我们需要把它们拉到同一位置,例如对于下面这两个\(S_1,S_2\),就需要让\(S_1\)这一段整体乘上\(bs^{j-i}\),如果这之后两段相等,就说明系数匹配上了,但不排除有冲突的情况

    如果判断范围比较大,比如下面讲的方法中,串可以在任意位置结束,那我们可以把所有的串的最高位都变成\(bs^{n-1}\),然后再进行匹配。

\(O(n^2)\)解法

    可以枚举长度,然后枚举起点,把同一长度的串的哈希值用链表或者std::map(期望复杂度会多个\(\log n\))存起来。对于链表,因为我们每次有\(n-l\)个元素,所以元素个数为\(O(n)\),因此我们开\(O(n)\)个哈希表,期望查找复杂度就是\(O(1)\),和上面一样更新\(ans\)即可。整体复杂度为\(O(n^2)\),期望得分\(30pts\)。

\(O(n\log n)\)解法

    因为两个和谐的串对答案造成的贡献是\(\min(|i-j|,l)\),可以推知,当两个串重叠时,答案就是\(|i-j|\),不重叠时答案是\(l\)。那么我们把前面的串在重叠的部分那一段去掉,变成了两个长为\(|i-j|\)的不重叠的和谐串,对答案的贡献并没有减小,因此,重叠可以转化为不重叠的情况,所以最优解中,两串一定不重叠。

    此时对答案做出贡献的只有被枚举的\(l\)了,也就是说,如果\(l\)无法更新答案,那么\(l+1\)就无法更新答案,而更新答案的要求就是两串不重叠。可见\(l\)是单调的,我们需要做的是二分出这个\(l\),每次可以\(\tt check(mid)\),根据是否存在两串相等的且不重叠的哈希值来判断\(mid\)是否成立即可。同样放在哈希表中,如果查到了哈希值相等的一段,那么判断两个起点差值是否大于\(|i-j|\),如果大于直接返回true即可,否则继续枚举。

    最终可以二分出来最大的合法的\(l\)。但是由于样本数量太多,取模非常容易起冲突,根据生日悖论,模数要开到超出\(\tt long long\)的数量级,使用普通哈希期望得分\(80pts\)。

点我跳过代码

Code of \(\tt std::map\):

    数组也只开到了\(10^5\),为了防止元素冲突,\(base\)也要开得很大。这里是用\(\tt std::map\)写的,后面有用哈希表写的

#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
#define p 200204121517
#define base 10000000019
using std::map;
ll qmul(ll x,ll y)
{
    ll ans=0;
    while(y)
    {
        if(y&1)
            ans=(ans+x)%p;
        x=x*2%p;
        y>>=1;
    }
    return ans;
}
int a[100100],n;//原数组
ll bs[100100],d[100100],sum[100100],hs[100100];
bool check(int l)
{
    map<ll,int> f;
    for(int i=1;i<=n-l+1;++i)
    {
        ll tmp=((sum[i+l-2]-sum[i-1])%p+p)%p;
        tmp=qmul(tmp,bs[n-l-i+1]);//n-l-i+1为与最后一位相差的位数
        map<ll,int>::iterator it=f.find(tmp);
        if(f.find(tmp)==f.end())
            f[tmp]=i;
        else
            if(it->second<=i-l)//间隔合法
                return true;
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    bs[0]=1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        bs[i]=qmul(bs[i-1],base);//预处理base的幂
    }
    for(int i=1;i<n;++i)
    {
        d[i]=a[i+1]-a[i];//计算差分
        d[i]=(d[i]+p)%p;//防止出现负数
        hs[i]=qmul(bs[i-1],d[i]);//计算哈希值
        sum[i]=sum[i-1]+hs[i];//哈希前缀和
    }
    int l=2,r=n,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    printf("%d\n",l-1);
    return 0;
}

点我跳过代码

Code of \(\tt hash table\):

#include<cstdio>
#include<cstring>
#define ll long long
#define p 200204121517
#define base 10000000019
#define pp 100003
ll qmul(ll x,ll y)
{
    ll ans=0;
    while(y)
    {
        if(y&1)
            ans=(ans+x)%p;
        x=x*2%p;
        y>>=1;
    }
    return ans;
}
int a[500100],n;
ll bs[500100],d[500100],sum[500100],hs[500100];
struct node
{
    int x;
    ll v;
    node *nxt;
    node(int x,ll v)
    {
        this->x=x;
        this->v=v;
        nxt=NULL;
    }
    node(){}
}head[pp],*tail[pp];
int stk[500100],tp=0;
bool check(int l)//l是原数组不是差分数组 
{
    while(tp)//注意清空哈希表时可以只清空用到过的以减小常数,但是复杂度是没有变的。
    {
        tail[stk[tp]]=&head[stk[tp]];
        head[stk[tp--]].nxt=NULL;//head.nxt注意要置NULL
    }
    for(int i=1;i<=n-l+1;++i)
    {
        ll tmp=((sum[i+l-2]-sum[i-1])%p+p)%p;
        tmp=qmul(tmp,bs[n-l-i+1]);
        int pos=tmp%pp;
        node *P=&head[pos];
        int flag=0;
        while(P->nxt!=NULL)
        {
            P=P->nxt;
            if(P->v==tmp)
            {
                flag=1;
                if(P->x<=i-l)
       	            return true;
            }
        }
        if(!flag)
        {
            if(tail[pos]==&head[pos])
                stk[++tp]=pos;
            tail[pos]->nxt=new node(i,tmp);
            tail[pos]=tail[pos]->nxt;
        }
    }
    return false;
}
int main()
{
    for(int i=0;i<pp;++i)
        tail[i]=&head[i];
    scanf("%d",&n);
    bs[0]=1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        bs[i]=qmul(bs[i-1],base);
    }
    for(int i=1;i<n;++i)
    {
        d[i]=a[i+1]-a[i];
        d[i]=(d[i]+p)%p;
        hs[i]=qmul(bs[i-1],d[i]);
        sum[i]=(sum[i-1]+hs[i])%p;
    }
    int l=2,r=n,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    printf("%d\n",l-1);
    return 0;
}

双哈希

    优化常数后,这个做法可以在\(6s\)以内AC掉本题。双哈希在复杂度上没有贡献,只是增加了正确的概率,使用普通哈希在最后一个子任务的任何测试点都无法通过。

    双哈希是取两个模数,当两个模数意义下哈希值都相等,那这次判断的错误概率就是原来的平方,几乎不会起冲突,但是双哈希增加了\(2\)的常数,需要注意时间上的优化。存两个模数时一定不要把它们放在数组里,数组引用非常慢,直接命名或者宏定义为\(p0,p1\)即可。

    哈希表在空间允许的情况下可以开到\(2n\)级别,保证了查询的上界复杂度,不过初始化时最好优化一下。

    最终在进行了各种优化后,最慢的点跑到了\(6s\),因为取模太多,还用了快速乘,常数非常大,而正解是常数相对较小的后缀数组,标准时限\(2s\),没学过就不写了。

Code:

#include<cstdio>
#include<cstring>
#define ll long long
#define base 10000000019
#define pp 100003
#define p0 200204123017
#define p1 201811051733

ll qmul(ll x,ll y,ll mod)//模数较大要用快速乘
{
    ll ans=0;
    while(y)
    {
        if(y&1)
            ans=(ans+x)%mod;
        x=x*2%mod;
        y>>=1;
    }
    return ans;
}
int a[500100],n;
ll bs[2][500100],d[2][500100],sum[2][500100],hs[2][500100];//分别对应两个模数的各类值
//base的幂    模意义下的差分数组  哈希值前缀和    哈希值
struct node
{
    int x;
    ll v1,v2;
    node *nxt;
    node(int x,ll v1,ll v2)
    {
        this->x=x;
        this->v1=v1;
        this->v2=v2;
        nxt=NULL;
    }
    node(){}
}head[pp],*tail[pp];
int stk[500100],tp=0;//需要还原的位置
bool check(int l)//l是原数组长度,差分数组的长度要-1
{
    while(tp)
    {
        tail[stk[tp]]=&head[stk[tp]];
        head[stk[tp--]].nxt=NULL;
    }
    for(int i=1;i<=n-l+1;++i)
    {
        ll tmp1=((sum[0][i+l-2]-sum[0][i-1])%p0+p0)%p0;
        tmp1=qmul(tmp1,bs[0][n-l-i+1],p0);//n-l-i+1是和最后一个串相差的位数
        ll tmp2=((sum[1][i+l-2]-sum[1][i-1])%p1+p1)%p1;
        tmp2=qmul(tmp2,bs[1][n-l-i+1],p1);
        int pos=tmp1%pp;
        node *P=&head[pos];
        int flag=0;
        while(P->nxt!=NULL)
        {
            P=P->nxt;
            if(P->v1==tmp1&&P->v2==tmp2)//同时匹配
            {
        	flag=1;
        	if(P->x<=i-l)
        	    return true;
            }
        }
        if(!flag)
        {
            if(tail[pos]==&head[pos])
                stk[++tp]=pos;
            tail[pos]->nxt=new node(i,tmp1,tmp2);
            tail[pos]=tail[pos]->nxt;
        }
    }
    return false;
}

int main()
{
    for(int i=0;i<pp;++i)
        tail[i]=&head[i];
    scanf("%d",&n);
    bs[0][0]=1;
    bs[1][0]=1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        bs[0][i]=qmul(bs[0][i-1],base,p0);
        bs[1][i]=qmul(bs[1][i-1],base,p1);
    }
    for(int i=1;i<n;++i)
    {
        d[0][i]=a[i+1]-a[i];
        d[1][i]=a[i+1]-a[i];
        d[0][i]=(d[0][i]+p0)%p0;
        d[1][i]=(d[1][i]+p1)%p1;
        hs[0][i]=qmul(bs[0][i-1],d[0][i],p0);//乘上相应的基数的幂
        sum[0][i]=(sum[0][i-1]+hs[0][i])%p0;
        hs[1][i]=qmul(bs[1][i-1],d[1][i],p1);
        sum[1][i]=(sum[1][i-1]+hs[1][i])%p1;
    }
    int l=2,r=n,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    printf("%d\n",l-1);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */