P3134 [USACO16JAN] Lights Out G 题解

· · 题解

我一开始读错题了，以为奶牛知道方向......

感觉大家都是字符串做法，来个快一点的哈希。

我们要找奶牛走的路径是否唯一，判断两个路径是否相同，需要存储很多信息，而且只比较是否相等，这显然是哈希的标志。

哈希的方式就很多了，我的方式是每条边距离乘上内角，内角用两个常数表示。

这里我觉得可能需要进一步解释，内角只有两种情况，分别是 90\degree 和 270\degree 两种可能，如何求角是个麻烦的事情。

我们可以讨论一手，然后发现，我们给出点的时候（也就是输入），要么是顺时针给，要么是逆时针给，而角度与 (i-1,i) 旋转至 (i,i+1) 是顺时针还是逆时针有关。

进一步地，我们不关心角度到底是多少，我们反正要把它变成一个常量了，我们不妨直接按顺时针还是逆时针给其表示内角的常量。

处理好了，每次还要乘上一个常数 K，防止溢出还需要模 10^9+7。

我们把这些路径存在 multiset 之中，我们需要多个 multiset，第 i 个表示路径经历边数为 i 的路径的哈希值可重集。

我们直接模拟吧，当我们走的一个地方时，我们的哈希值在可重集中是唯一的，那么终止循环并更新答案即可。

由于我用了 multiset，时间复杂度为 O(n^2\log n)，理论上可以优化成 O(n^2)，但我懒。

我丧心病狂也才全洛谷第四，前面的字符串怎么比我快啊 QAQ。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1005;
const LL L=114514,R=191981,K=2008;
const LL mod=1e9+7;

LL n,x[N],y[N],dis[N],mx,l[N],r[N],d[N];
multiset<LL>s[N];
LL cal(LL a,LL b)
{
    if(a==n+1)a=1;
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x[i],&y[i]);
    }
    for(int i=2;i<=n;i++)
    {
        dis[i]=dis[i-1]+cal(i-1,i);
    }
    for(int i=n;i>=2;i--)
    {
        dis[i]=min(dis[i],dis[i+1]+cal(i+1,i));
    }   
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            if(x[i]+y[i]<=x[n]+y[n])l[i]=1; 
        }
        else if(x[i]+y[i]<=x[i-1]+y[i-1])l[i]=1;    
    }
    for(int i=n;i>=1;i--)
    {
        if(i==n)
        {
            if(x[i]+y[i]<=x[1]+y[1])r[i]=1; 
            if(x[i]==x[1]&&l[i]==0&&r[i]==1)d[i]=R;
            else if(y[i]==y[1]&&l[i]==1&&r[i]==1)d[i]=R;
            else if(x[i]==x[1]&&l[i]==1&&r[i]==0)d[i]=R;
            else if(y[i]==y[1]&&l[i]==0&&r[i]==0)d[i]=R;
        }
        else
        {
            if(x[i]+y[i]<=x[i+1]+y[i+1])r[i]=1;
            if(x[i]==x[i+1]&&l[i]==0&&r[i]==1)d[i]=R;
            else if(y[i]==y[i+1]&&l[i]==1&&r[i]==1)d[i]=R;
            else if(x[i]==x[i+1]&&l[i]==1&&r[i]==0)d[i]=R;
            else if(y[i]==y[i+1]&&l[i]==0&&r[i]==0)d[i]=R;
        }
        if(d[i]==0)d[i]=L;
    }   
    for(int i=2;i<=n;i++)
    {
        LL cnt=d[i];
        s[0].insert(d[i]);
        for(int j=i+1;j<=n;j++)
        {
            cnt=cnt*K%mod;
            if(x[j]+y[j]<=x[j-1]+y[j-1])
            {
                cnt=(cnt+d[j]*cal(j,j-1)%mod)%mod;
            }
            else
            {
                cnt=(cnt+d[j]*cal(j,j-1)%mod)%mod;
            }
            s[j-i].insert(cnt);
        }
    }
    for(int i=2;i<=n;i++)
    {
        LL cnt=d[i],sum=0;      
        for(int j=i+1;j<=n;j++)
        {
            cnt=cnt*K%mod;
            if(x[j]+y[j]<=x[j-1]+y[j-1])
            {
                cnt=(cnt+d[j]*cal(j,j-1)%mod)%mod;
            }
            else
            {
                cnt=(cnt+d[j]*cal(j,j-1)%mod)%mod;
            }
            sum+=cal(j,j-1); 
            if(s[j-i].count(cnt)<=1)
            {
                mx=max(mx,dis[j]+sum-dis[i]);
                break;
            }           
        }       
    }
    printf("%lld",mx);
    return 0;
}