#P18774. [2027年国家集训队互测] Two Steps Away
[2027年国家集训队互测] Two Steps Away
Two Steps Away
题目描述
有一台专门处理01串的字符串变换机,其内部预设一个包含若干条规则的有限集合 。每条规则形如 ,其中 是非空等长01串,表示一步操作可以选择当前串的一个子串 ,并把它替换为 。
每次输入一对非空等长串 ,机器都会输出把 变为 所需的最少操作步数,或报告无解。你回忆起曾输入过 对非空等长串 。记忆中每次都有解,而且最少步数 。
判断是否存在一个有限规则集 ,使机器对这 组输入的实际输出与你的记忆完全一致。规则可在串中任意匹配位置使用;每一步只替换一次所选子串,长度始终不变。同一组测试的所有记录共享 ,不同测试组分别判断。
输入格式
第一行正整数 。每组测试第一行为正整数 ;接下来 行,第 行有两个非空等长01串 和整数 ,,分别为初始串、目标串和记忆中的最少步数。
输出格式
每组测试输出一行:存在符合条件的 则为 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
第一组可取 :恒等串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步。
数据范围与子任务
,,串只含0和1。记单组 ,单个输入文件所有测试组的总和满足 。这里只统计初始串,不能把目标串再加一次。本题开启合理的子任务依赖。
| 子任务 | 分值 | 上限 | 特殊性质 |
|---|---|---|---|
| 1 | 16 | 4000 | A |
| 2 | 20 | 3000000 | |
| 3 | 20000 | 无 | |
| 4 | 28 | 100000 | |
| 5 | 16 | 3000000 |
性质A:所有 均有 。