OI - Matvey's Birthday(Codeforces)

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


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!

再也不想做搜索题了(啊~搜索还是香啊!

0%