0w1

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;
}