ARC 071 E - TrBBnsformBBtion ( Ad hoc )
E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder
題意:
給字串 S, T。Q 筆詢問,指定 S 的某個子字串 S', T 的某個子字串 T',問是否能透過施行以下操作任意次由 S' 轉換為 T'。
1. 將 'A' 換成 "BB"
2. 將 'B' 換成 "AA"
3. 將 "AAA" 換成 ""
4. 將 "BBB" 換成 ""
制約:
1≤|S|,|T|≤1e5
S,T は文字A,Bからなる。
1≤q≤1e5
1≤ai≤bi≤|S|
1≤ci≤di≤|T|
解法:
首先可以發現 "BB" 也可以變成 "A"。因此有一種像是群的概念的雙向等價關係。接著能發現 "A" 也可以變成 "AAAA",但無論怎麼變,個數除以 3 的餘不會改變。由等價關係都是雙向的這個觀察,可以得到啟發先將兩個字串都標準化,也就是全部統一成相同字符。由個數除以 3 的餘數不會改變的觀察,可以由兩個字串分別所含的字符個數直接判斷兩個字串是否等價。
時間 / 空間複雜度:
O( N + Q )
#include <bits/stdc++.h> using namespace std; const int MAXL = ( int ) 1e5 + 1; string S, T; int sapfx[ MAXL ], sbpfx[ MAXL ]; int tapfx[ MAXL ], tbpfx[ MAXL ]; signed main(){ ios::sync_with_stdio( 0 ); cin >> S >> T; for( int i = 0; i < S.size(); ++i ){ sapfx[ i + 1 ] = sapfx[ i ] + ( S[ i ] == 'A' ); sbpfx[ i + 1 ] = sbpfx[ i ] + ( S[ i ] == 'B' ); } for( int i = 0; i < T.size(); ++i ){ tapfx[ i + 1 ] = tapfx[ i ] + ( T[ i ] == 'A' ); tbpfx[ i + 1 ] = tbpfx[ i ] + ( T[ i ] == 'B' ); } int Q; cin >> Q; for( int qi = 0; qi < Q; ++qi ){ int slb, srb, tlb, trb; cin >> slb >> srb >> tlb >> trb; --slb, --tlb; // [ lb, rb ) int sa = sapfx[ srb ] - sapfx[ slb ]; int sb = sbpfx[ srb ] - sbpfx[ slb ]; int ta = tapfx[ trb ] - tapfx[ tlb ]; int tb = tbpfx[ trb ] - tbpfx[ tlb ]; int x = sa * 2 + sb; int y = ta * 2 + tb; if( x % 3 == y % 3 ){ cout << "YES\n"; } else{ cout << "NO\n"; } } return 0; }