OI - Matvey's Birthday(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Matvey's Birthday(Codeforces)

发表于 分类于 Valine：

开始验证你是不是出题人……

Part1. 题面

> 传送门(Codeforces)

有一个 $n$ 个点的图，每个点有一个颜色，点的编号为 $1$ 到 $n$。共有不超过 $8$ 种颜色，编号为 a~h。
对于 $i\in[2,n]$，编号为 $i$ 的点与编号 $i-1$ 的点之间有一条无向边。另外，两个颜色相同的点之间也有无向边。

现给出所有点的颜色，求这张图的直径的长度以及直径的数量。（图的直径是图上任意两点间最短距离的最大值）

数据规模：$1\le n\le10^5$

Part2. 题解

Part2/1. 函数定义

定义 $dis(u,v)$ 表示点 $u,v$ 的最短距离，$c_u$ 为点 $u$ 的颜色。然后再定义两个函数：

  1. $f(u,c)$ ：点 $u$ 到任意一个颜色为 $c$ 的点的最小距离，即：

  2. $g(a,b)$：任意一个颜色为 $a$ 的点 $u$ 到任意一个颜色为 $b$ 的点 $v$ 的距离，即：

> Hint.
先看懂定义，至于有什么用，之后就知道了

$f(u,c)$ 可以对每一种 $c$ 做一次 BFS 求出，然后就可以进一步求得 $g(a,b)$ 了。

Part2/2. 结论

接下来证明一些结论：

  1. 任意两点的距离不会超过 $15$；
    任意两点之间的路径上，一定不会出现超过两个颜色相同的点（否则就可以不经过中间那个点），总共 $8$ 种颜色，就不会超过 $16$ 个点，即长度不会超过 $15$。

  2. $dis(u,v)=\min\{|u-v|,f(u,c)+f(v,c)+1\}$ （$c\in[0,7]$）；

    对应了两种方案：$|u-v|$ 即从 $u$ 出发，只走 $i\to i\pm1$ 的边；$f(u,c)+f(v,c)+1$ 则对应了从 $u$ 先走到颜色为 $c$ 的点，再通过相同颜色的点之间的边走到另一个颜色为 $c$ 的点，最后走到 $v$ 点

  3. $f(u,c)$ 的值要么为 $g(c_u,c)$，要么为 $g(c_u,c)+1$；

    比较明显，为 $g(c_u,c)$ 时，说明从 $u$ 出发直接到达一个颜色为 $c$ 的点是最短的；为 $g(c_u,c)+1$ 时，说明要先从 $u$ 走一步到离颜色为 $c$ 的点最近的另一个颜色与 $u$ 相同的点

结合第 1,2 个结论，不难发现当 $|u-v|>15$ 时，$dis(u,v)=f(u,c)+f(v,c)+1$ 。

Part2/3. 求解

直径即 $\max\{dis(u,v)\}$。为了避免 $u,v$ 计算重复，只考虑 $v<u$ 的情况。那么其实就是要计算有多少对 $(u,v)$ 满足 $\min\{|u-v|,f(u,c)+f(v,c)+1\}$ 最大。

对于 $|u-v|\le15$ 的情况，需要取 $\min$，比较麻烦，但是显然 $15$ 是比较小的数，可以直接枚举 $v\in[u-15,u-1]$，然后计算答案。

1
2
3
4
5
6
7
for(int j=max(1,i-15);j<i;j++){ //i,j 即 u,v
	int now=i-j;
	for(int k=0;k<8;k++)
		now=min(now,f[i][k]+f[j][k]+1);
	if(now>ans) ans=now,cans=0; //ans是当前算出的直径长度，cans统计数量
	if(now==ans) cans++;
}

对于 $|u-v|\ge16$ 的情况，$dis(u,v)$ 一定为 $f(u,c)+f(v,c)+1$。但是这种情况下 $v$ 的规模比较大，不能直接枚举计算。考虑能否通过 $g(a,b)$ 来求解 $f(u,c)+f(v,c)+1$。因为 $g(a,b)$ 的规模是 $8\times8$ ，可以接受。

