[洛谷 5292,loj 3057][HNOI2019]校园旅行

题目链接

https://www.luogu.com.cn/problem/P5292

https://loj.ac/problem/3057

题解

是 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注