合作公司做网站,最简 wordpress主题,毕设做系统与网站,建设网站企业邮箱网站建设服务题目链接
Picking String
题意
给出字符串S和T#xff0c;1e5个询问#xff0c;每次询问S的一段区间是否能转变成T的一段区间。 转变方式#xff1a; ABCABCBACBACCABCABAAAAAA可以消除 题解
我们从以上四个条件出发推导出更加精华的条件 B1e5个询问每次询问S的一段区间是否能转变成T的一段区间。 转变方式
ABCABCA>BCBACBACB>ACCABCABC>ABAAAAAAAAA可以消除 题解
我们从以上四个条件出发推导出更加精华的条件
BACAABAAACCBACAABAAACCB>AC>AAB>AAAC>CCABAACAAABBCABAACAAABBC>AB>AAC>AAAB>BABCBBABCBBA>BC>BB
也就是说所有的CCC都等价于B" role="presentation" style="position: relative;">BBB
由于BACBACB>AC也就是BABBABB>AB而3个AAA可以消除，这个操作意味着B前面可以有任意多个A" role="presentation" style="position: relative;">AAA所以说BBB前面的紧贴着的A" role="presentation" style="position: relative;">AAA的数量我们可以忽略。
由于BABBBBABBBBBBBBABBABBBBBBBABBBBABBBBBBBBABBABBBBBBB>AB>BBB>ABBB>BBBBB，A>BB>ABB>BBBB也就是说我们只要有一个AAA或者B" role="presentation" style="position: relative;">BBB就可以在这基础上增加偶数个BBB。
那么问题就比较清楚了。但是T[c,d]" role="presentation" style="position: relative;">T[c,d]T[c,d]T[c,d]串最后的AAA是一定要被S[a,b]" role="presentation" style="position: relative;">S[a,b]S[a,b]S[a,b]最后的A抵消掉因为没有操作可以生成A并且把A插入到S[a,b]S[a,b]S[a,b]的最后。
分如下情况讨论
如果S[a,b]S[a,b]S[a,b]最后的AAA不足以抵消掉T[a,b]" role="presentation" style="position: relative;">T[a,b]T[a,b]T[a,b]的A那么输出0否则记录S[a,b]后面的A与T[a,b]的后面的A的差值记做delta2delta2delta2。如果delta20delta20delta2 = 0那么只需要比较S[a,b]S[a,b]S[a,b]中的BBB的数量和T[c,d]" role="presentation" style="position: relative;">T[c,d]T[c,d]T[c,d]中的BBB的数量，如果T[c,d]" role="presentation" style="position: relative;">T[c,d]T[c,d]T[c,d]中BBB的数量大于S[a,b]" role="presentation" style="position: relative;">S[a,b]S[a,b]S[a,b]中BBB的数量，那么差值必定要为2的倍数，并且如果T[c,d]" role="presentation" style="position: relative;">T[c,d]T[c,d]T[c,d]中BBB的数量不为0，那么S[a,b]" role="presentation" style="position: relative;">S[a,b]S[a,b]S[a,b]中BBB的数量也必须不为0(无法从空串生成BB" role="presentation" style="position: relative;">BBBBBB)。如果delta20delta20delta2 > 0那么如果S[a,b]S[a,b]S[a,b]中BBB的数量小于T[c,d]" role="presentation" style="position: relative;">T[c,d]T[c,d]T[c,d]中B的数量并且差值为偶数时候S[a,b]S[a,b]S[a,b]多出来的AAA可以用来生成BB" role="presentation" style="position: relative;">BBBBBB并且多余的A作为B的前缀可以被消除掉。如果delta20delta20delta2 > 0那么如果S[a,b]S[a,b]S[a,b]中BBB的数量等于T[c,d]" role="presentation" style="position: relative;">T[c,d]T[c,d]T[c,d]中B的数量那么delta2delta2delta2一定要被3整除。这样可以通过消除来得到TTscript typemath/tex idMathJax-Element-56T/script 代码
#include iostream
#include cstdio
#include cstring
using namespace std;
const int maxn 2e57;
char S[maxn],T[maxn];
int Q,a,b,c,d;
int sumS[maxn],sumT[maxn];
int lastS[maxn],lastT[maxn];
int main(){scanf( %s %s %d,S,T,Q);for(int i 0;S[i];i){sumS[i1] sumS[i] (S[i] C || S[i] B);lastS[i1] lastS[i];if(S[i] B || S[i] C)lastS[i1] i1;}for(int i 0;T[i];i){sumT[i1] sumT[i] (T[i] C || T[i] B);lastT[i1] lastT[i];if(T[i] B || T[i] C)lastT[i1] i1;}while(Q--){scanf(%d%d%d%d,a,b,c,d);int delta sumT[d]-sumS[b]sumS[a-1]-sumT[c-1];int delta2 b - max(a-1,lastS[b]) - (d - max(c-1,lastT[d]));if(delta 0 || delta % 2 ! 0 || delta2 0 || delta2 0 !(sumS[b] - sumS[a-1]) delta 0) {putchar(0);continue;}if(delta2 0 || delta 0 || delta2 % 3 0)putchar(1);else putchar(0);}return 0;
}
