自动搬运

查看原文

来自洛谷，原作者为

	DengDuck 澳門現役 OIer，萌萌未花日奈雙推人一枚

搬运于2025-08-24 21:45:40，当前版本为作者最后更新于2023-07-13 10:12:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

这里我觉得可能需要进一步解释，内角只有两种情况，分别是 $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;
}