题目链接
我是奶龙，这种题目做不出来。
问题不妨转化成：
给定一个长度为 \(n\) 的序列，每个点有权值 \(a_i\)，每次移动可以走到相邻节点或者同色节点，求从 \(s\) 到 \(t\) 所需的最少时间
这个问题大抵是挺经典的。考虑建模成图论。显然的，可以对于相邻位置连一个大小为 1 的边，但是如果对于同色节点两两连边，边数可以来到 \(O(n^2)\)，难以接受，因此对于每种颜色建立一个超级原点，使得节点连向超级原点所需的权值为1，超级原点连向节点需要的权值为0。
但是这样子直接建图跑还是会 TLE，继续优化。观察到这道题原点的个数很少，因此尝试使用原点进行搜索。但是一个节点是否会到原点，这便是这道题卡住我的地方。实际上，我们可以分类讨论。如果一个节点没有来到原点，那么肯定是直接走，否则必定要先到一个原点。可以枚举这个原点，时间复杂度是正确的。具体实现看代码。
Code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 5e4 + 26 * 26 + 10,M = 26 * 26 + 10;
string s;
int n;
vector< pair<int,int> > G[N];
int f[M][N],g[M][N];//all,only
const int INF = 1e9 + 7;
int vis[N];
inline void getmin(int &a,int b){if(a > b) a = b;
}
inline void bfs1(int st){int fake = st - n;for(int i=0;i<=n+26*26;i++)g[fake][i] = INF;g[fake][st] = 0;for(pair<int,int> e : G[st]){g[fake][e.fi] = 0;}for(int i=1;i<=n;i++){getmin(g[fake][i],g[fake][i-1] + 1);}for(int i=n-1;i>=1;i--)getmin(g[fake][i],g[fake][i+1] + 1);
}
inline void bfs2(int st){int fake = st - n;deque<int> q;q.push_back(st);for(int i=1;i<=n+26*26;i++)f[fake][i] = INF;f[fake][st] = 0;while(!q.empty()){int u = q.front();q.pop_front();if(vis[u] == fake + 26 * 26) continue;vis[u] = fake + 26 * 26;for(pair<int,int> e : G[u]){int v = e.fi,w = e.se;if(f[fake][v] > f[fake][u] + w){f[fake][v] = f[fake][u] + w;if(w == 0) q.push_front(v);else q.push_back(v);}}}
}
int main()
{IOS;cin >> s;n = s.size();s = " " + s;for(int i=1;i<n;i++){if(i > 1) G[i].push_back({i-1,1});if(i < n - 1)G[i].push_back({i+1,1});int x = n + (s[i] - 'a') * 26 + (s[i+1] - 'a') + 1;G[x].push_back({i,0});G[i].push_back({x,1});}for(int i=n+1;i<=n+26*26;i++){bfs1(i);bfs2(i);}int Q;cin >> Q;while(Q -- ){int st,ed;cin >> st >> ed;int ans = abs(ed - st);for(int i=n+1;i<=n+26*26;i++)getmin(ans,g[i-n][st] + 1 + f[i-n][ed]);cout << ans << "\n";}return 0;
}
后记
赞美【数据删除】，在缩小原题时限的同时，不知道自己评测机跑的有多慢，卡常卡了半天，靠评测波动过去了。