[UOI2024] Lady's Gift 题解

· · 题解

记 s[l,r] 表示字符串 s 下标在范围 [l,r] 内的子串。下文中字符串下标全部从 0 开始。

考虑 q=0 怎么做，显然现在每个点上面的字符已经确定了，于是只需要找后继。由于给出的字符串长度为 3n，所以一个点 u 的后继 p_u 必然满足 s_u[1,3n-1]=s_{p_u}[0,3n-2]。直接对于每个 u 暴力枚举 p_u，用字符串哈希判等，即可通过 q=0 的 63 分。

那么如何扩展到正解？注意到正解比 q=0 多出来的东西是一些字符串未知的结点，沿用上面的方法，如果某一个点 u 没找到后继，那么直接将后继设为某个字符串未知的结点 v；显然可以通过这样的方式确定整个 s_v——具体地可以发现 s_v 相当于 s_u 删掉首字母再在末尾加上一个字母，而 s_u 的长度为 3n 所以可以直接枚举基环树上环的长度（用哈希判断这个长度是否合法），进而可以唯一确定 s_v 的最后一位；之后再递归下去给 s_v 找后继……题目保证有解，所以这样的操作过程是正确的。

枚举长度并判定循环的部分是经典调和级数时间复杂度，而我们要对于每个找不到后继的字符串都做一遍，所以总的时间复杂度为 O(n^2\log n)，常数非常小可以通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int B=6907,P=1e9+9;
class hashing{
  private:
    vector<int> p,h;
  public:
    hashing(string a){
      p.resize(a.size()+1),h.resize(a.size());
      for(int i=p[0]=1;i<=a.size();i++)
        p[i]=1ll*p[i-1]*B%P;
      for(int i=0;i<a.size();i++)
        h[i]=(1ll*(i?h[i-1]:0)*B+a[i]-96)%P;
    }
    inline int get(int l,int r){
      return (h[r]-(l?1ll*h[l-1]*p[r-l+1]%P:0)+P)%P;
    }
}; // 字符串哈希模板
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  vector<string> s(n);
  vector<int> v;
  for(auto &i:s)cin>>i;
  vector<optional<hashing> > h(n);
  for(int i=0;i<n;i++){
    h[i].emplace(s[i]);
    if(s[i][0]=='?')v.emplace_back(i);
  } // 预处理一些信息
  vector<int> p(n,-1);
  auto gen=[&](int x,int y){
    auto t=s[x].substr(1,n*3-1);
    for(int l=1;l<=n;l++){
      bool f=true;
      for(int j=n*3-l;j>=n&&f;j-=l)
        f&=h[x]->get(j,j+l-1)==h[x]->get(n*3-l,n*3-1);
      if(f){t+=s[x][n*3-l]; break;}
    }
    return t;
  }; // 通过 s[x] 生成 s[y]，即删一个字母加一个字母的过程
  auto dfs=[&](auto &&self,int x)->int{
    for(int i=0;i<n;i++)
      if(s[i][0]!='?'&&h[x]->get(1,n*3-1)==h[i]->get(0,n*3-2))return i;
    int y=v.back(); v.pop_back(); // 没找到，取一个字符串未知的
    return h[y].emplace(s[y]=gen(x,y)),p[y]=self(self,y),y;
  }; // 找后继
  for(int i=0;i<n;i++)
    if(s[i][0]!='?')p[i]=dfs(dfs,i);
  for(int i=0;i<n;i++)
    if(p[i]<0)s[i][0]='q',p[i]=i; // 剩下的未确定的随便填
  for(int i=0;i<n;i++)
    cout<<s[i][0];
  cout<<endl;
  for(int i:p)cout<<i+1<<' ';
  cout<<endl;
  return 0;
}