专栏文章

Solution P14256 | Textbook-style Construction of Automata

BBreakPlus
P14256题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miniyj1r
此快照首次捕获于
2025/12/02 03:10
3 个月前
此快照最后确认于
2025/12/02 03:10
3 个月前
查看原文
这种垃圾的不能再垃圾的，模拟乱七八糟的操作的题，本质上就是要构造一个自动机，能实现在序列末尾添加一个元素，并更新答案的操作。
如果人脑构造不出来就倒闭了。
下面定义 0,1,20,1,2 表示布，剪刀，石头。
写个程序建自动机。 一个状态可以用一个序列表示。定义 f(S)f(S) 表示序列 SS 的答案。定义状态 SS 和 TT 等价，当且仅当对于任意 i∈{0,1,2}i \in \{0,1,2\}，满足 f(S+{i})−f(S)=f(T+{i})−f(T)f(S+\{i\}) - f(S) = f(T+\{i\}) - f(T)，并且 S+{i}S + \{i\} 与 T+{i}T + \{i\} 等价。
考虑到这是个无限递归的定义，但感性理解一下，序列长度比较小的时候，多搜几层后继状态去判定即可。下面是能在比较短的时间内写出的建自动机的代码。
CPP
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,20,1,2 分别对应的后继状态）
CPP
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
很难不发现规律，到这里大家都会了。
如果序列长度是 nn，一共有大约 6n6n 个状态。并且上面的内容具有长度为 1818 的循环节（边权也有，这里没打印出来）。
T=6T=6 的时候，Automaton::build(6) 能在短时间内跑完，所以直接把这一坨扔进代码，利用循环节建立整个自动机。那么这题就做完了。
由于一些神秘原因下面的代码有点神秘，写的很冗余，仅供参考。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = 1e9+7;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline void addmod(int &x){ if(x >= mod) x -= mod; }
inline void addmod(ll &x){ if(x >= mod) x -= mod; }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
inline ll INV(ll x){ return qpow(x, mod-2); };

int n, seq[15], f[15][15][3], jc[15][15][3], ans;

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 Solver{
	const int N = 20000;
	int n, f1[N+5], f2[N+5], g1[N+5], g2[N+5], nxt[N+5][3], w[N+5][3];
	char s[N];

	void cover(int f,int a,int b,int c){
		nxt[f][0] = a, nxt[f][1] = b, nxt[f][2] = c;
	}
	void eval(int f,int a,int b,int c){
		w[f][0] = a, w[f][1] = b, w[f][2] = c;
	}

	void main(){
		n=read();
		scanf("%s", s+1);

		for(int i=0; i<=2; i++){
			if(s[1]-'0'>>i&1){
				f1[i]=1;
			}
		}

		for(int i=2;i<=n;i++){
			memset(g1, 0, sizeof(g1));
			memset(g2, 0, sizeof(g2));

			for(int j=0; j<=N; j++){
				for(int k:{0,1,2}){

					if(!(s[i]-'0'>>k&1)) continue;
					addmod(g1[nxt[j][k]] += f1[j]);
					addmod(g2[nxt[j][k]] += f2[j]);
					if(w[j][k]) addmod(g2[nxt[j][k]] += f1[j]);
				}
			}
			memcpy(f1, g1, sizeof(g1));
			memcpy(f2, g2, sizeof(g2));
		}
		int ans = 0;
		for(int j=0;j<=N;j++) addmod(ans += f2[j]);
		printf("%d\n", ans);
	}
}
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};

	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;
	}

	int getid(int x){
		if(!x) return 0;
		if(dfa[x].sta.size() == 1) return dfa[x].sta[0];
		else {
			int w = (dfa[x].sta.size()-1) * 6;
			pair<int,int> p = {dfa[x].sta[0], dfa[x].sta[1]};
			if(p == (pair<int,int>){0,1}) return w + 0;
			if(p == (pair<int,int>){0,2}) return w + 1;
			if(p == (pair<int,int>){1,0}) return w + 2;
			if(p == (pair<int,int>){1,2}) return w + 3;
			if(p == (pair<int,int>){2,0}) return w + 4;
			return w + 5;
		}
	}
	int getval(int x,int o){
		vector<int>tmp = dfa[x].sta;
		tmp.pb(o);
		return bf::solve(tmp) - dfa[x].val;
	}
	void build(int 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;
						}
				}
			}
		}


		vector<tuple<int,int,int>>COVER(20001), EVAL(20001);

		for(int i=1;i<id;i++){
			COVER[getid(i)] = {getid(dfa[i].son[0]), getid(dfa[i].son[1]), getid(dfa[i].son[2])};
			EVAL[getid(i)] = {getval(i,0), getval(i,1), getval(i,2)};
		}
		for(int i=30; i<=20000; i++){
			auto [b,c,d] = COVER[i-18];
			auto [f,g,h] = EVAL[i-18];

			COVER[i] = {b+18,c+18,d+18};
			EVAL[i] = {f,g,h};
		}

		for(int i=0;i<=20000;i++) {
			if(i >= 3 && i <= 5) continue;
			auto [b,c,d] = COVER[i]; Solver::cover(i,b,c,d);
			auto [f,g,h] = EVAL[i]; Solver::eval(i,f,g,h);
		}
	}
}
int main(){
	Automaton::build(6);
	Solver::main();
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...