CSU 1929: 01串（形式系统）
【摘要】
题目：
Description
对于一个01串，我们可以有如下操作：
将字符串中的“0”替换为“11”，或者将字符串中的“1”替换为“00”；将字符串中的“000”或者“111”删除。
例如，将字符串“010”执行第一个操作，并选择了第一个字符“0”，那么字符串将变为“1110”。如果将字符串“1110000”执行...
题目：
Description
对于一个01串，我们可以有如下操作：
- 将字符串中的“0”替换为“11”，或者将字符串中的“1”替换为“00”；
- 将字符串中的“000”或者“111”删除。
例如，将字符串“010”执行第一个操作，并选择了第一个字符“0”，那么字符串将变为“1110”。如果将字符串“1110000”执行第二个操作，并选择了最后三个字符“000”，那么字符串变为“1110”。
这些操作可以按任意顺序执行任意次数。
给出两个01串S和T，并且有q查询，每个查询四个整数ai,bi,ci,di。 对于每个查询，判断SaiSai + 1…Sbi（S的子串）是否可以被转换成TciTci + 1…Tdi（T的子串）。
Input
第一行一个整数K，表示样例个数 。(1<=K<=5)
对于每个样例：
第一行包括两个字符串，分别表示S，T 。（1≤|S|,|T|≤105）
第二行一个整数q，表示询问个数。（1<=q<=105）
接下来q行，每行四个整数ai,bi,ci,di。(1≤ai≤bi≤|S|，1≤ci≤di≤|T|)
这就是一个形式系统，和著名的形式系统 WU谜题 差不多
代码：
-
#include<iostream>
-
#include<stdio.h>
-
#include<string.h>
-
using namespace std;
-
-
char s[100005], t[100005];
-
int ns[100005], nt[100005];
-
-
int main()
-
{
-
int k;
-
cin >> k;
-
while(k--)
-
{
-
scanf("%s%s", s+1, t+1);
-
int ls = strlen(s+1), lt = strlen(t+1);
-
ns[0] = nt[0] = 0;
-
for (int i = 1; i <= ls; i++)ns[i] = ns[i - 1] + (s[i] == 'A') * 2 - 1;
-
for (int i = 1; i <= lt; i++)nt[i] = nt[i - 1] + (t[i] == 'A') * 2 - 1;
-
int q, a, b, c, d;
-
cin >> q;
-
while (q--)
-
{
-
scanf("%d%d%d%d", &a, &b, &c, &d);
-
if ((ns[b] - ns[a - 1] - nt[d] + nt[c - 1]) % 3)printf("NO\n");
-
else printf("YES\n");
-
}
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/79874511
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）