专栏文章

P12294

llsj2009Isj2OO9
P12294题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio0dvsf
此快照首次捕获于
2025/12/02 11:18
3 个月前
此快照最后确认于
2025/12/02 11:18
3 个月前
查看原文
将三目运算符刻画成，每次选取一个长为 33 的子串变成 0/10/1；令函数 f(s,t)f(s,t) 返回 ss 能否进行如上操作后变成 tt。当 tt 固定时，构建自动机 AtA_t，若字符串 s1,s2s_1,s_2 满足对于任意 0101 串 ss 有 f(s1+s,t)=f(s2+s,t)f(s_1+s,t)=f(s_2+s,t)，则显然可以把 s1/s2s_1/s_2 压入 AtA_t 种同一节点。若变化规律比较简单，自动机状态是有限的，且仅取所有 ∣s∣≤m|s|\le m 的字符串 ss 就可以区分所有状态（mm 是一个常数）。
令 g(s)g(s) 为一个长度为 2n2^n 的序列，其中第 ii 项存储 f(s+ai,t)f(s+a_i,t) 的值，aia_i 是 ii 对应的 0101 串；如何构建自动机？直接 bfs，每遇到一个新字符串 ss，若其 g(s)g(s) 未出现过，则丢入队列并作为 g(s)g(s) 状态的代表元。则构建自动机复杂度为 O(∣At∣(l+m)32m)\mathcal{O}\left(|A_t|(l+m)^32^m\right)，其中 ll 是 AtA_t 所有状态对应的代表元的最长长度。对于所有 ∣t∣≤2|t|\le 2 的 tt 建立自动机 AtA_t，实际上有 l≤9,m≤6,∣A∣≤47l\le9,m\le 6,|A|\le47，复杂度可以接受。
如何构造 sl∼rs_{l\sim r} 合成 tt 的方案？若 ∣t∣=2|t|=2 则枚举合成 t1,t2t_1,t_2 区间的分段点，否则 ∣t∣=1|t|=1 若 t1′t2′t3′→tt_1't_2't_3'\to t，枚举 t1′,t2′t3′t_1',t_2't_3' 区间分段点，类似于启发式分裂，从两边开始向中间找；问题变成快速 check 一个区间 sl∼rs_{l\sim r} 是否可以合成 tt，对每个 AtA_t 建线段树即可，维护每个 AtA_t 上状态走过一个线段树区间对应的转移变成了什么；或者是建猫树，做到查询 O(1)\mathcal{O}(1)，但预处理复杂度和空间复杂度多带上一个 log⁡n\log{n}。
用线段树做的复杂度是 O(∣At∣(l+m)32m+∣At∣∑n+∑nlog⁡2n)\mathcal{O}\left(|A_t|(l+m)^32^m+|A_t|\sum n+\sum n\log^2{n}\right)。
CPP
#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define umap unordered_map
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
int op[8];
struct DFA {
	static const int N=50,L=20,m=6;
	int trans[N][2],f[L][L][6],s[N],t,p;
	bool ok[N];
	map<bint,int> h;
	bint check(int s) {
		int n=lg(s);
		rep(i,0,n-1) {
			rep(j,0,n-1) {
				rep(k,0,5)
					f[i][j][k]=false;
			}
			f[i][i][(s>>i)&1]=true;
		}
		rep(len,2,n) {
			rep(l,0,n-len) {
				int r=l+len-1;
				rep(k,l,r-1) {
					rep(i,0,5) {
						if(!f[l][k][i])
							continue;
						rep(j,0,5) {
							if(!f[k+1][r][j])
								continue;
							if(i<=1&&j<=1)
								f[l][r][(i|(j<<1))+2]=true;
							else if(i<=1)
								f[l][r][op[i|((j-2)<<1)]]=true;
							else if(j<=1)
								f[l][r][op[(i-2)|(j<<2)]]=true;
							else {
								f[l][r][(((i-2)&1)|(op[((i-2)>>1)|((j-2)<<1)]<<1))+2]=true;
								f[l][r][(op[(i-2)|(((j-2)&1)<<2)]|((j-2)&2))+2]=true;
							}
						}
					}
				}
			}
		}
		return f[0][n-1][t];
	}
	bint calc(int s) {
		int x=lg(s);
		bint res=0;
		int cnt=0;
		rep(j,0,m) {
			if(j) {
				s^=1<<(x+j-1);
				s^=1<<(x+j);
			}
			rep(i,0,(1<<j)-1)
				res|=check(s|(i<<x))<<(cnt++);
		}
		return res;
	}
	void build(int _t) {
		t=_t;
		queue<int> q;
		bint g=calc(1);
		h[g]=++p;
		ok[p]=g&1;
		s[p]=1;
		q.push(p);
		while(!q.empty()) {
			int u=q.front(); q.pop();
			int x=lg(s[u]);
			int u0=s[u]^(1<<x)^(1<<(x+1)),u1=s[u]^(1<<(x+1));
			bint gu0=calc(u0),gu1=calc(u1);
			if(!h.count(gu0)) {
				h[gu0]=++p;
				s[p]=u0;
				ok[p]=gu0&1;
				q.push(p);
			}
			if(!h.count(gu1)) {
				h[gu1]=++p;
				s[p]=u1;
				ok[p]=gu1&1;
				q.push(p);
			}
			trans[u][0]=h[gu0];
			trans[u][1]=h[gu1];
		}
	}
}; DFA f[6];
const int N=1e5+5;
char s[N];
struct SGT {
	static const int M=50;
	int m;
	struct node {
		int l,r,trans[M];
	}; node tree[N<<2];
	#define ls(k) (k<<1)
	#define rs(k) (k<<1|1)
	void push_up(int k) {
		rep(i,1,m)
			tree[k].trans[i]=tree[rs(k)].trans[tree[ls(k)].trans[i]];
	}
	void build(int k,int l,int r,DFA &f) {
		tree[k].l=l; tree[k].r=r;
		if(l==r) {
			rep(i,1,m)
				tree[k].trans[i]=f.trans[i][s[l]-48];
			return;
		}
		int mid=(l+r)>>1;
		build(ls(k),l,mid,f);
		build(rs(k),mid+1,r,f);
		push_up(k);
	}
	int query(int k,int ql,int qr,int u) {
		if(ql<=tree[k].l&&tree[k].r<=qr)
			return tree[k].trans[u];
		if(ql<=tree[ls(k)].r)
			u=query(ls(k),ql,qr,u);
		if(qr>=tree[rs(k)].l)
			u=query(rs(k),ql,qr,u);
		return u;
	}
	#undef ls
	#undef rs
}; SGT T[6];
bool check(int l,int r,int op) {
	return f[op].ok[T[op].query(1,l,r,1)];
}
void solve(int l,int r,int c) {
	// debug("([%d,%d],%d)\n",l,r,c);
	if(l==r) {
		printf("%c",s[l]);
		return;
	}
	if(c<=1) {
		putchar('(');
		int pl=l,pr=r;
		while(true) {
			bool flag=false;
			rep(i,0,1) {
				rep(j,0,3) {
					if(op[i|(j<<1)]!=c)
						continue;
					if(pl!=r&&check(l,pl,i)&&check(pl+1,r,j+2)) {
						solve(l,pl,i);
						solve(pl+1,r,j+2);
						flag=true;
						break;
					}
					if(l!=pr&&check(l,pr-1,i)&&check(pr,r,j+2)) {
						solve(l,pr-1,i);
						solve(pr,r,j+2);
						flag=true;
						break;
					}
				}
				if(flag)
					break;
			}
			if(flag)
				break;
			++pl; --pr;
		}
		putchar(')');
	} else {
		int pl=l,pr=r;
		while(true) {
			if(pl!=r&&check(l,pl,(c-2)&1)&&check(pl+1,r,(c-2)>>1)) {
				solve(l,pl,(c-2)&1);
				solve(pl+1,r,(c-2)>>1);
				break;
			}
			if(l!=pr&&check(l,pr-1,(c-2)&1)&&check(pr,r,(c-2)>>1)) {
				solve(l,pr-1,(c-2)&1);
				solve(pr,r,(c-2)>>1);
				break;
			}
			++pl; --pr;
		}
	}
}
void solve() {
	rep(i,0,7) {
		char ch;
		cin>>ch;
		op[i]=ch-48;
	}
	rep(i,0,5)
		f[i].build(i);
	int q;
	scanf("%d",&q);
	while(q--) {
		scanf("%s",s+1);
		int n=strlen(s+1);
		rep(i,0,5)
			T[i].m=f[i].p,T[i].build(1,1,n,f[i]);
		if(!check(1,n,1)) {
			puts("-1");
			continue;
		}
		solve(1,n,1);
		puts("");
	}
}
bool M2;
// g++ P12294.cpp -std=c++14 -Wall -O2 -o P12294
signed main() {
	// file_IO();
	int testcase=1;
	// scanf("%d",&testcase);
	while(testcase--)
		solve();
	debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
	debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
	return 0;
}

评论

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

正在加载评论...