[南海云课堂] [SPFA] [二分答案] [巧妙转换] 单词串

_Cheems · 2023-08-18 16:31:28 · 个人记录

题意

我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。

如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。

我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。

如下例：

ababc

bckjaca

caahoynaab

第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 5+7+10=22（重复部分算两次），总共使用了 3 个串，所以平均长度是 223≈7.33。

## 思路 * ### 歪解：缩点无法保证百分百正确，不详讲。观察题目，显然可以建边，又因为答案与环有关，因此考虑求强连通分量，在弹出栈这一步时计算答案即可。但很容易被卡，因为题目要求平均值，而最大的均值不一定在极大强连通分量中。而且这种做法很容易 $\rm{MLE}$，不要用为好。 ~~其实卡一卡就能过随机数据。~~ * ### 二分 + $\rm{SPFA}

首先我们发现，朴素建边不仅会爆空间还很麻烦，没有利用边权。

观察到前后缀共有 26^2 种不同形态，不妨将前后缀设为节点，字符串长度设为边权，这样将几种元素都很好地利用起来。例如：abac，我们就将 ab 到 ac 连一条权为 4 的边。

其次，直接找遍历环很难实现。由复杂度理论知：判断性问题比直接做要简单，那不妨二分答案平均长度。

最后就是 check 函数了。平均长度 k 合法，当且仅当存在任意环使得 \frac {\sum\limits_{i=1}^{tot} {w_i}}{tot}\ge k。变式一下得：\sum\limits_{i=1}^{tot} wi\ge \sum\limits_{i=1}^{tot} k\to \sum\limits_{i=1}^{tot}(wi-k)\ge0。

于是将每条边减去 k，\rm{SPFA} 跑最长路判断是否存在正环即可。

代码

没有太多可说，主要是思路咋来的。

二分 + \rm{SPFA}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=4e5+5,K=7e2+5,P=2e3;
int t,n,val[N],head[K],cnt,f[K],tot;
int x,y;
double dis[K];
string s;
struct ed{
  int v,nxt,w;
}e[M];
inline void add(int u,int v,int w){
  e[++cnt]={v,head[u],w};
  head[u]=cnt;
}
inline int getq(string s){
  return (s[0]-'a'+1)*26+(s[1]-'a'+1);
} 
inline int geth(string s){
  return (s[s.size()-2]-'a'+1)*26+(s[s.size()-1]-'a'+1);
}
inline bool SPFA(double p){
  memset(dis,0,sizeof dis);
  memset(f,0,sizeof f);
  queue<int>q;
  for(int i=0; i<=700;i++){
      q.push(i);
  }
  tot=0;
  while(!q.empty()){
      int u=q.front();
      q.pop();
      for(int i=head[u]; i;i=e[i].nxt){
          int v=e[i].v;
          if(dis[u]+e[i].w-p>dis[v]){
              dis[v]=dis[u]+e[i].w-p;
              f[v]++; tot++;
              if(f[v]>1000||tot>20000) return true;
              q.push(v);
          }
      }
  }
  return false;
}
int main()
{
  scanf("%d",&n);
  while(n!=0){
      memset(head,0,sizeof head);
      cnt=0;
      for(int i=1; i<=n;i++){
          cin>>s;
          if(s.size()<2) continue;
          x=getq(s); y=geth(s);
          add(x,y,s.size());
      }
      double l=0,r=1000,mid;
      while(l+1e-5<r){
          mid=1.0*(l+r)/2;
          if(SPFA(mid)) l=mid;
          else r=mid;
      }
      if(l<=0){
          printf("No solution\n");
      }
      else{
          printf("%.2f\n",l);   
      }
      scanf("%d",&n);
  }
  return 0;
}

缩点

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=1e5+5,M=4e6+5,K=2e4+5;
const ull base=1331,mod=19991;
int n,val[N],head[N],cnt;
int low[N],vis[N],dfn[N],df;
int st[N],top;
double ans;
string s;
ull x,y;
struct ed{
  int v,nxt;
}e[4*M];
inline void add(int u,int v){
  e[++cnt]={v,head[u]};
  head[u]=cnt;
}
inline int getq(string s){
  return ((s[0]-'a'+1)*base*base+(s[1]-'a'+1)*base+55)%mod+1;
} 
inline int geth(string s){
  return ((s[s.size()-2]-'a'+1)*base*base+(s[s.size()-1]-'a'+1)*base+55)%mod+1;
}
vector<int>qx[K],hx[K];
inline void tarjan(int u){
  dfn[u]=low[u]=++df;
  vis[u]=1;
  st[++top]=u;
  for(int i=head[u]; i;i=e[i].nxt){
      int v=e[i].v;
      if(vis[v]==2) continue;
      if(!vis[v]){
          tarjan(v);
          low[u]=min(low[u],low[v]);
      }
      else{
          low[u]=min(low[u],dfn[v]);
      }
  }
  if(dfn[u]==low[u]){
      double s=0,res=0;
      int v;
      do{
          v=st[top--];
          res+=val[v];
          s++;
          vis[v]=2;
      }while(top&&v^u);
      if(s>1) ans=max(ans,1.0*res/s);
  }
}
int main(){
  scanf("%d",&n);
  while(n!=0){
      memset(qx,0,sizeof qx);
      memset(hx,0,sizeof hx);
      memset(vis,0,sizeof vis);
      df=0;
      ans=-1;
      for(int i=1; i<=n;i++){
          cin>>s;
          val[i]=s.size();
          if(s.size()<2) continue;
          x=getq(s); y=geth(s);
          qx[x].push_back(i);
          hx[y].push_back(i);
          for(int j=0; j<qx[y].size();j++){
              add(i,qx[y][j]);
          }
          for(int j=0; j<hx[x].size();j++){
              add(hx[x][j],i);
          }
          if(x==y){
              ans=max(ans,1.0*s.size());
          }
      }
      for(int i=1; i<=n;i++){
          if(!vis[i]){
              top=0; df=0;
              tarjan(i);
          }
      }
      if(ans==-1){
          printf("No solution\n");
      }
      else {
          printf("%.2f\n",ans);
      }
      scanf("%d",&n);
  }
  return 0;
}