「bzoj4382」「POI2015」Podział naszyjnika - 字符串+Hash | Bill Yang's Blog

「bzoj4382」「POI2015」Podział naszyjnika - 字符串+Hash

题目大意

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


题目分析

这篇文章讲得比较清楚。

补充一下。
以颜色作为分界线,对于每一种颜色,只能在同一个连通块内分割。
故对连通块作Hash,Hash相同的地方即可划分成两块。
若能得到Hash,剩下的就可以排序+双指针了。

普通的$O(nk)$的Hash不可行。
因为相邻两个位置颜色只差$1$,故可以放弃乘底数式Hash,直接采用相加的Hash,即可$O(1)$计算下一个的Hash值。
但这样Hash的准确度有所下降,使用双Hash即可解决。

注意对于每一种颜色,最后分界线后与第一个分界线前编号应该相同。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005,mod=99995999;
LL n,k,v[maxn],a[maxn][2],b[maxn][2],Last[maxn],ans=0,ans2=mod;
struct Hash {
int val[2],pos;
bool operator < (const Hash& b) const {
return val[0]<b.val[0]||(val[0]==b.val[0]&&val[1]<b.val[1]);
}
bool operator == (const Hash& b) const {
return val[0]==b.val[0]&&val[1]==b.val[1];
}
} Hash[maxn];
int main() {
srand(99995999);
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)v[i]=Get_Int();
for(int i=1; i<=k; i++) {
a[i][0]=rand(); //底数
a[i][1]=rand();
b[i][0]=b[i][1]=1;
}
for(int i=n; i>=1; i--)if(!Last[v[i]])Last[v[i]]=i;
Hash[0].val[0]=Hash[0].val[1]=k;
for(int i=1; i<=n; i++)
for(int id=0; id<=1; id++) {
int x=v[i];
Hash[i].val[id]=Hash[i-1].val[id]-b[x][id];
b[x][id]=b[x][id]*a[x][id]%mod;
if(Last[x]==i)b[x][id]=1;
Hash[i].val[id]=(Hash[i].val[id]+b[x][id]+mod)%mod;
Hash[i].pos=i;
}
sort(Hash+1,Hash+n+1);
for(int i=1,j; i<=n; i=j) {
j=i;
int cnt=0;
vector<LL> cur;
while(Hash[j]==Hash[i]) {
cnt++;
cur.push_back(Hash[j].pos);
j++;
}
ans+=(long long)(cnt-1)*cnt/2;
sort(cur.begin(),cur.end());
int k=1;
for(auto x:cur) {
while(k<cur.size()&&cur[k]-x<n/2)k++;
if(k<cur.size())ans2=min(ans2,max(cur[k]-x,n-cur[k]+x)-min(cur[k]-x,n-cur[k]+x));
ans2=min(ans2,max(cur[k-1]-x,n-cur[k-1]+x)-min(cur[k-1]-x,n-cur[k-1]+x));
if(k==cur.size())break;
}
}
printf("%lld %d\n",ans,ans2);
return 0;
}
0%