Description
给定一个仅包含 a~h 的字符串。
有一个 $n$ 个结点的无向图，编号为 $0$ 到 $n−1$ 结点 $i$ 与结点 $j$ 间有边相连当且仅当 $|i-j|=1$ 或 $S_i=S_j$。
求这个无向图的直径和有多少对点间的最短距离与直径相同。
$n\leq10^5$
Solution
难是真的难，我看题解才懂，然后写代码时候挂了，又看了代码才过。。。
是个状压的妙用，思维难度不小。
先一步一步来。
很显然一个字母的边最多走一遍（因为走多遍和走一遍效果是一样的，而且不优）。
那么发现直径最大是 $15$，即 aabbccddeeffgghh 这个字符串，证明就用上面这个结论就行了，很显然。
然后考虑两点间最短路 $dis(i,j)$。
下面记 a~h 为 $8$ 种颜色。分别为 $c_0\sim c_7$，$f(i,c)$ 表示 第 $i$ 个点到 $c$ 颜色 的最短路长度，$T$ 为总颜色数。
想一想之后能得到：$dis(i,j)=\min(|i-j|,\min\limits_{0\leq k\leq7}\{f(i,k)+f(j,k)+1\})$。挺显然的，画个图或者想一想就明白了。
$f$ 数组可以枚举颜色然后 BFS 得到，$O(Tn)$，然后最短路直接暴力枚举是 $O(Tn^2)$ 的，得优化，然后我就不会了。
接下来就是看题解才会的东西了（）
看上面那个式子，对于每个点 $i$，在链上往前走 $15$ 个点，这些点到 $i$ 的最短路可能是全在链上，也可能不在，而再往前，就一定要走相同字母连出来的边了。
于是对于这 $15$ 个点，暴力算一下最短路。
对于剩下的点，$dis(i,j)=\min\limits_{0\leq k\leq7}\{f(i,k)+f(j,k)+1\}$。我们枚举点 $i$ 和颜色 $k$，需要快速得到前面所有点 $f(j,k)$ 的值以及个数。
不知道怎么做了，回头看一看有没有什么性质。
然后就定义 $g(a,b)$ 表示从颜色 $a$ 到颜色 $b$ 的最短路长度。
发现 $g(c_i,c_j)\leq f(i,j)\leq g(c_i,c_j)+1$。这个很显然，要么是直接走过去，要么先走到最近的，再走一条相同字符的边。
变个形，$f(i,j)-g(c_i,c_j)=0/1$。
那么我们发现每个点对后面答案的贡献只与其颜色和上面的 $f(i,j)$ 是两种情况的某一种有关，那么可以把每种颜色的状态作为状态压缩一下，记录每种颜色和这个状态的个数，在每个点枚举所有颜色和状态，就能知道前面所有点 $f(j,k)$ 的值对应的个数了。
这个 $g$ 也在 BFS 时候顺便求一下就行。
计算一下复杂度，预处理 $O(Tn)$，后面是 $O(T^22^Tn)$，算一下，发现达到了 $10^9$ 级别。2s 时限的话也许能过（？）。
我直接莽完交的时候最大的点跑了 $\text{1996ms}$，总时长 $\text{1.11min}$，真尬住了。。
后来加了个剪枝，快多了，最大的点只需要 $\text{468ms}$。（见代码）
似乎有点抽象，上代码（）
Code
有一些细节，颜色和点别弄混了。。。下标套下标有时候容易出错。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using std::cout;
using std::endl;
const int maxn = 1e5 + 10, maxt = 8, maxs = 1 << maxt;
char s[maxn];
int f[maxn][maxt + 1], g[maxt][maxt], cnt[maxt][maxs + 10];
int n, t = 8, used[maxt], a[maxn];
std::vector<int> p[maxt];
bool visi[maxn], visc[maxt];
int ans = 0;
long long tot = 0;
inline void updmi(int &a, int b) { a = std::min(a, b); }
inline void updans(int dis, int cnt)
{
if (cnt == 0)
return;
if (dis == ans)
tot += cnt;
else if (dis > ans)
ans = dis, tot = cnt;
}
int main()
{
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++)
a[i] = s[i] - 'a', p[a[i]].push_back(i);
memset(f, 1, sizeof(f)), memset(g, 1, sizeof(g));
std::queue<int> q;
for (int i = 0; i < t; i++)
{
memset(visi, 0, sizeof(visi)), memset(visc, 0, sizeof(visc));
g[i][i] = 0, visc[i] = 1;
for (int v : p[i])
q.push(v), visi[v] = 1, f[v][i] = 0;
while (!q.empty())
{
int now = q.front();
q.pop();
if (now > 1 && !visi[now - 1])
f[now - 1][i] = f[now][i] + 1, visi[now - 1] = true, q.push(now - 1);
if (now < n && !visi[now + 1])
f[now + 1][i] = f[now][i] + 1, visi[now + 1] = true, q.push(now + 1);
if (!visc[a[now]])
{
visc[a[now]] = 1, g[a[now]][i] = f[now][i];
for (int v : p[a[now]])
if (!visi[v])
f[v][i] = f[now][i] + 1, visi[v] = true, q.push(v);
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = std::max(1, i - 15); j < i; j++)
{
int dis = i - j;
for (int c = 0; c < t; c++)
updmi(dis, f[j][c] + f[i][c] + 1);
updans(dis, 1);
}
if (i > 16)
{
int nowst = 0;
for (int j = 0; j < t; j++)
nowst = (nowst << 1) | (f[i - 16][j] - g[a[i - 16]][j]);
cnt[a[i - 16]][nowst]++;
for (int j = 0; j < t; j++)
{
for (int k = 0; k < (1 << t); k++)
{
if (cnt[j][k] == 0) // 此处剪枝优化是很大的。
continue;
int dis = 1 << 30;
for (int q = 0; q < t; q++)
updmi(dis, f[i][q] + g[q][j] + ((k >> (t - q - 1)) & 1) + 1);
updans(dis, cnt[j][k]);
}
}
}
}
printf("%d %lld\n", ans, tot);
}
一点闲话
谁知道如何能想到这个 $g$ 啊，我想不到这个点。。