#P18774. [2027年国家集训队互测] Two Steps Away

[2027年国家集训队互测] Two Steps Away

Two Steps Away

题目描述

有一台专门处理01串的字符串变换机,其内部预设一个包含若干条规则的有限集合 RR。每条规则形如 (u,v)(u,v),其中 u,vu,v 是非空等长01串,表示一步操作可以选择当前串的一个子串 uu,并把它替换为 vv。

每次输入一对非空等长串 (s,t)(s,t),机器都会输出把 ss 变为 tt 所需的最少操作步数,或报告无解。你回忆起曾输入过 nn 对非空等长串 (s1,t1),…,(sn,tn)(s_1,t_1),\ldots,(s_n,t_n)。记忆中每次都有解,而且最少步数 di≤2d_i\le2。

判断是否存在一个有限规则集 RR,使机器对这 nn 组输入的实际输出与你的记忆完全一致。规则可在串中任意匹配位置使用;每一步只替换一次所选子串,长度始终不变。同一组测试的所有记录共享 RR,不同测试组分别判断。

输入格式

第一行正整数 TT。每组测试第一行为正整数 nn;接下来 nn 行,第 ii 行有两个非空等长01串 si,tis_i,t_i 和整数 did_i,0≤di≤20\le d_i\le2,分别为初始串、目标串和记忆中的最少步数。

输出格式

每组测试输出一行:存在符合条件的 RR 则为 YES,否则为 NO。大小写任意,如yes、Yes、YES均视为相同答案。

样例

输入:

3
3
010 010 0
001 010 1
001 100 2
2
10 01 1
100 010 2
1
0 1 2

输出:

YES
NO
NO

第一组可取 R={(01,10)}R=\{(01,10)\}:恒等串010无需操作;001的后缀01替换为10得到010,只需1步;001与100首尾两位均不同,长度2的规则不能一次完成,但可以001→010→100,正好2步。 第二组要求10到01最少1步,必须包含规则(10,01)。于是100的前缀10也可一步替换为01,得到010,与记忆2步冲突。 第三组中长度1的01串只有0与1,若0可变1,就必有规则(0,1)且只需1步,不可能最少2步。

数据范围与子任务

T≥1,n≥1,0≤di≤2T\ge1,n\ge1,0\le d_i\le2,1≤∣si∣=∣ti∣1\le|s_i|=|t_i|,串只含0和1。记单组 L=∑i=1n∣si∣L=\sum_{i=1}^n|s_i|,单个输入文件所有测试组的总和满足 ∑L≤3×106\sum L\le3\times10^6。这里只统计初始串,不能把目标串再加一次。本题开启合理的子任务依赖。

子任务 分值 ∑L\sum L上限 特殊性质
1 16 4000 A
2 20 3000000
3 20000 无
4 28 100000
5 16 3000000

性质A:所有 1≤i≤n1\le i\le n 均有 ∣si∣≥50|s_i|\ge50。