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

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

点击量：222

 

    感觉这个题挺有价值的（正解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;
}

 

2
说点什么

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback
rolex replicas for sale

… [Trackback]

[…] Find More Info here to that Topic: wjyyy.top/2377.html […]

赞0踩  回复
3 年 之前
trackback
buy valid dumps

… [Trackback]

[…] Information to that Topic: wjyyy.top/2377.html […]

赞0踩  回复
3 年 之前
wpdiscuz   wpDiscuz
更多阅读
标签云
DP gcd/lcm KMP LCA lct splay tarjan 二分答案 二进制 倍增 前缀和 区间DP 同余 图论 堆 字符串 学习笔记 平衡树 快速排序 拓扑排序 搜索 数列 数学 最小割 最短路 构造 枚举 树 树形DP 树状数组 树链剖分 概率期望 模拟 状态压缩 生成树 线段树 组合数学 网络流 背包 解题报告 计算几何 记录 贪心 递推 随笔
/* */