[NEFU ACM大一暑假集训解题报告]字典树

标签：int res LL ACM son NEFU str 大一 include

[NEFU ACM大一暑假集训解题报告]字典树

题目

A - L 语言

多模式匹配，AC自动机建立Trie图。不过这个题数据量很小，貌似可以暴力建立跳转关系，加上标记处理即可。

对于样例的AC自动机（Trie图）应该长下面这样，省略了所有结点到根结点的跳转。

[NEFU ACM大一暑假集训解题报告]字典树_#include

单纯Trie+暴力建立跳转关系+标记应该也可以实现。AC自动机在Trie树上使用KMP的思想进行多模式匹配。主要的话，优化了跳转关系的建立（fail指针）。

fail指针或者说失配指针其实就是一种反悔的操作。我们走某一条路径，走到一般发现走不下去了，就想要回去走其他路径，而失配指针直接建立fail边，让你跳转到要去的地方（上图红色的边），大致明白这个思想就行。

其实感觉如果AC自动机做难点主要在怎么写匹配过程（因为其他都是板子哈哈哈）

匹配求答案过程借鉴洛谷这篇题解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<vector>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
#define endl '\n'
//CHECK MULTIPLY INPUT  !!!
//NEW DATA CLEAN    !!!
//THINK > CODE   !!!
const int N=2E6+10;
int n,m;
int tr[N][26],cnt[N],idx;
char str[N];
int q[N],fail[N];
bool vis[N];
void insert(){
    int p=0;
    for(int i=0;str[i];i++){
        int t=str[i]-'a';
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]=strlen(str);
}

void build(){
    int hh=0,tt=-1;
    for(int i=0;i<26;i++){//从第一层开始搜索
        if(tr[0][i])q[++tt]=tr[0][i];
    }
    while(hh<=tt){//BFS构建Trie图
        int t=q[hh++];
        for(int i=0;i<26;i++){
            int p=tr[t][i];
            if(!p)tr[t][i]=tr[fail[t]][i];
            else{
                fail[p]=tr[fail[t]][i];
                q[++tt]=p;
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){//构建Trie树
        scanf(" %s",str);
        insert();
    }
    build();//AC自动机建Trie图
    while(m--){//AC自动机匹配
        int res=0;
        scanf("%s",str);
        memset(vis,0,sizeof vis);
        vis[0]=1;
        for(int i=0,j=0;str[i];i++){
            int t=str[i]-'a';
            j=tr[j][t];//Trie图的某个结点
            int p=j;
            while(p){
                if (vis[i - cnt[p] + 1]){//判断之前是否存在一个合法前缀
                    vis[i + 1] = true;//标记一下
                    break;//一个优化，如果找到了就直接退出，不然会T掉最后一个点
                }
                p=fail[p];//向上回溯，防止漏答案
            }
            if(vis[i+1])res=i+1;
        }
        printf("%d\n",res);
        
    }
    return 0;
}

B - Secret Message 秘密信息

插入的时候记录每个结点经过的次数以及以该结点为结尾的数量。相减去掉重复部分即可。

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=500010;
int a[N],son[M][2],ed[M],pas[M],idx;
void insert(int* a,int k){
  int p=0;
  for(int i=0;i<k;i++){
    if(!son[p][a[i]])son[p][a[i]]=++idx;
    p=son[p][a[i]];
    pas[p]++;
  }
  ed[p]++;
}
int query(int* a,int k){
  int res=0,p=0;
  for(int i=0;i<k;i++){
    if(!son[p][a[i]])return res;
    p=son[p][a[i]];
    res+=ed[p];
  }
  return res+pas[p]-ed[p];
}
int main(){
  int n,m;cin>>n>>m;
  for(int i=0;i<n;i++){
    int k;cin>>k;
    for(int j=0;j<k;j++)cin>>a[j];
    insert(a,k);
  }
  for(int i=0;i<m;i++){
    int k;cin>>k;
    for(int j=0;j<k;j++)cin>>a[j];
    cout<<query(a,k)<<endl;
  }
  return 0;
}

C - The XOR-longest Path

先做D题。
根据异或前缀和性质： $[NEFU ACM大一暑假集训解题报告]字典树_#include_02$
那么，在trie树上的路径异或和等于两个叶子结点到根节点的异或和。
我们先用vector存图，再用dfs求解叶结点到根结点的异或和。这样问题就变成D题，求解最大异或对了。

#include<bits/stdc++.h>
using namespace std;
const  int N=1000010,M=N*31;
typedef long long LL;
typedef pair<LL,LL> PIL;
vector<PIL>root[N];
LL idx;
LL a[N],son[M][2];
void insert(LL x){
    LL p=0;
    for(LL i=31;i>=0;i--){
        LL &s=son[p][x>>i&1];
        if(!s)s=++idx;
        p=s;
    }
}
LL query(LL x){
    LL p=0,res=0;
    for(LL i=31;i>=0;i--){
        LL u=x>>i&1;
        if(son[p][!u]){
            res=res*2+1;
            p=son[p][!u];
        }
        else{
            res=res*2;
            p=son[p][u];
        }
    }
    return res;
}
void dfs(LL u,LL fa,LL sum){
    a[u]=sum;
    for(auto j:root[u]){
        if(j.first==fa)continue;
        dfs(j.first,u,j.second^sum);
    }
}
int main(){
    LL n;cin>>n;
    for(LL i=1;i<n;i++){
        LL u,v;LL w;cin>>u>>v>>w;
        root[u].push_back({v,w});
        root[v].push_back({u,w});
    }
    dfs(1,-1,0);
    for(LL i=1;i<=n;i++)insert(a[i]);
    LL ans=0;
    for(LL i=1;i<=n;i++)ans=max(ans,query(a[i]));
    cout<<ans;
    return 0;
}

D - The XOR Largest Pair

异或性质：相同为0,相异为1。
query查询过程优先走相反的即可。
Trie树每往下走一层，就相当于答案向左移动一次，如果存在相反的那么还要进一。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=31*N;
int a[N],son[M][2],idx;
void insert(int x){
    int p=0;
    for(int i=30;~i;i--){
        int &s=son[p][x>>i&1];
        if(!s)s=++idx;//创建新节点
        p=s;
    }
}
int query(int x){
    int res=0,p=0;
    for(int i=30;~i;i--){
        int s=x>>i&1;
        if(son[p][!s]){//看相反的是否存在
            res=res*2+1;//答案左移进一
            p=son[p][!s];
        }
        else{
            p=son[p][s];
            res=res*2;
        }
    }
    return res;
}
int main(void)
{
    cin.tie(0);
    int n;
    cin>>n;
    idx=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }
    int res=0;
    for(int i=0;i<n;i++)
    {   
        res=max(res,query(a[i]));  
    }
    cout<<res<<endl;
}

E - Phone List

注意多组重置trie树啊啊啊
貌似只要用pas数组记录结点经过次数，然后查询的时候看是不是每个结点出现次数>=2次了，如果存在只出现一次的就不行。

#include<bits/stdc++.h>
using namespace std;
const int N=1E4+10,M=1e5+10;
int son[M][12],pas[M],idx;
char str[M][12];
bool flag;
void insert(char* str){
  int p=0;
  for(int i=0;str[i];i++){
    int ch=str[i]-'0';
    if(!son[p][ch])son[p][ch]=++idx;
    p=son[p][ch];
    pas[p]++;
  }
}
bool query(char* str){
  int p=0;
  for(int i=0;str[i];i++){
    int u=str[i]-'0';
    if(pas[son[p][u]]==1)return false;
    p=son[p][u];
  }
  return true;
}
int main(){
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    flag=true;
    idx=0;
    memset(pas,0,sizeof pas);
    memset(son,0,sizeof son);
    for(int i=0;i<n;i++){
      cin>>str[i];
      insert(str[i]);
    }
    for(int i=0;i<n;i++){
      if(query(str[i])){
        flag=false;
        break;
      }
    }
    if(flag)puts("YES");
    else puts("NO");
  }
}

