P9934 [NFLSPC #6] 绝不能忘记的事…… 题解

· · 题解

典型的思路简单实现稍复杂的 trie + map 字符串模拟题。

使用官方题解做法；附参考代码。

下令 S 为 string 类型，* 为通配符。

显然 N 在后面的情况和 N 在前面的情况本质上是一样的，可以进行一些处理后用同一种方法做。但是记得数组要清空。

先考虑 N 在前面的情况，令记录串为 NZH 的形式：

  1. NZH 在给定复制串中出现过，可以匹配的复制串有且仅有如下几种情况：

    • 复制串为 NZH：使用 map<S,int> 统计；

    • 复制串为 NP*，P 为 ZH 非空真前缀：使用字典树统计；

    • 复制串为 N*S，S 为 ZH 非空真后缀：同上；

    • 复制串为 N**：使用一个变量统计；

  2. NZH 在给定复制串中未出现过（NZ* 和 N*H 出现过），可以匹配的复制串有且仅有如下几种情况：

    • 复制串为 NP*，P 为 Z 非空前缀：使用字典树统计；

    • 复制串为 N*S，S 为 H 非空后缀：同上；

    • 复制串为 N**：使用一个变量统计。

再考虑 N 在中间的情况，令记录串为 QNH 的形式：

  1. QNH 在给定复制串中出现过，可以匹配的复制串有且仅有如下几种情况：

    • 复制串为 QNH：使用 map<pair<S,S>,int> 统计；

    • 复制串为 QN*：使用 map<S,int> 统计；

    • 复制串为 *NH：同上；

    • 复制串为 *N*：使用一个变量统计；

  2. QNH 在给定复制串中未出现过（QN* 和 *NH 出现过），可以匹配的复制串有且仅有如下几种情况：

    • 复制串为 QN*：使用 map<S,int> 统计；

    • 复制串为 *NH：同上；

    • 复制串为 *N*：使用一个变量统计。

几种情况取个最大值即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef string S;
namespace Trie{
  int t[2][1000001][26],c[2][1000001],o[2];
  void C(){
    memset(t,0,sizeof(t));
    memset(c,0,sizeof(c));
    o[0]=o[1]=0;
  }
  void I(int b,S s){
    int p=0;
    for(char i:s)
      if(t[b][p][i-97])p=t[b][p][i-97];
      else p=t[b][p][i-97]=++o[b];
    c[b][p]++;
  }
  int Q(int b,S s){
    int p=0,w=0;
    for(char i:s)
      if(t[b][p][i-97])w+=c[b][p=t[b][p][i-97]];
      else break;
    return w;
  }
} // 字典树模板
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<vector<pair<S,S> > > a(3);
  while(n--){
    S q,z,h; cin>>q>>z>>h;
    if(q=="N")a[0].emplace_back(z,h);
    else if(z=="N")a[1].emplace_back(q,h);
    else{
      if(q=="Q")q="H";
      else reverse(q.begin(),q.end());
      reverse(z.begin(),z.end());
      a[2].emplace_back(z,q);
      // 把 N 在后面的情况变成 N 在前面
    }
  } // 处理输入的字符串
  vector<int> c(3);
  for(int i=0;i<3;i++)
    if(int ca=0,cb=0,w=0;i&1){
      map<S,int> m1,m2;
      map<pair<S,S>,int> m3;
      for(auto [x,y]:a[i]){
        if(x!="Q"){
          if(y!="H")m3[make_pair(x,y)]++;
          else m1[x]++;
        }
        else if(y!="H")m2[y]++;
        else w++;
      } // 统计
      for(auto [x,y]:a[i]){
        if(x!="Q"){
          if(y!="H")c[i]=max(c[i],m1[x]+m2[y]+m3[make_pair(x,y)]);
          else ca=max(ca,m1[x]);
        }
        else if(y!="H")cb=max(cb,m2[y]);
      } // 计算答案
      c[i]=max(c[i],ca+cb)+w;
    } // N 在中间
    else{
      Trie::C();
      map<S,int> m;
      for(auto [x,y]:a[i]){
        S z=y; reverse(z.begin(),z.end());
        if(x!="Z"){
          if(y!="H")m[x+y]++;
          else Trie::I(0,x);
        }
        else if(y!="H")Trie::I(1,z);
        else w++;
      } // 统计
      for(auto [x,y]:a[i]){
        S e=x+y,r=e,z=y;
        reverse(r.begin(),r.end());
        reverse(z.begin(),z.end());
        e.pop_back(),r.pop_back();
        if(x!="Z"){
          if(y!="H")c[i]=max(c[i],m[x+y]+Trie::Q(0,e)+Trie::Q(1,r));
          else ca=max(ca,Trie::Q(0,x));
        }
        else if(y!="H")cb=max(cb,Trie::Q(1,z));
      } // 计算答案
      c[i]=max(c[i],ca+cb)+w;
    } // N 在前面
  cout<<*max_element(c.begin(),c.end())<<endl;
  return 0;
}