ICPC Online 2024 K AC Automation Chicken 题解

很涩的一个题。

题意

题目链接

假如我们有一个 AC 自动机,我们可以取出其中的点,字符边和 Fail 边,这样其就变成了一个有 $n$ 个点和 $2n-2$ 条边的有向图。现在给出你这样一个有向图,你需要找到其原始的 AC 自动机结构(包括 1. 找到根 2. 找到哪些边是 Trie 树边 3. 给所有的 Trie 树边分配一个字符,字符集大小不限)。

$n=10^5$.

题解

Part I 找根

大力观察 AC 自动机,你发现如果只考虑其中 $u \to v, v \to u$ 这样的边,这些边一定会连成一个类菊花的结构(均是从根节点开始,按照每个字符边一路往下走到某个位置停止)或是一条链。

你只需要画出一个 AC 自动机,然后只保留那些 $u \to v, v \to u$ 的边,就可以明晰大致结构了。

如果这些双向边构成的子无向图中,有一个点度数 $\ge3$,那么他就一定为根。考虑链的时候怎么做。

如果形成了一条链,我们再对这一情况进行大力观察(建议画出一个符合结构的 AC 自动机),我们发现存在这样的一类点,满足以下三个条件:

  1. 这个点初始时不在链上
  2. 链上有一个点连向该点
  3. 这个点有一条边连向链上的点(易知这是 fail 边)

那么,这条 fail 边一定会连向根节点或根节点的儿子(详细说明过于繁琐,你可以自行画出 AC 自动机,找到这样的点,并尝试回答为什么)。

因此,记这个点为 $x$,我们只需要 check $x$ 以及与 $x$ 相邻的两点这三个点作为根的可能性即可。问题转化为,我们假定了一个根,如何去 check 是否存在一种合法的情况。

注意,你还需要警惕保留 $u \to v, v \to u$ 的边后出现多个连通块的情况,这显然是不合法的。

Part II 构建 AC 自动机

check 的第一步一定是根据这个根构建出 AC 自动机,这一步较为简单,从根节点开始,所有连向没有连过的点都是 Trie 树边,所有连向深度比他低的边都是 fail 边,若出现一条边连向深度相同的点,或出现一个点没有 fail 边(根节点除外) / 有超过一个 fail 边,报告无解。如果有一个点没有边连向他(根节点除外),也报告无解。

现在,我们已经找到那些边是 Trie 树边了,对于字符的分配,我们不妨将其分配在边连向的点上而并非边上。我们利用一个并查集结构。我们从根开始 bfs 遍历每个点,对于一个点 $u$,如果其 fail 连向的是 $v$,我们就把 $u,v$ 并起来,然后 $u$ 和 $v$ 再各自向其父亲跳,直至:

  1. $u$ 和 $v$ 已经被 merge 过了
  2. $v$ 到达了根

这两个条件任意满足其一即可。

然后,我们为每个并查集分配一个不同的字符,再验证对于每个点,其儿子的字符都是互不相同的。

Part III 验证 AC 自动机

现在我们已经构造好了 AC 自动机的结构,但其不一定为合法的,我们需要通过当前分配的字符集,重新跑一边 AC 自动机,验证其 fail 结构与原来构建的是否相同。问题转换为了构造字符集大小为 $O(n)$ 的 AC 自动机。

观察原来的 AC 自动机构造方法,发现时间复杂度瓶颈在于克隆 to 数组,在字符集大小为 $O(n)$ 是,将 $fail[u]$ 的 to 数组克隆到 $u$ 上需要 $O(n)$ 的时间复杂度,导致总时间复杂度来到了 $O(n^2)$。

因此,我们对于每一个点都开一个可持久化线段树,这棵线段树只需要满足两种操作,单点修改与单点查询,我们将原来访问 tr[u].to[x] 的操作变成了 query(root[u],x),虽然修改和查询的时间复杂度由 $O(1)$ 变成了 $O(\log n)$,但是现在我们可以直接通过 root[u]=root[tr[u].fail] 来完成原来需要 $O(n)$ 完成的克隆操作。

至此,我们根据在 Part II 中得到的字符分配构建好 AC 自动机,再将其的 fail 结构与 Part II 中得到的 fail 结构一一对比即可。

总体时间复杂度为 $O(n\log n)$。

代码

代码过于狗屎,不建议查看。

#include<bits/stdc++.h>
#define pi pair<int,int>
#define mk make_pair
using namespace std;
const int N=4e5+5;
int T,n,root;
struct node{
    int to,nxt;
}e[N];
int head[N],cnt;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
map<pi,bool> ma;
int du[N],child[N],fa[N],ffa[N];
int find(int u){
    return ffa[u]==u?(u):(ffa[u]=find(ffa[u]));
} 
int dep[N];
void merge(int u,int v){
    while(u!=root && v!=root){
        if(find(u)==find(v)) break;
        ffa[find(u)]=find(v);
        u=fa[u];v=fa[v];
    }
}
int col[N],fail[N];

int c[N*16][2],val[N*16],treetot,ro[N*16];
void Ins(int &p, int l, int r, int x, int y) {
    int q = ++treetot;
    c[q][0] = c[p][0], c[q][1] = c[p][1], val[q] = val[p], p = q;
    if (l == r) return val[p] = y, void();
    int mid = (l + r) >> 1;
    if (x <= mid) Ins(c[p][0], l, mid, x, y);
    else Ins(c[p][1], mid + 1, r, x, y);
}
int Get(int p, int l, int r, int x) {
    if (l == r || !p) return val[p];
    int mid = (l + r) >> 1;
    if (x <= mid) return Get(c[p][0], l, mid, x);
    return Get(c[p][1], mid + 1, r, x);
}


struct ACAM{
    struct Trie_Tree{
        int fail;
        map<int,int> to;
    }tr[N];
    void init(){
        for(int i=1;i<=treetot;i++) c[i][0]=c[i][1]=val[i]=0;
        treetot=0;
        for(int i=1;i<=n;i++){
            tr[i].to.clear();
            tr[i].fail=0;
            ro[i]=0;
        }
        for(int u=1;u<=n;u++){
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].to;if(v==fail[u]) continue;
                tr[u].to[col[v]]=v;
            }
        }
    }
    void Get_Fail(){
        queue<int> q;q.push(root);ro[root]=++treetot;
        while(!q.empty()){
            int u=q.front();q.pop();
            if(u!=root) ro[u]=ro[tr[u].fail];
            for(auto x:tr[u].to){
                tr[x.second].fail=Get(ro[tr[u].fail],1,n,x.first);
                Ins(ro[u],1,n,x.first,x.second);
                if(tr[x.second].fail==0) tr[x.second].fail=root;
                q.push(x.second);
            }
        }
    }
}AC;
int in[N];
bool check(){
    queue<int> q;q.push(root);
    for(int i=1;i<=n;i++) dep[i]=fa[i]=col[i]=fail[i]=in[i]=0;
    for(int i=1;i<=n;i++) ffa[i]=i;
    dep[root]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        int failcnt=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dep[v]!=0 && dep[v]<dep[u]){
                merge(u,v);fail[u]=v;
                failcnt++;
            }
            else if(dep[u]==dep[v]){
                return 0;
            }
            else{
                q.push(v);fa[v]=u;in[v]++;
                dep[v]=dep[u]+1;
            }
        }

        if(u==root){
            if(failcnt!=0) return 0;
        }
        else{
            if(failcnt!=1) return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(i==root && in[i]!=0) return 0;
        else if(i!=root && in[i]!=1) return 0;
    }


    int tot=0;
    for(int i=1;i<=n;i++){
        if(i==root) continue;
        if(!col[find(i)]){
            col[find(i)]=++tot;
        }
        col[i]=col[find(i)];
    }

    for(int u=1;u<=n;u++){
        set<int> tmpset;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;if(v==fail[u]) continue;
            if(tmpset.count(col[v])) return 0;
            tmpset.insert(col[v]);
        }
    }


    AC.init();
    AC.Get_Fail();
    for(int i=1;i<=n;i++){
        if(AC.tr[i].fail!=fail[i]) return 0;
    }
    printf("Yes\n");
    for(int u=1;u<=n;u++){
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;if(v==fail[u]) continue;
            printf("%d %d %d\n",u,v,col[v]);
        }
    }
    return 1;
}
int lianshu;
int lianfa[N];
int lianfind(int u){
    return lianfa[u]==u?u:lianfa[u]=lianfind(lianfa[u]);
}


void solve(){
    scanf("%d",&n);lianshu=0;
    if(n==1){
        printf("Yes\n");return;
    }
    cnt=0;
    int Root=0;
    for(int i=1;i<=n;i++){
        head[i]=du[i]=child[i]=0;
    }
    ma.clear();

    for(int i=1;i<=n;i++) lianfa[i]=i;

    for(int i=1,u,v;i<=2*n-2;i++){
        scanf("%d%d",&u,&v);
        add(u,v);ma[make_pair(u,v)]=1;
        if(ma.count(make_pair(v,u))){
            du[v]++;du[u]++;
            if(lianfind(u)!=lianfind(v)){
                lianfa[lianfind(u)]=lianfind(v);
            }
        }
    }

    int tmp=0;
    for(int i=1;i<=n;i++){
        if(du[i]==0) continue;
        if(lianfind(i)!=tmp){
            if(tmp==0) tmp=lianfind(i);
            else{
                printf("No\n");
                return;
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(du[i]>=3){
            if(!Root) Root=i;
            else {
                printf("No\n");return;
            }
        }
    }
    if(!Root){
        bool allhasdu=1;
        for(int u=1;u<=n;u++){
            if(du[u]>0){
                for(int i=head[u];i;i=e[i].nxt){
                    int v=e[i].to;if(du[v]>0) continue;
                    child[v]=1;
                }
            }
        }
        for(int u=1;u<=n;u++){
            if(child[u] && du[u]==0){
                allhasdu=0;
                for(int i=head[u];i;i=e[i].nxt){
                    int v=e[i].to;
                    if(du[v]>0){
                        for(int j=head[v];j;j=e[j].nxt){
                            int _v=e[j].to;
                            if(du[_v]>0){
                                root=_v;
                                if(check()) return;
                            }
                        }
                        root=v;
                        if(check()) return;
                        printf("No\n");return;
                    }
                }
            }
        }
        if(allhasdu){
            root=1;
            if(check()) return;
        }
    }
    else{
        root=Root;
        if(check()) return;
    }
    printf("No\n");
    return;
}
int main(){
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