「题解」「POI2015」项链拆分 POD-Necklace partition

POI2015 Stage 2 Day 1 T1,POD,一道有趣的 哈希 Hash 题,也有 线段树 的做法。

题目链接:Luogu P3587POI2015 S2D1T1

本题解中的图片使用 Microsoft PowerPoint 2016 绘制。可以下载 ppt 文件看到更加清晰的图片。

题目

题目描述

长度为 \(n\) 的一串项链,每颗珠子是 \(k\) 种颜色之一。第 \(i\) 颗与第 \(i-1\)、\(i+1\) 颗珠子相邻,第 \(n\) 颗与第 \(1\) 颗也相邻。切两刀,把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。求方案数量(保证至少存在一种),以及切成的两段长度之差绝对值的最小值。

数据范围

变量数据范围
\(n,k\)\(1\leq k\leq n\leq 10^6\)

时空限制

题目编号时间限制空间限制
Luogu P3587\(1\texttt{s}\)\(125\texttt{MiB}\)
POI2015 S2D1T1\(1\texttt{s}\)\(128\texttt{MiB}\)

题解

POI2015 Stage 2 Day 1 T1,一道有趣的 哈希 Hash 题,也有 线段树 的做法。

为了节省时间,仅介绍时间效率较高的 哈希 Hash 做法。

解法 A(哈希 Hash)

考虑一串项链。

POI2015 POD Z1.png
如果图像失效请联系 Lu@Lu-Anlai.com
一串项链

我们不妨从上面那个红珠子的左边开始处理项链。

POI2015 POD Z2.png
如果图像失效请联系 Lu@Lu-Anlai.com
注意箭头的方向

这里有一个构造的方法:

  • 每次珠子出现后,对应颜色的出现次数增加一;
  • 如果这是该颜色珠子出现的最后一个,那么次数置为 \(0\)。

上面那个项链构造出来是这样的。

POI2015 POD Z3.png
如果图像失效请联系 Lu@Lu-Anlai.com
每颗珠子旁边都是考虑完它之后的状态

不难发现,能够满足题意的切法满足:落刀处的 \(k\) 元组状态相同。

例如上面那个项链。

POI2015 POD Z4.png
如果图像失效请联系 Lu@Lu-Anlai.com
\(k\) 元组之间的箭头代表他们相等,可以切割。

考虑到我们要维护 \(k\) 元组,而单次经过一个珠子只会改变 \(k\) 元组中一个位置上的值,所以可以用 哈希 Hash 解决

答案直接双指针法统计即可,没什么难的。

值得注意的是,本题卡哈希,可以考虑双哈希。

时间复杂度为 \(\Theta(n\log _ 2n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e6+5;
const int MAXK=MAXN;
const int pr1=200019,pr2=200011;
const int mod1=1e9+7,mod2=1e9+9;

struct Node{
	int id,h1,h2;
	inline Node(reg int id=0,reg int h1=0,reg int h2=0):id(id),h1(h1),h2(h2){
		return;
	}
	inline bool operator<(const Node& a)const{
		if(h1!=a.h1)
			return h1<a.h1;
		else if(h2!=a.h2)
			return h2<a.h2;
		else
			return id<a.id;
	}
};

int n,K;
int a[MAXN];
int las[MAXK];
int T[MAXK];
int base1[MAXN],base2[MAXN];
Node H[MAXN];

inline void Init(reg int n){
	base1[0]=base2[0]=1;
	for(reg int i=1;i<=n;++i){
		base1[i]=1ll*base1[i-1]*pr1%mod1;
		base2[i]=1ll*base2[i-1]*pr2%mod2;
	}
	return;
}

int main(void){
	Init(1e6);
	n=read(),K=read();
	for(reg int i=1;i<=n;++i)
		a[i]=read();
	for(reg int i=n;i>=1;--i)
		if(!las[a[i]])
			las[a[i]]=i;
	reg int h1=0,h2=0;
	for(reg int i=1;i<=n;++i){
		++T[a[i]];
		h1=(h1+base1[a[i]-1])%mod1;
		h2=(h2+base2[a[i]-1])%mod2;
		if(i==las[a[i]]){
			h1=(h1-1ll*T[a[i]]*base1[a[i]-1]%mod1+mod1)%mod1;
			h2=(h2-1ll*T[a[i]]*base2[a[i]-1]%mod2+mod2)%mod2;
		}
		H[i]=Node(i,h1,h2);
	}
	sort(H+1,H+n+1);
	reg int mid=(1+n)>>1;
	int ans=n;
	reg ll cnt=0;
	for(reg int i=1;i<=n;){
		reg int nxt=i;
		while(nxt<=n&&H[nxt].h1==H[i].h1&&H[nxt].h2==H[i].h2)
			++nxt;
		cnt+=(1ll*(nxt-i)*(nxt-i-1))>>1;
		for(reg int l=i,r=i;r<nxt;++r){
			while(l<r&&H[r].id-H[l].id>=mid)
				++l;
			if(l>i)
				ans=min(ans,abs(n-2*(H[r].id-H[l-1].id)));
			ans=min(ans,abs(n-2*(H[r].id-H[l].id)));
		}
		i=nxt;
	}
	printf("%lld %d\n",cnt,ans);
	return 0;
}