BZOJ 4382 Podział naszyjnika

发表于 | 更新于

Link

看到题，转化了一番，搞出了一个类似"选出不与别的边相交的边"之类的东西。。然后感觉非常复杂不会做 其实正解的思路也差不多，只是没有刻意去套那么鬼畜的模型。。

Solution

对于每种颜色，断点只能在相邻的两个珠子之间。 如果两条边能满足对于每种颜色，都在这种颜色相邻同一对珠子之间，就可以取。 所以！ 对每种颜色，把相邻的两个珠子中间的片段都编上号。 这样，如果两条边的每种颜色的编号都相同，就可以取。这一步用哈希实现。 这样，对于一段哈希值相同的点，用乘法原理算方案数，用双指针算最优解。

Tips

坑点 如果在算哈希的时候碰上了每种颜色在链上的第一个珠子，需要把1..first,last..n1..first,last..n都标上同一个号。 双指针的时候，右指针必须在解开始变差之前停下，否则可能影响左指针移动之后的计算。 so 要格外小心拆环的边界情况 双指针要如上地写 and 如果做题的时候套的模型太鬼畜导致不会处理，不一定是想法错了。。可以回归本质，用正常一些的模型试试

Code

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
#include "lucida"

typedef unsigned long long qword;
using std::partial_sum;
using std::pair;
using std::make_pair;
using std::sort;

const int MAXN=1000000+11,MAXM=MAXN;
int main() {
//	freopen("input","r",stdin);
	static int pre[MAXN],c[MAXN],last[MAXM];
	static qword hcode[MAXN];
	static pair<qword,int> hi[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=n;++i) {
		is>>c[i];
		pre[i]=last[c[i]];
		last[c[i]]=i;
	}
	qword BASE=9999929,POW=1;
	//n--[n th]--1--[1 st]--2--[2 nd]--
	for(int col=1;col<=m;POW*=BASE,++col) {
		qword HASH=POW;
		for(int i=last[col];i;HASH+=POW,i=pre[i]) {
			//当前处理的边的区间是[pre[i],i)
			if(pre[i]) {
				hcode[pre[i]]+=HASH;
				hcode[i]-=HASH;
			} else {
				hcode[last[col]]+=HASH;
				hcode[1]+=HASH;
				hcode[i]-=HASH;
			}
		}
	}
	partial_sum(hcode+1,hcode+1+n,hcode+1);
	for(int i=1;i<=n;++i)
		hi[i]=make_pair(hcode[i],i);
	sort(hi+1,hi+1+n);
	qword Ans=0;
	int mind=n;
	#define dist(i,j) ((i)<=(j)?(j)-(i):(n-((i)-(j))))
	#define calc(i,j) (abs(dist((i),(j))-dist((j),(i))))
	for(int l=1,r=l;r<=n;l=r=r+1) {
		while(hi[l].first==hi[r+1].first) 
			r++;
		Ans+=1ULL*(r-l+1)*(r-l)/2;
		for(int i=l,j=i+1;i+1<=r;++i) {
			j=(i==j)?i+1:j;
			int diff=calc(hi[i].second,hi[j].second);
			chkmn(mind,diff);
			while(j+1<=r && chkmn(diff,calc(hi[i].second,hi[j+1].second))) {
				chkmn(mind,diff);
				j++;
			}
		}
	}
	os<<Ans<<' '<<mind<<'\n';
	return 0;
}