C. Diluc and Kaeya #724 Div.2

5465 ワード
2021.07.04 テキストリンク
https://codeforces.com/contest/1536/problem/C
2秒、256 MBメモリ
input :
  • t (1≤t≤1000)
  • n (1≤n≤5⋅10^5)
  • s(「D」,「K」からなる文字列)
    • output :
  • For each test case, output n space separated integers. The i-th of these numbers should equal the answer for the prefix s1,s2,…,si.n個の整数が各テストケースに出力される.i番目の数字は接頭辞の正解と同じです.
    • 条件:

  • They want to know the maximum number of pieces you can split the wood into such that the ratios of the number of occurrences of 'D' to the number of occurrences of 'K' in each chunk are the same.
    木を「D」の出現回数、「K」の出現回数の比率で区切った場合、最も多く得られる数を知りたい.

  • 'DDD' the ratio will be 3:0, for 'DKD' — 2:1, for 'DKK' — 1:2, and for 'KKKKDD' — 2:4. Note that the ratios of the latter two strings are equal to each other, but they are not equal to the ratios of the first two strings.
    例えば、「DDD」の割合は3:0、「DKD」の割合は2:1、「DKK」の割合は1:2、「KKKKDD」の割合は2:4である.最後の2つの割合は同じです.
    • 各部分の文字列を見ると、パーセンテージがすべての最大公約数に分割され、最小パーセンテージで作成される場合は、すでに作成されているのは1つだけです.
    私が书いた时もどういう意味だと思いましたか.
    DKのように1:2の比率で一度分けたことがあるなら.
    DKKKKDの場合は2種類に分けられます.[DKK][KKD]
    しかし、KKKDDについては1つと見なすべきである.比率はprefixで保存されているので、同じ比率で分けたことがないので、0から1つ計算します.
    x,y座標で説明すると,1:2,2:4が現れると,この2つが原点に接続されたときに同じ線上に置かれる.従って、上記カウントが成立する.
    import sys
from collections import defaultdict
import math

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

    ans = []
    D, K = 0, 0

    for item in data:
        if item == 'D':
            D += 1
        if item == 'K':
            K += 1

        gcd = math.gcd(D, K)
        d[(D // gcd, K // gcd)] += 1
        ans.append(d[(D // gcd, K // gcd)])

    print(* ans)
    最大公約数で最小の比率を決める.
    ディック・シャナリーにとっては、トーンキーを使用することができます.
    次いで、*배열이름を使用して配列の値を1行に出力する.
    [BOJ]1010架橋(Week 8,No.3)
    LinuxにDataiku DSSをインストールするには