Codeforces 1197簡単な問題解
文書ディレクトリ A題 B題 C題 D題 E題 F題 レースゲート
A題
トランスポートゲートは、次いで、a[n−1]−1 a[n−1]−1 a[n−1]−1とn−2 n−2 n−2の最小値をとる.コード:
B題
転送ドアは勝手に双方向チェーンテーブルを書いて、問題に従ってシミュレーションします.コード:
C題
トランスポートゲートは変換問題を考慮する.a i−a i−1 aを求めるようになるi-a_{i−1}ai−ai−1の前k−1 k−1 k−1の大きい値を用い,その後a n−a 1 a_n-a_1 an−a 1からそれらの和を減算すればよい.コード:
D題
転送ゲートはO(n)O(n)O(n)O(n)ができるはずだが、ブロガーは怠け者でO(n m)O(nm)O(nm)を書いた.i fiは、区間左端点がi i i iの場合の最適値を表す.このi i i iを右から左に列挙することを考える.そこで、1つの左端点i i i iについて、2つの状況を考慮する必要があります.⌈r−l+1 m⌉=1lceilfrac{r−l+1}{m}rceil=1⌈mr−l+1⌉=1,直接O(m)O(m)暴力列挙でよい. ⌈r−l+1 m⌉>1lceilfrac{r−l+1}{m}rceil>1⌈mr−l+1⌉>1であると、i i i i~i+m−1 i+m−1 i+m−1 i+m−m−1が選択され、i+m i+m i+m i+m i+m~n nにおいて⌈r−l+1 m⌉−l+1lceilfrac{ r−l+1}{m}rceil−1{m}rceil−1{m}rceil−1{m}rceil−1{m}rceil−1{m}rce⌈mr−l+1⌉−1群であれば、f i+mf_{i+m}fi+mは最適値を導出し,O(1)O(1)O(1)遷移であった.
どちらの場合も最大値を取ればいいです.
E題
転送ゲートが離散化した後、境界がw a wa waを3回書き間違えた...まず左右の端点を離散化した.一つの区間[l i,r i][l_i,r_i][li,ri]に対してのみ、r j≦l i r_を満たすj\le l_i rj≦liの区間はそれに影響を与えることができ、問題の意味に基づいて、私たちは各区間に対してこのような情報を維持しなければならない.開始から現在の区間までの総空桁数の最小値は です.開始から現在の区間までの総空桁数が最小値に等しいシナリオ数を満たす 点p p pに対して、k k kの方式がp p pで終了し、総空位数の最小値がd i s disに等しいとすると、p p pがq q qに移行できる場合、総空位数はd i s+q−p=d i s−p+q dis+q−p=dis−p+q−dis+q−p=dis−p+qとなり、1つのr j r_r_qからj rjはl i l_に移行することができるi li,必ずd i s r j−r j=minr k≦l i{d i s r k−r k}dis_を満たす{r_j}-r_j=\min_{r_k\le l_i}\{dis_{r_k}-r_k}disrj−rj=minrk≦li{disrk−rk}では,線分ツリー上でd i s p−p dis_を維持する.{p}−p disp−pの最小値とこの最小値の出現回数でよい.
コード:
F題
コンベヤーは私が長い間考えていた問題を感じていたが、試合中に問題を間違えてできなかったので、問題解を見て突然自分が問題を間違えたことに気づいた.の布袋が1枚しかないことを考えています.せいぜい3 3、3歩しか歩けないことに気づいた.状態f i,0/1,0/1,0/1,0/1 f_を設計することができる.{i,0/1,0/1,0/1}fi,0/1,0/1,0/1,0/1は前のi i i個の格子を表し,最後の3個の格子から出発したn p np np状態は0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1のスキーム数であり,これにより問題中の制限配列に基づいて状態遷移時を書き出すことができる.しかし、布の長さが大きいため、直接T L E TLE TLEを作ることができ、マトリクスの高速べき乗を最適化することができ、色が与えられた場所ごとに色がない場所と移動式が異なることが分かった.そこで、色ごとに移動式を前処理し、2つの塗布格子間のスペースごとにマトリクスで高速べき乗で移動すればよい.複雑度はO(m∗a 3 l o g 2 a n)O(m*a^3 log_2 a_n)O(m∗a 3 log 2 an)であり,a a a aは行列辺長である.時間の複雑さを最適化できますか?明らかに可能であり、最後に行列全体の値ではなくベクトルを1つ求めるだけであるため、2 k 2^k 2 k個のスペースの行列を前処理し、次いで倍増転送するたびに、O(m∗a 2∗l o g 2 a n)O(m*a^2*log_2 a_n)O(m∗a 2∗log 2 an)の時間的複雑さを達成することができる.
今は複数の布がある場合を考えています.n p np npの状態をs g sg sg関数値に変えて最後にパケットバックパックのような方法で移行すればよいことが分かった.この問題のs g sg値は3 3 3 3を超えないため、総複雑度はO(m a 2 l o g 2 a)O(ma^2 log_2 a_n)O(ma 2 log 2 an)であり、ここでa=64 a=64 a=64 a=64である.コード:
A題
トランスポートゲートは、次いで、a[n−1]−1 a[n−1]−1 a[n−1]−1とn−2 n−2 n−2の最小値をとる.コード:
#include
';
}
return 0;
}
B題
転送ドアは勝手に双方向チェーンテーブルを書いて、問題に従ってシミュレーションします.コード:
#includeC題
トランスポートゲートは変換問題を考慮する.a i−a i−1 aを求めるようになるi-a_{i−1}ai−ai−1の前k−1 k−1 k−1の大きい値を用い,その後a n−a 1 a_n-a_1 an−a 1からそれらの和を減算すればよい.コード:
#includeD題
転送ゲートはO(n)O(n)O(n)O(n)ができるはずだが、ブロガーは怠け者でO(n m)O(nm)O(nm)を書いた.i fiは、区間左端点がi i i iの場合の最適値を表す.このi i i iを右から左に列挙することを考える.そこで、1つの左端点i i i iについて、2つの状況を考慮する必要があります.
どちらの場合も最大値を取ればいいです.
#includeE題
転送ゲートが離散化した後、境界がw a wa waを3回書き間違えた...まず左右の端点を離散化した.一つの区間[l i,r i][l_i,r_i][li,ri]に対してのみ、r j≦l i r_を満たすj\le l_i rj≦liの区間はそれに影響を与えることができ、問題の意味に基づいて、私たちは各区間に対してこのような情報を維持しなければならない.
コード:
#includeF題
コンベヤーは私が長い間考えていた問題を感じていたが、試合中に問題を間違えてできなかったので、問題解を見て突然自分が問題を間違えたことに気づいた.の布袋が1枚しかないことを考えています.せいぜい3 3、3歩しか歩けないことに気づいた.状態f i,0/1,0/1,0/1,0/1 f_を設計することができる.{i,0/1,0/1,0/1}fi,0/1,0/1,0/1,0/1は前のi i i個の格子を表し,最後の3個の格子から出発したn p np np状態は0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1のスキーム数であり,これにより問題中の制限配列に基づいて状態遷移時を書き出すことができる.しかし、布の長さが大きいため、直接T L E TLE TLEを作ることができ、マトリクスの高速べき乗を最適化することができ、色が与えられた場所ごとに色がない場所と移動式が異なることが分かった.そこで、色ごとに移動式を前処理し、2つの塗布格子間のスペースごとにマトリクスで高速べき乗で移動すればよい.複雑度はO(m∗a 3 l o g 2 a n)O(m*a^3 log_2 a_n)O(m∗a 3 log 2 an)であり,a a a aは行列辺長である.時間の複雑さを最適化できますか?明らかに可能であり、最後に行列全体の値ではなくベクトルを1つ求めるだけであるため、2 k 2^k 2 k個のスペースの行列を前処理し、次いで倍増転送するたびに、O(m∗a 2∗l o g 2 a n)O(m*a^2*log_2 a_n)O(m∗a 2∗log 2 an)の時間的複雑さを達成することができる.
今は複数の布がある場合を考えています.n p np npの状態をs g sg sg関数値に変えて最後にパケットバックパックのような方法で移行すればよいことが分かった.この問題のs g sg値は3 3 3 3を超えないため、総複雑度はO(m a 2 l o g 2 a)O(ma^2 log_2 a_n)O(ma 2 log 2 an)であり、ここでa=64 a=64 a=64 a=64である.コード:
#include