解析

比较复杂的一道题
看数据范围，我们肯定要从种类很少的颜色入手

因为第二种加边方式和颜色密切相关
所以设计$di{s}_{i,k}$表示 i 号节点到颜色为 k 的节点的最小步数
通过对每个k bfs一遍就能得出答案
然后两个点之间的距离就可以写出转移式：
$$f_{i,j}=\min (|i-j|,\underset{k}{\overset{8}{\min }}di{s}_{i,k}+di{s}_{j,k}+1)$$
考虑这样我们就得到了一种$n^2$的算法

考虑如何加速
首先，由于最差情况就是aabbcc…这样的情形，答案不会超过15，所以第一项我们只需要在距离[i-15,i-1]的区间考虑，可以暴力求解

关键是对后面一项的处理

设计$co{l}_{i,j}$表示从任意 i 颜色的块走到任意 j 颜色的块的最小步数
这个也可以在bfs时顺便转移
可以得到一个不等关系式：
$$co{l}_{a_i,j}\le di{s}_{i,j}\le co{l}_{a_i,j}+1$$
为什么？
也比较显然，如果任何一个不等关系不符合，col和dis数组就会在bfs时互相更新，使这个不等关系重新满足

所以，我们的dis-col的差值只可能为0或1,我们可以把8个对应的差值状态压缩，然后一起求解

实现上，建议把所有状态的结果预处理出来，会在瓶颈部分少一个8的循环，应该快很多

代码

#include<bits/stdc++.h>const int N=1e5+100;
const int mod=1e9+7;
#define ll long long
using namespace std;
inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}int n,m;int col[9][9],dis[N][9],a[N];
bool vis[N];
char s[N];
int q[N],st,ed;
int dx[3]={0,1,-1};
vector<int>v[9];
void bfs(int k){memset(vis,0,sizeof(vis));st=1;ed=0;for(int i=1;i<=n;i++){if(a[i]==k) q[++ed]=i,vis[i]=1;}col[k][k]=0;while(st<=ed){int now=q[st++];for(int i=1;i<=2;i++){int to=now+dx[i];if(vis[to]||to==0||to>n) continue;vis[to]=1;dis[to][k]=dis[now][k]+1;q[++ed]=to;}if(col[k][a[now]]==1e9){col[k][a[now]]=dis[now][k];for(int i=0,tp=v[a[now]].size();i<tp;i++){int x=v[a[now]][i];if(!vis[x]){dis[x][k]=dis[now][k]+1;q[++ed]=x;vis[x]=1;}}}}return;
}
int mi[15],cst[2060][2060];
int sta[N],num[2060];
int main(){
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read();scanf(" %s",s+1);for(int i=1;i<=8;i++){for(int j=1;j<=8;j++) col[i][j]=1e9;}for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1,v[a[i]].push_back(i);for(int i=1;i<=8;i++) bfs(i);mi[0]=1;for(int i=1;i<=11;i++) mi[i]=mi[i-1]<<1;for(int i=0;i<mi[11];i++){for(int j=0;j<mi[11];j++){int a=(i>>8)+1,b=(j>>8)+1;int res=2e9;for(int k=1;k<=8;k++){res=min(res,col[a][k]+1+col[b][k]+((i&mi[k-1])?1:0)+((j&mi[k-1])?1:0));}cst[i][j]=res;}}for(int i=1;i<=n;i++){int s=a[i]-1,o=a[i];for(int k=8;k>=1;k--){s<<=1;if(dis[i][k]>col[o][k]) s|=1;}sta[i]=s;}int ans(0);ll sum(0);for(int i=1;i<=n;i++){for(int j=max(i-15,1);j<i;j++){int w=min(i-j,cst[sta[i]][sta[j]]);if(w>ans){ans=w;sum=1;}else if(w==ans) sum++;}for(int s=0;s<mi[11];s++){if(!num[s]) continue;if(cst[s][sta[i]]>ans) ans=cst[s][sta[i]],sum=num[s];else if(cst[s][sta[i]]==ans) sum+=num[s];}if(i>=16) num[sta[i-15]]++;}//printf("st[1]=%d st[7]=%d\n",sta[1],sta[7]);//printf("dis[1][1]=%d col[3][1]=%d\n",dis[1][1],col[3][1]);printf("%d %lld\n",ans,sum);return 0;
}