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をコピーしました