目录
显示
题目链接
https://www.luogu.com.cn/problem/P5292
题解
是 myy 的题 orz
首先给个回文串的形式化递归定义：
- 只有一个字符的串是回文串。
- 只有两个字符的串，如果这两个字符相同，也是回文串；
- 如果 \(S\) 是回文串，那么在 \(S\) 的开头和末尾插入一个相同的字符，形成的新串也是回文串。
根据前两条，我们可以预处理出所有长度为 \(1\)（只经过一个点）和长度为 \(2\)（两个点通过一条边直接相连）的回文串。
根据第三条，我们可以在已有的回文串基础上，尝试在开头和结尾各添加一个新的字符，产生新的回文串。
具体来说，设 \(f_{i,j}\) 表示从 \(i\) 到 \(j\) 是否存在一条回文路径。刚开始将所有长度为 \(1\) 和 \(2\) 的回文串状态加入队列。每次取出一个状态 \((i,j)\)，遍历 \(i\) 的所有出点，遍历 \(j\) 的所有出点，看是否能扩展出新的回文串。如果可以，就将新的回文串压入队列中。
时间复杂度 \(O(m^2)\)。
这个转移本身没有什么太大优化空间，我们只能从降低 \(m\) 的规模入手。
考虑连接两个标号相同的点的所有边，这些边能够形成若干个连通块。
每个连通块有两种情况：
- 如果连通块是二分图（不存在奇环），经过偶环并不会对串的长度的奇偶性造成改变，再加上允许一条边可以走多次，因此没有必要保留环，只需保留这个连通块的一个生成树即可。
- 如果连通块不是二分图（存在奇环），经过奇环会影响串长度的奇偶性，为了方便处理，我们仍然只保留这个连通块的生成树，并在这个连通块的其中一个点上加一个自环（从而留下改变奇偶性的机会）。
如果把每个颜色相同的连通块看作一个点，所有不同颜色的点之间也能形成若干连通块。容易看出，这些连通块里都不存在奇数环。
因此和上面同理，我们只用保留每个连通块的一个生成树即可，剩下成环的边都可以删除。
最后会剩下多少边呢？可以证明，最多不超过 \(2n-2\) 条边。
从而我们将 \(m\) 的规模降到了与 \(n\) 同阶，我们可以在 \(O(n^2)\) 的时间复杂度内解决本题。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> pii;
struct dsu
{
int fa[5005];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool merge(int x,int y)
{
x=find(x),y=find(y);
if(x==y)return false;
fa[y]=x;
return true;
}
}d;
int n,m,q;
int col[5005];
char s[5005];
bool flag;
bool res[5005][5005];
vector<int> e1[5005],e2[5005];
queue<pii> que;
void dfs(int u,int c)
{
col[u]=c;
for(auto v:e2[u])
if(col[v]==col[u])flag=false;
else if(col[v]==-1)
{
e1[u].push_back(v);
e1[v].push_back(u);
dfs(v,c^1);
}
}
int main()
{
ios::sync_with_stdio(false);
memset(col,-1,sizeof(col));
cin>>n>>m>>q;
cin>>(s+1);
d.init(n);
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
if(s[u]!=s[v])
{
if(d.merge(u,v))
{
e1[u].push_back(v);
e1[v].push_back(u);
}
}
else
{
e2[u].push_back(v);
e2[v].push_back(u);
}
}
for(int i=1;i<=n;i++)
if(col[i]==-1)
{
flag=true;
dfs(i,0);
if(!flag)e1[i].push_back(i);
}
for(int i=1;i<=n;i++)
que.push({i,i}),res[i][i]=true;
for(int u=1;u<=n;u++)
for(auto v:e1[u])
{
if(v!=u&&s[u]==s[v])
que.push({u,v}),res[u][v]=true;
}
while(!que.empty())
{
int x=que.front().first,y=que.front().second;
que.pop();
for(auto v1:e1[x])
for(auto v2:e1[y])
if(s[v1]==s[v2])
if(!res[v1][v2])
res[v1][v2]=true,que.push({v1,v2});
}
while(q--)
{
int x,y;
cin>>x>>y;
cout<<(res[x][y]?"YES":"NO")<<endl;
}
return 0;
}