目录
显示
题目链接
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; }