Educational Codeforces Round 71

スポンサーリンク

A. There Are Two Types Of Burgers

制約が小さいので全探索で大丈夫です.

B. Square Filling

操作可能な場所はすべて操作するとしてよいです.

C. Gas Pipeline

最後の高さをキーとして dp します.

D. Number Of Permutations

片方が増加になる場合,両方が増加する場合を計算します.多項係数になります.

E. XOR Guessing

$[0,127]$ から $100$ 個を送信すると,$x$ の上位 $7$ bit が得られます.

$128$ の倍数を $100$ 個送信すると,$x$ の下位 $7$ bit が得られます.

F. Remainder Problem

適当なしきい値を設定します.

mod がしきい値より小さい場合の答は,変更クエリごとに更新します.

mod がしきい値より大きい場合は,求値クエリごとに計算します.

クエリごとに $O(\sqrt{A})$ 時間が達成できます.

G. Indie Album

$s_i$ から構築した trie を $S$,$t$ から構築した trie を $T$ とします.$T$ については Aho Corasick 法で suffix link を求めておきます.

suffix link に関する木構造を suf(T) とします.$s_i$ を固定したときのクエリ処理はどうなるかというと,$s_i$ にしたがって $T$ を移動したあと,$t\in T$ の suf(T) の subtree 内で通った点の個数を数えればよいです.つまり,trie をたどりながら点加算と部分木クエリをすればよいです.

木 $S$ を dfs しながらこれを行えば,すべての $s_i$ に対するクエリを処理できます.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました