#1998. 两步之遥

    ID: 1998 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4604来源:qoj.ac数据:公开样例字符串

两步之遥

两步之遥

题目描述

标题: 两步之遥 - Problem - QOJ.ac

#21437. 两步之遥

Statistics

题目描述

有一台专门处理 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