Gが解けず。G1を終了二分後にAC。
コンテスト後のツイート
Codeforces Round 916 (Div. 3)
— titia (@titia_til) December 19, 2023
A Counter
B 大きい数を昇順→小さい数を降順
C 累積和
D 上位三個を全探索
E A[i]+B[i]が大きい方から使う
F 子孫の個数が多い枝を調べる
G1 グラフを作ってSCC
G2. Light Bulbs (Hard Version)
この解説の方法でACした。
区間に値を割り振り累積xorを取ると、0のところで区間が完全に分かれるので、最低何個点灯させればよいかは分かる。
さらに、「同じ値が二個出てくる区間」について考えると、これも他と独立していることが分かるので、そうでない部分のindexの個数を掛け合わせれば良い。
なお、ちゃんと理解していないが「区間に辺を張るテク」（セグ木を使うもの。検索すれば出てくる）でも解けるらしいので、こちらでも書けるようになっておくべきか。
0 件のコメント:
コメントを投稿