Solution P14256 | Textbook-style Construction of Automata

BreakPlus · 2025-10-23 15:26:11 · 题解

这种垃圾的不能再垃圾的，模拟乱七八糟的操作的题，本质上就是要构造一个自动机，能实现在序列末尾添加一个元素，并更新答案的操作。

如果人脑构造不出来就倒闭了。

下面定义 0,1,2 表示布，剪刀，石头。

写个程序建自动机。 一个状态可以用一个序列表示。定义 f(S) 表示序列 S 的答案。定义状态 S 和 T 等价，当且仅当对于任意 i \in \{0,1,2\}，满足 f(S+\{i\}) - f(S) = f(T+\{i\}) - f(T)，并且 S + \{i\} 与 T + \{i\} 等价。

考虑到这是个无限递归的定义，但感性理解一下，序列长度比较小的时候，多搜几层后继状态去判定即可。下面是能在比较短的时间内写出的建自动机的代码。

namespace bf{
    int calc(int x,int y){
        return (x == (y+1)%3) ? x : y;
    }

    int f[15][15][3];
    int solve(vector<int>seq){
        int n = seq.size();
        memset(f,0xc0,sizeof(f));
        for(int i=0;i<n;i++) f[i][i][seq[i]]=0;

        for(int x=1;x<n;x++){
            for(int i=0,j=x;j<n;i++,j++){
                for(int k=i;k<j;k++){
                    for(auto x:{0,1,2}) for(auto y:{0,1,2}){
                        if(x == y){
                            int val = f[i][k][y] + f[k+1][j][y] + 1;
                            if(val > f[i][j][x]){
                                f[i][j][x] = val;
                            }
                        }else{
                            int w = calc(x,y);
                            int val = f[i][k][x] + f[k+1][j][y];
                            if(val > f[i][j][w]){
                                f[i][j][w] = val;
                            }
                        }
                    }
                }
            }
        }
        return max({f[0][n-1][0], f[0][n-1][1], f[0][n-1][2]});
    }
} // 显然我们需要一个能用的暴力算法
namespace Automaton{
    struct Node{
        vector<int>sta;
        int son[3], val;

        void upd(){ val = bf::solve(sta); }
    }dfa[100005]; int id;
    void printNode(Node A, string s="\n"){
        for(auto x: A.sta) cout<<x; cout<<s;
    }
    const int F = 6, pw[10] = {1,3,9,27,81,243,729,2187};
// 往后搜 F=6 层去判定

    inline bool operator == (Node A, Node B){
        for(int i=0; i<pw[F]; i++){
            vector<int>v1 = A.sta, v2 = B.sta;

            for(int j=0,x=i; j<F; j++,x/=3)
                v1.pb(x%3), v2.pb(x%3);

            if(bf::solve(v1)-A.val != bf::solve(v2)-B.val) return 0; // 要求差值相等
        }
        return 1;
    } // 判定两个状态等价
    void build(int T){ // T 表示搜索的串长
        while(T--){
            int n = id;
            for(int i=0; i<=n; i++){ // 枚举一个上一层的状态，进行扩展
                for(auto o:{0,1,2}){
                    if(dfa[i].son[o]) continue;
                    dfa[i].son[o] = ++id;
                    dfa[id].sta = dfa[i].sta; dfa[id].sta.pb(o);

                    dfa[id].upd(); // 新建状态

                    for(int j=0;j<id;j++)
                        if(dfa[j] == dfa[id]){
                            dfa[i].son[o] = j;
                            id --;
                            break;
                        } // 如果之前有和它等价的状态，就不用新建
                }
            }
        }
}

把这个自动机输出来（行末的三个数字表示在该状态末尾新加一个元素 0,1,2 分别对应的后继状态）

0 sta=: 1 2 3
1 sta=0: 1 4 5
2 sta=1: 6 2 7
3 sta=2: 8 9 3
4 sta=01: 10 4 5
5 sta=02: 1 11 5
6 sta=10: 6 2 12
7 sta=12: 6 13 7
8 sta=20: 8 9 14
9 sta=21: 15 9 3
10 sta=010: 10 4 16
11 sta=021: 17 11 5
12 sta=102: 6 18 12
13 sta=121: 19 13 7
14 sta=202: 8 20 14
15 sta=210: 15 9 21
16 sta=0102: 10 22 16
17 sta=0210: 17 11 23
18 sta=1021: 24 18 12
19 sta=1210: 19 13 25
20 sta=2021: 26 20 14
21 sta=2102: 15 27 21
22 sta=01021: 28 22 16
23 sta=02102: 17 29 23
24 sta=10210: 24 18 30
25 sta=12102: 19 31 25
26 sta=20210: 26 20 32
27 sta=21021: 33 27 21
28 sta=010210: 28 22 30
29 sta=021021: 34 29 23
30 sta=102102: 24 35 30
31 sta=121021: 33 31 25
32 sta=202102: 26 29 32
33 sta=210210: 33 27 36
34 sta=0210210: 34 29 37
35 sta=1021021: 38 35 30
36 sta=2102102: 33 39 36

很难不发现规律，到这里大家都会了。

如果序列长度是 n，一共有大约 6n 个状态。并且上面的内容具有长度为 18 的循环节（边权也有，这里没打印出来）。