Codeforces ラウンド #281 (ディビジョン 2)_html/css_WEB-ITnose

この質問も難しくありません。

でも、私は面白くあり続けます。 質問を読み間違えたか、配列が小さすぎるかのどちらかです。

A、B、C、D はどれも非常に優れています。E は実際には非常に単純ですが、当時は理解できませんでした。 。

C、考えられるすべての ds を列挙するだけで、複雑さは nlogn でソートされます

D、奇数の場合、黒は勝つために白と対称的に動くだけで済みます

偶数がある場合、白1 と 2 に向かって 1 ステップ移動すると、奇数になります。その後、黒は対称に移動し、白は対称に移動します。つまり、最終的には白が必ず勝つでしょう

E

与えられた t, a, b について

最初に特別な判断を扱いましょう、

は t = 1, a= の場合に過ぎません。 1

によると、bが1に等しいかどうかは特別な判断です

その他の場合は方程式に依存します

a0+a1t+a2t^2+...=a

a0+a1a +a2a^2+...=b

次に、項を移動して

a1+a2t + a3t^2+...= (a-a0)/t

a1+a2a + a3a^2+...=(b-a0 ) /a

この問題は再帰的に解決できることがわかります。

ここで a0 の値には要件があります

(a-a0) %t ==0

(b-a0)%a==0

つまり、 a0%a == b % a , a0 % t = = a % t

すると、a0 を列挙する量は実際には非常に少ないことがわかりました

a0%a == b%a の場合、 a0= k * a + b %a0

a0 < ;= b && a0 <= a

k=0 または 1 であることがわかり、それは a0 % t == a % t を満たす必要があります

次のステップは再帰です。答えが出ました

rree