0w1

ARC 064 D - An Ordinary Game ( Ad hoc, Game Theory )

D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder

題意:
給一個字串,每次可選取非兩端的任意字元使其消失,但前提是消失後不能有任意兩個相鄰字元相同。兩個人輪流做,先不能做的輸,求誰贏。

資料規模:
3 ≤ | S | ≤ 1e5

解法:
考慮最終狀態的長度基偶性。此時發現,兩端字元若一樣,則最後必然是奇數長度; 若不一樣,則一定是偶數長度( 或者為空 )。因此能用亦或判斷先手勝敗。

時間 / 空間複雜度:
O( 1 ) / O( N )

const string msg[] = { "First", "Second" };
string S;
 
void solve(){
  cin >> S;
  cout << msg[ ( S.size() % 2 == 0 ) ^ ( S.front() == S.back() ) ] << endl;
}