C. Sequence Pair Weight #721 Div.2
6271 ワード
https://codeforces.com/contest/1527/problem/C
2秒、256 MBメモリ
input : t (1 ≤ t ≤ 105) n (2 ≤ n ≤ 105) a1, a2, …, an (0 ≤ ai ≤ 100) output : For each test case, print a single integer — the sum of the weight of all subsegments of
各テストケースにおいて、 条件: The weightは、整列されていない配列の各要素が同じであれば、それらをグループ化することができ、これはこれらのグループの数を表す. 最も基礎的な方法で暴力を振るうなら?1万個ある場合、文字列ごとにどのような方法があるかを知る必要がある可能性があるので、少なくとも2回繰り返し、時間が爆発します.
まず解答を見てから理解しようと思ったが、まだ理解できなかった.下記のコメントでは、
この問題をdpで解いてください.一部の文字列については、長さで区切ることもできますが、可能です.
では、どんな機能があるのでしょうか.
dpのインデックス
2秒、256 MBメモリ
input :
a
.各テストケースにおいて、
weight
の合計が、すべての連続部分配列から出力される.weight
of a sequence is defined as the number of unordered pairs of indexes (i,j) (here iまず解答を見てから理解しようと思ったが、まだ理解できなかった.下記のコメントでは、
CQTshadow
の説明を見て、頭を整理するのは難しいです.この問題をdpで解いてください.一部の文字列については、長さで区切ることもできますが、可能です.
では、どんな機能があるのでしょうか.
dpのインデックス
ここで作成したdpのインデックスはどういう意味ですか?もちろん入力された配列の要素を指します.ではdpの計算はどうすればいいのでしょうか.要素は、配列内のインデックスを使用します.この部分がどういう意味か分かりません.
1 2 1を入力した場合
現在idxは3です.(1 2 1)
同じ値「1」が既に存在するので、それが含まれていることを記録したい.この場合、部分配列にするには[1,3]でなければなりません.
現在のidxが4の場合.(1 2 1 1)
同じ値が既に存在します.これらの値を含む配列を作成したいです.idx 3にいるやつを含めたいなら、[3,4],[2,4],[1,4]に参加することができます.(もちろん、インデックス1には同じ要素が存在するが、これは無視された数であり、現在の目的は3にあるやつだけを用いて無秩序pairを作成してカウントすることである)
idx 1にいるやつを置きたいなら[1,4]を置くことができます.では同時に2つ入れると?dp[idx-1]に記録された値が含まれます.
現在の配列のインデックス
したがって,作成可能な配列のインデックスは1から自分のインデックスである.インデックスの合計を格納します.
そうであれば、インデックスを記録する必要があります.そのため、私はあなたにディックシャナを作ってあげました.
dickshernerに値がある場合はansに値を追加する必要があります.そうしないと初期化されます.
文をループするときは、ディック文で値を更新し続けます.import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [0] * (n + 1)
temp = dict()
for idx in range(1, n + 1):
dp[idx] += dp[idx - 1]
if data[idx - 1] in temp:
dp[idx] += temp[data[idx - 1]]
else:
temp[data[idx - 1]] = 0
temp[data[idx - 1]] += idx
print(sum(dp))
Reference
この問題について(C. Sequence Pair Weight #721 Div.2), 我々は、より多くの情報をここで見つけました
https://velog.io/@jsin2475/C.-Sequence-Pair-Weight-721-Div.2
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
したがって,作成可能な配列のインデックスは1から自分のインデックスである.インデックスの合計を格納します.
そうであれば、インデックスを記録する必要があります.そのため、私はあなたにディックシャナを作ってあげました.
dickshernerに値がある場合はansに値を追加する必要があります.そうしないと初期化されます.
文をループするときは、ディック文で値を更新し続けます.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [0] * (n + 1)
temp = dict()
for idx in range(1, n + 1):
dp[idx] += dp[idx - 1]
if data[idx - 1] in temp:
dp[idx] += temp[data[idx - 1]]
else:
temp[data[idx - 1]] = 0
temp[data[idx - 1]] += idx
print(sum(dp))
Reference
この問題について(C. Sequence Pair Weight #721 Div.2), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/C.-Sequence-Pair-Weight-721-Div.2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol