[ABC354G] Select Strings 题解

FFTotoro · 2024-05-18 22:36:58 · 题解

赛时这个一遍过，全场 rk 28。写题解以纪念。

首先考虑用 KMP 暴力处理出每一对字符串可不可以同时选，如果能选就连边，转换为一般图带权最大独立集问题。

最大独立集可以用求最大团的方法求出（直接随机排列），但是带权的不太好做。于是考虑爬山，先将初始排列按照权值排序，如果这样直接贪心选肯定是错的；但是我们每次循环随机交换其中的 3 对元素，然后判断解是不是比当前解更优，如果是那么更新答案。卡时后可以通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
inline bool find(string text,string pattern){
  /* 字符串匹配 KMP 模板，请自行补全 */
}
int st; inline long long wmis(vector<vector<int> > b,vector<int> a){
  int n=a.size();
  for(auto &i:b)for(auto &j:i)j=!j;
  vector<int> p(n),r;
  iota(p.begin(),p.end(),0);
  sort(p.begin(),p.end(),[&](int x,int y){
    return a[x]>a[y];
  }); // 初始排列
  long long w=a[p[0]]; mt19937 g;
  uniform_int_distribution<> u(0,n-1);
  while(r.size()<n&&1.0*(clock()-st)/CLOCKS_PER_SEC<1.98){
    auto q=p;
    for(int i=0;i<3;i++)
      swap(q[u(g)],q[u(g)]);
    vector<int> v; long long c=0;
    for(int i:q){
      bool f=true;
      for(int j:v)f&=b[i][j];
      if(f)v.emplace_back(i),c+=a[i];
    } // 找最大团
    if(c>w)p=q,w=c; // 更新答案
  } // 卡时
  return w;
} // 找最大权独立集
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  st=clock(); int n; cin>>n;
  vector<string> s(n);
  for(auto &i:s)cin>>i;
  vector b(n,vector<int>(n));
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      if(find(s[i],s[j]))b[i][j]=b[j][i]=true; // 建图
  vector<int> a(n);
  for(auto &i:a)cin>>i;
  cout<<wmis(b,a)<<endl;
  return 0;
}