題目鏈接

Picking String

題意

給出字符串S和T，1e5個詢問，每次詢問S的一段區(qū)間是否能轉(zhuǎn)變成T的一段區(qū)間。
轉(zhuǎn)變方式：

• A>BCA>BC
• B>ACB>AC
• C>ABC>AB
• AAAAAA可以消除

---

題解

我們從以上四個條件出發(fā)推導出更加精華的條件

• B>AC>AAB>AAAC>CB>AC>AAB>AAAC>C
• C>AB>AAC>AAAB>BC>AB>AAC>AAAB>B
• A>BC>BBA>BC>BB

也就是說所有的CC都等價于BB

由于B>ACB>AC也就是B>ABB>AB，而3個AA可以消除，這個操作意味著B前面可以有任意多個AA，所以說，BB前面的緊貼著的AA的數(shù)量我們可以忽略。

由于B>AB>BBB>ABBB>BBBBB，A>BB>ABB>BBBBB>AB>BBB>ABBB>BBBBB，A>BB>ABB>BBBB也就是說，我們只要有一個AA或者BB就可以在這基礎上增加偶數(shù)個BB。
那么問題就比較清楚了。

但是T[c,d]T[c,d]串最后的AA是一定要被S[a,b]S[a,b]最后的A抵消掉，因為沒有操作可以生成A并且把A插入到S[a,b]S[a,b]的最后。

分如下情況討論：

• 如果S[a,b]S[a,b]最后的AA不足以抵消掉T[a,b]T[a,b]的A，那么輸出0，否則記錄S[a,b]后面的A與T[a,b]的后面的A的差值，記做delta2delta2。

• 如果delta2=0delta2=0那么只需要比較S[a,b]S[a,b]中的BB的數(shù)量和T[c,d]T[c,d]中的BB的數(shù)量，如果T[c,d]T[c,d]中BB的數(shù)量大于S[a,b]S[a,b]中BB的數(shù)量，那么差值必定要為2的倍數(shù)，并且如果T[c,d]T[c,d]中BB的數(shù)量不為0，那么S[a,b]S[a,b]中BB的數(shù)量也必須不為0(無法從空串生成BBBB)。

• 如果delta2>0delta2>0那么如果S[a,b]S[a,b]中BB的數(shù)量小于T[c,d]T[c,d]中B的數(shù)量，并且差值為偶數(shù)時候，S[a,b]S[a,b]多出來的AA可以用來生成BBBB，并且多余的A作為B的前綴可以被消除掉。

• 如果delta2>0delta2>0那么如果S[a,b]S[a,b]中BB的數(shù)量等于T[c,d]T[c,d]中B的數(shù)量，那么delta2delta2一定要被3整除。這樣可以通過消除來得到TT<script type="math/tex" id="MathJax-Element-56">T</script>

---

代碼

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 2e5+7; 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[i+1] = sumS[i] + (S[i] == 'C' || S[i] == 'B');lastS[i+1] = lastS[i];if(S[i] == 'B' || S[i] == 'C')lastS[i+1] = i+1;}for(int i = 0;T[i];++i){sumT[i+1] = sumT[i] + (T[i] == 'C' || T[i] == 'B');lastT[i+1] = lastT[i];if(T[i] == 'B' || T[i] == 'C')lastT[i+1] = i+1;}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; }

總結

以上是生活随笔為你收集整理的codeforces E. Picking Strings 构造的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。