B2. Palindrome Game (hard version) #721 Div.2

6053 ワード
2021.07.07 テキストリンク
https://codeforces.com/contest/1527/problem/B2
1秒、256 MBメモリ
input :
  • t (1≤t≤103)
  • n (1≤n≤103)
  • string s of length n
    • output :
  • For each test case print a single word in a new line:
    "ALICE", if Alice will win the game,
    "BOB", if Bob will win the game,
    "DRAW", if the game ends in a draw.
    • 各テストケースで、次のいずれかの単語を出力します.
    Alicが勝ったら「ALICE」、Bobが勝ったら「BOB」、引き分けたら「DRAW」を出力します.
    条件:

  • Both players take alternate turns with Alice going first.
    プレイヤーたちは交代で遊ぶ.先制攻撃はアリスが取った

  • Choose any i (1≤i≤n), where s[i]= '0' and change s[i] to '1'. Pay 1 dollar.iポイントの代わりに1ドルを支払う.

  • Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse.
    文字列を反転します.この条件は、文字列が返信文でない場合にのみ使用できます.そして相手の行動はreverseではない.
    • ああ...どうして飛んで行ったのか...
    とりあえず、ファリン症候群なら、もうB 1です.で確認しました.現在入力されている文字列は空ではない可能性があります.

    ファリンドロンじゃない時


    アリスが勝つどうしたんですか.ファリンドロンではないときはずっとひっくり返すことができます.
    だから続けてひっくり返すと、ボブは一つ一つおろして、ファリンドロンに近づいてきて、アリスは1をおろして、ファリンドロンになると、ボブは一度もひっくり返せないので、刺繍を続けます.

    引き分け。


    しかし、考慮すべきこともある.110101111のような文字列では、どうしても引き分けが発生します.0が2つで、真ん中に0があるとき.
    0が2より大きい場合
    110001111の時にひっくり返し続け、ファリンドロンになる前に1を置いて、ファリンドロンになると、また同じことが起こります.
    だからファリン症候群であることを確認し、上の条件を確認します.
    import sys

t = int(sys.stdin.readline())
for i in range(t):
  n = int(sys.stdin.readline())
  data = sys.stdin.readline().rstrip()

  zeros = 0
  for item in data:
      if item == '0':
          zeros += 1

  if data == data[::-1]:
      if zeros == 1 or zeros % 2 == 0:
          print("BOB")
      else:
          print("ALICE")
  else:
      if zeros == 2 and len(data) % 2 == 1 and data[len(data) // 2] == '0':
          print("DRAW")
      else:
          print("ALICE")
    7月19日(月)[JS/Node]対象
    [白俊#2493]塔