C. A-B Palindrome | Round #713 Div.3

16611 ワード
2021.07.26 テキストリンク
https://codeforces.com/contest/1512/problem/A
2秒、256 MBメモリ
input :
  • t (1 ≤ t ≤ 104)
  • a b(0 ≤ a, b ≤ 2 * 105)
  • a+b長の文字列
    • output :
  • "-1", if you can't replace all the characters '?' in the string s by '0' or '1' so that the string becomes a palindrome and that it contains exactly a characters '0' and exactly b characters '1';
    the string that is obtained as a result of the replacement, otherwise.
    '?'「0」または「1」に置き換えられない文字列の場合、「0」がa文字列でない場合、「-1」が出力されます.そうでない場合は、新しく取得した文字列を出力します.
    • 条件:
  • You need to replace all the characters with '?' in the string s by '0' or '1' so that the string becomes a palindrome and has exactly a characters '0' and exactly b characters '1'. Note that each of the characters '?' is replaced independently from the others.
    '?'「0」または「1」に変更する場合は、返信を保持します.そして、正確には、「1」はb個、「0」はa個であるべきである.

    • palindrome


    私たちはまずファリン症候群かどうかを確認しなければなりません.一部を除いて、優先的に打たれた症候群でなければ、本人にはどうしようもない.
    しかも多くの条件が必要です.

    偶数


    パリンドロン文字列の場合、長さが奇数と偶数の場合に分けられます.まだあります.
    二つの字の中の一つ?この場合、すでに決まっていると思われるはずです.他の文字を挿入する方法を使うべきです.
    どちらも?それ以外は、a、b個の数を減らすようにカウントを続けます.
    だから、まず固定された文字をカウントして、それから2つとも計算しますか?これらのものを満たすことです.

    奇数


    ?記入し終わるときは残りの数字が奇数の場合に注意しましょう.
    毎回2つ消えてしまうと、足首をつかむことができます.
    import sys
import math

t = int(sys.stdin.readline())
for _ in range(t):
    temp_a, temp_b = map(int, sys.stdin.readline().split())
    a, b = temp_a, temp_b
    data = list(sys.stdin.readline().rstrip())
    right_idx, flag = len(data) - 1, 0

    for i in range(math.ceil(len(data) / 2)):
        if data[i] != '?' and data[right_idx] != '?':
            if data[i] != data[right_idx]:
                flag = 1
                break
        right_idx -= 1

    if (a % 2 == 1 and b % 2 == 1) or flag == 1:
        print(-1)
        continue

    right_idx = len(data) - 1
    for i in range(math.ceil(len(data) / 2)):
        if i == right_idx:
            if data[i] == '0':
                a -= 1
            elif data[i] == '1':
                b -= 1
            continue

        if data[i] != '?' and data[right_idx] == '?':
            if data[i] == '0':
                a -= 2
                data[right_idx] = '0'
            else:
                b -= 2
                data[right_idx] = '1'
        elif data[i] == '?' and data[right_idx] != '?':
            if data[right_idx] == '0':
                a -= 2
                data[i] = '0'
            else:
                b -= 2
                data[i] = '1'
        elif data[i] != '?' and data[right_idx] != '?':
            if data[i] == '0':
                a -= 2
            else:
                b -= 2

        right_idx -= 1
        
    right_idx = len(data) - 1
    for i in range(math.ceil(len(data) / 2)):
        if i == right_idx:
            if a > 0:
                data[i] = '0'
                a -= 1
            elif b > 0:
                data[i] = '1'
                b -= 1
            continue

        if data[i] == '?':
            if a > 1:
                data[i], data[right_idx] = '0', '0'
                a -= 2
            else:
                data[i], data[right_idx] = '1', '1'
                b -= 2

        right_idx -= 1

    if a == 0 and b == 0:
        for i in data:
            print(i, end="")
        print()
    else:
        print(-1)
    きれいに書かれていて、見た目はいい人もいますが、今ではなく、後で・・・やってみよう
    ZUFE 1035文字幅符号化(文字列)
    王小太りのBase 64コード/復号