[Codeforces] 1660C. Get an Even Strings [Codeforces Round #780 (Div. 3)]

3431 ワード
codeforces テキストリンク

📚 質問する


https://codeforces.com/problemset/problem/1660/C

📖 に答える


大会で1時間ほど悩んだが、解けなかった.
これは、文字列を偶数配列の文字列にするために、少なくとも数文字を消去する必要があるという問題です.
  • Input 
    • 6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
    最初の症例aabbdabdcccはaabbddccとすることができる.偶数個を連続して生成すればよい.
    2番目の症例zyxはすべて削除すればよい.
    入力した文字列の前から確認し、配列に文字列が存在しない場合は配列に入れます.配列に文字列がある場合は、その間の値を削除できます.したがって、配列内の他の文字は削除されます.そして並べ替えます.
    上記の手順を例として説明します.
    例1では、文字列はa a a b d a b d cである.最初の文字列から、1つずつ巡回して解きます.
  • aに並びます.[a]
  • a配列で、他の文字があるか確認します.ないので削除する文字がなく、配列も初期化されます.
  • bをアレイにロードします.[b]
  • bは配列中であり、他の文字は配列中ではないため、配列を初期化する.
  • dをアレイにロードします.[d]
  • aに並びます.[a, d]
  • bをアレイにロードします.[a, b, d]
  • d配列では,a,bを除いて配列を初期化する.(2個削除)
  • cをアレイにロードします.[c]
  • cアレイでアレイを初期化します.
  • cをアレイにロードします.[c]これが最後なので、cを取り除くべきです.(合計3個削除)
    • 以上の方法で3つを除去することが分かる.

    📒 コード#コード#

    t = int(input())
for _ in range(t):
    string = input()
    visited = []
    cnt = 0
    for i in string:
        if i in visited:
            cnt += len(visited) - 1
            visited = []
        else:
            visited.append(i)
    print(cnt + len(visited))

    🔍 結果


    継承制御継承/initial/unset
    [BOJ]1597:矢印を描く