#1998. 两步之遥
两步之遥
两步之遥
题目描述
标题: 两步之遥 - Problem - QOJ.ac
#21437. 两步之遥
题目描述
有一台专门处理 01 串的字符串变换机,其内部预设了一个包含若干条规则的有限集合 R。每条规则形如 (u,v),其中 u,v 是非空等长的 01 串,表示在一步操作中,可以选择当前字符串的一个子串 u,并将其替换为 v。每次向机器输入一对非空等长 01 串 (s,t),机器都会输出将 s 变换为 t 所需的最少操作步数,或报告无解。
你回忆起自己曾向这台机器输入过 n 对非空等长 01 串 (s1,t1),(s2,t2),…,(sn,tn)。巧合的是,在你的记忆中,每次询问不仅都有解,而且满足最少操作步数 di⩽2。
为了验证你的记忆是否出现偏差,请你判断:是否存在一个规则集 R,使得机器对这 n 组输入的实际输出与你的记忆完全一致?
输入格式
第一行包含一个正整数 T,表示测试数据组数。
对于每组测试数据,第一行包含一个正整数 n,表示询问记录的数量。接下来 n 行,第 i 行包含两个非空等长 01 串 si,ti 和一个整数 di(0⩽di⩽2),分别表示第 i 次输入的初始串、目标串以及机器给出的最少操作步数。
输出格式
对于每组测试数据,输出一行一个字符串。若存在满足条件的规则集 R,则输出 YES;否则输出 NO。
你可以输出 YES 和 NO 的任意大小写形式,例如 yes、Yes 或 YES 均会被视为相同答案。
样例
样例输入 1
3
3
010 010 0
001 010 1
001 100 2
2
10 01 1
100 010 2
1
0 1 2
样例输出 1
YES
NO
NO
样例解释 1
-
第 1 组测试数据:可以构造只包含一条规则的集合 R={(01,10)}:
- 对于第 1 次询问,s1=t1=010,无需任何操作即可完成变换,最少操作步数为 0。
- 对于第 2 次询问,将 001 的后缀 01 替换为 10,即可在 1 步内得到 010。
- 对于第 3 次询问,由于 001 与 100 在第 1 位和第 3 位均不同,仅靠长度为 2 的规则无法在 1 步内完成变换;但可以先将初始串 001 的后缀 01 替换为 10 得到中间串 010,再将中间串 010 的前缀 01 替换为 10 得到目标串 100,因此最少操作步数为 2。
-
第 2 组测试数据:为了在 1 步内将 10 变换为 01,规则集 R 中必须包含规则 (10,01)。然而一旦包含该规则,第 2 次询问只需将 100 的前缀 10 替换为 01,即可在 1 步内得到 010,与记忆中的 d2=2 矛盾。
-
第 3 组测试数据:变换过程中的所有字符串均须为等长的 01 串。长度为 1 的 01 串仅有 0 和 1 两种,若能从 0 变换为 1,则必然存在规则 (0,1) 并且只需 1 步即可完成,不可能最少需要 2 步。
数据范围
对于所有测试数据,保证 T⩾1,n⩾1,0⩽di⩽2,1⩽|si|=|ti|,且 si,ti 均为仅包含字符 0 和 1 的字符串。
记 L=∑ni=1|si| 为单组测试数据中所有初始串的长度之和,∑L 为单个测试点内所有测试数据的 L 之和,则保证 ∑L⩽3×106。
本题开启合理的子任务依赖。
子任务编号 分值 ∑L⩽ 特殊性质 1 16 4×103 A 2 20 3×106 A 3 20 2×104 无 4 28 105 无 5 16 3×106 无
- 特殊性质 A:保证对于所有 1⩽i⩽n,均有 |si|⩾50。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
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