根据 Part2/2. 所述的结论 3：对每一个点 $u$，存储一个二进制状态 $S_u$。如果 $f(u,c)=g(c_u,c)+1$，则 $S_u$ 的第 $c$ 位为 $1$，否则为 $0$。那么 $f(v,c)$ 就可以转换为 $f(c_v,c)+[c\in S_v]$。

> Hint
$[c\in S_v]$ ：如果 $S_v$ 的第 $c$ 位为 $1$，则 $[c\in S_v]=1$ ，否则为 $0$。

根据所得式子，不难发现：如果点 $v_1,v_2$ 的颜色相同，且 $S_{v_1}=S_{v_2}$，那么 $f(v,c)$ 一定相同。

那么我们统计 cnt[S][c] 表示 $v\in[1,u-16]$ 且 $S_v=S$，$c_v=c$ 的 $v$ 的数量。就可以得到

的 $v$ 的数量，就可以计算答案了！

1
2
3
4
5
6
7
8
9
for(int j=0;j<8;j++) //枚举 v 的颜色 c_v
	for(int S=(1<<8)-1;S>=0;S--) //枚举 S_v
		if(cnt[S][j]){
			int now=inf;
			for(int c=0;c<8;c++)
				now=min(now,f[i][c]+1+g[j][c]+(S>>c&1));
			if(now>ans) ans=now,cans=0;
			if(now==ans) cans+=cnt[S][j];
		}

Part3. 源代码

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5;

int n,inf;
char str[N+10];
int idx[N+10],f[N+3][8],g[8][8],mak[N+3],cnt[1<<8][8];
queue< int > que;

void CalF(int col){
	for(int i=1;i<=n;i++)
		if(idx[i]==col){
			que.push(i);
			f[i][col]=0;
		}
	bool vis[8]={};
	vis[col]=true;
	while(!que.empty()){
		int u=que.front();que.pop();
		if(!vis[idx[u]]){
			vis[idx[u]]=true;
			for(int i=1;i<=n;i++)
				if(idx[i]==idx[u] && f[i][col]==inf){
					f[i][col]=f[u][col]+1;
					que.push(i);
				}
		}
		for(int i=-1;i<=1;i+=2){
			int v=u+i;
			if(v<1 || v>n || f[v][col]!=inf) continue;
			f[v][col]=f[u][col]+1;
			que.push(v);
		}
	}
}
int main(){
	scanf("%d%s",&n,str+1);
	for(int i=1;i<=n;i++) idx[i]=str[i]-'a';
	memset(f,0x3f,sizeof f);inf=f[0][0];
	for(int i=0;i<8;i++) CalF(i);
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=n;i++)
		for(int j=0;j<8;j++)
			g[idx[i]][j]=min(g[idx[i]][j],f[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=0;j<8;j++)
			mak[i]|=(f[i][j]==g[idx[i]][j]+1)<<j;
	int ans=-1;long long cans=0;
	for(int i=1;i<=n;i++){
		for(int j=max(1,i-15);j<i;j++){
			int now=i-j;
			for(int k=0;k<8;k++)
				now=min(now,f[i][k]+f[j][k]+1);
			if(now>ans) ans=now,cans=0;
			if(now==ans) cans++;
		}
		if(i-16>=1) cnt[mak[i-16]][idx[i-16]]++;
		for(int j=0;j<8;j++) //i -> color=j
			for(int S=(1<<8)-1;S>=0;S--)
				if(cnt[S][j]){
					int now=inf;
					for(int c=0;c<8;c++)
						//f[j][c]=g[colorj][c]+mark[colorj][c]
						now=min(now,f[i][c]+1+g[j][c]+(S>>c&1));
					if(now>ans) ans=now,cans=0;
					if(now==ans) cans+=cnt[S][j];
				}
	}
	printf("%d %lld\n",ans,cans);
	return 0;
}

The End

Thanks for reading!

再也不想做搜索题了（啊~搜索还是香啊！）