F - Xor sum

类似数位DP的思想，然后跪在代码实现了。
要找出最短的连续子序列，其异或和不小于 k。
首先预处理异或前缀和,将问题转化为 $[NEFU ACM大一暑假集训解题报告]字典树_i++_03$
为了求最短，我们每次将i固定，找到最大的满足条件的j。
原本写了 $[NEFU ACM大一暑假集训解题报告]字典树_i++_04$ 的结果写崩了，后来借鉴这篇题解还是按照原来的式子处理。
我们从高位开始构建01trie树，每次关注最高位置。

如果k的当前位为1,a[i]当前位为1：往0走
如果k的当前位为1,a[i]当前位为0：往1走
上面这两个情况属于，我们最多只能和k相等，是需要继续向下搜索的。

如果k的当前位为0,a[i]当前位为1：往0走
如果k的当前位为0,a[i]当前位为0：往1走
这两种情况属于，我们可以选择=k和>k两种情况，对于>k的我们可以直接获取答案（插入的时候使用预处理出这个结点往下最大下标，存ma里），对于=k的情况我们需要继续向下搜索。

如果你对数位DP有些了解就会有些感觉，搜索树大概是这样的，>k获取答案，=k继续向下搜索

[NEFU ACM大一暑假集训解题报告]字典树_结点_05

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<vector>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
#define MULINPUT
/*DATA & KEY

*/
int T;
const int N=100010,M=N*31;
int a[N],son[M][2],ma[M];
int idx=0;
void insert(int x,int id){
  int p=0;
  for(int i=31;~i;i--){
    int &s=son[p][x>>i&1];
    if(!s)s=++idx;
    p=s;
    ma[p]=max(ma[p],id);
  }
}
int query(int x,int mid){
  int p=0,ans=-1;
  for(int i=31;~i;i--){
    int u1=x>>i&1;//a[i]的当前位
    int u2=mid>>i&1;//k的当前位
    if(u2){//如果k当前位置为1
      if(u1==1)p=son[p][0];
      else p=son[p][1];
    }
    else{//如果k当前位置为0
      if(u1==1){
        if(ma[son[p][0]])ans=max(ans,ma[son[p][0]]);//>k部分答案
        p=son[p][1];//=k部分继续向下搜索
      }
      else{
        if(ma[son[p][1]])ans=max(ans,ma[son[p][1]]);
                p=son[p][0];
      }
    }
    if(p==0)break;
  }
  if(p!=0)ans=max(ans,ma[p]);
  return ans;
}
void init(){
  for(int i=0;i<=idx+5;i++){
    son[i][0]=son[i][1]=ma[i]=0;
  }
  idx=0;
}
int main(){
  int T;scanf("%d",&T);
  while(T--){
    int n,k;scanf("%d%d",&n,&k);
    init();
    for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
      a[i]^=a[i-1];
    }
    insert(0,1);
    int ans=2e9,p=-1;
    for(int i=1;i<=n;i++){
      int l=query(a[i],k);
      if(l!=-1&&i-l+1<ans)ans=i-l+1,p=l;
      insert(a[i],i+1);
    }
    if(ans==2e9)printf("-1\n");
    else printf("%d %d\n",p,p+ans-1);
  }
}

标签：int,res,LL,ACM,son,NEFU,str,大一,include
From： https://blog.51cto.com/u_15891800/5887540

[NEFU ACM大一暑假集训解题报告]字典树