Codeforces 1111簡単な問題解
文書ディレクトリ A題 B題 C題 D題 E題 トランスファゲート
A題
トランスポートゲートの問題の簡単な説明:26の26個の英文の字母を2種類のAに分けて、B A、B A、B、A A類の文字はA A類の文字に回転することができて、B類の文字はB類の文字に回転することができて、与えた2つの文字列のS S S SはT T Tに変換することができますかを聞きます
考え方:まず長さを判断して、それからS、T S、Tの中でA A類をa a aに変えて、B B類をb bに変えて、それから違いを見ます.コード:
B題
転送ゲートの問題の簡単な説明:n nの数をあげて、あなたは多くのm m m回まで操作することができて、毎回1つの数に1 1 1をプラスするか、あるいは1つの数を削除して、最後に残った数の最大平均値を聞くことができます.
考え方:すべての数を並べ替えて、前のi i iの数を列挙して答えを更新すればいい.
コード:
C題
トランスポートゲートの問題は簡単に述べる:1つの2 n 2^n 2 nの長いシーケンスに、n≦30 nle 30 n≦30を与えて、その中にk k個の特殊な点k≦100000 kle 100000 k≦100000があって、今シーケンス全体を除去することを要求して、現在のシーケンスに対していくつかの操作方式があります.現在のシーケンス等分をそれぞれ 除去する.現在のシーケンスを消去し、現在のシーケンスに特別なポイントがない場合A Aを費やす.そうでない場合、B∗特殊ポイント数∗現在のシーケンス長B*特殊ポイント数*現在のシーケンス長B∗特殊ポイント数∗現在のシーケンス長 を費やす
保証A,B≧0 A,Bge 0 A,B≧0はシーケンス全体の最小費用を除去する.
考え方:現在の区間に特殊点が1つしか残っていない場合はB Bを直接返し、特殊点がなければA A Aを直接返し、そうでなければ題意通りにシミュレーションします.
コード:
D題
転送ドアのタイトルの簡単な説明:n,n≦1 e 5 n,nle 1 e 5 n,n≦1 e 5色(色は最大52,52,52種)の点(n n n nは偶数)を任意に配列することができ、合法的な配列は各色について、すべての色の点が前半または同後半にあることを規定し、現在q q qはq≦100000 qle 100000 q≦100000 q,2つの色x,y x,y x,yを指定するたびに、この2つの色に対応するすべての点が前半または後半にあることを要求し、この条件の下で合法的なシーケンスの個数を尋ねる.
考え方:色ごとの個数を貯金して、01 01リュックサックを作ることを考えて、f i f_i fiは、i i iを絞り出すシナリオ数を表す.このように順序とx,y x,y x,yの制限f n 2 f_を考慮しない{frac n 2}f 2 nはすべての合法的なシーケンス数であり、その後、x、y x、y x、yのペアごとにそれらの寄与をa n s x、y ans_として列挙する.{x,y}ansx,yは終わりです.最後に順序の問題を考慮すると,合法的なシーケンス数に対して明らかに対応できる(n 2!)2 ∗ ∏ i = 0 , 52 i n v f a c c n t i (\frac n2!)^2*\prod_{i=0,52}invfac_{cnt_i} (2n!)2∗∏i=0,52 invfaccti中放法.
コード:
E題
転送ドアのテーマは簡単に説明します:あなたに1本の木をあげて、毎回あなたにいくつかの肝心な点と1つの根と1つのmをあげて、あなたにこれらの点を多くのmグループに分けて各グループの任意の2つの数を満たすように要求して祖先の関係がなくて、方案の数を求めます.キー総数≦100000,n≦100000,m≦m i n{n,300}le 100000,nle 100000,mle min{n,300}≦100000,n≦100000,m≦min{n,300}を満たす
構想:1 1がルートである場合を直接考慮し、現在のすべてのキーを抽出して1つの集合を構成し、1つのf i,j f_を記す.{i,j}fi,jは集合中の前i i i個の数をj j j個のグループに分けてパケット方式で題意を満たすシナリオ数,g i g_を表す.i giは集合中のi i iの祖先の個数を表し,明らかにf i,j=f i−1,j−1+f i−1,j∗(j−g i)f_{i,j}=f_{i-1,j-1}+f_{i−1,j}*(j−g_i)fi,j=fi−1,j−1+fi−1,j∗(j−gi)というように,g g配列を毎回考慮するだけでよい.すべての点のd f s dfs dfsシーケンスを作成し、ツリー配列でg g gを維持し、ルートをl c a lca lcaで差分すればよい.
コード:
A題
トランスポートゲートの問題の簡単な説明:26の26個の英文の字母を2種類のAに分けて、B A、B A、B、A A類の文字はA A類の文字に回転することができて、B類の文字はB類の文字に回転することができて、与えた2つの文字列のS S S SはT T Tに変換することができますかを聞きます
考え方:まず長さを判断して、それからS、T S、Tの中でA A類をa a aに変えて、B B類をb bに変えて、それから違いを見ます.コード:
#includeB題
転送ゲートの問題の簡単な説明:n nの数をあげて、あなたは多くのm m m回まで操作することができて、毎回1つの数に1 1 1をプラスするか、あるいは1つの数を削除して、最後に残った数の最大平均値を聞くことができます.
考え方:すべての数を並べ替えて、前のi i iの数を列挙して答えを更新すればいい.
コード:
#include
",ans);
return 0;
}
C題
トランスポートゲートの問題は簡単に述べる:1つの2 n 2^n 2 nの長いシーケンスに、n≦30 nle 30 n≦30を与えて、その中にk k個の特殊な点k≦100000 kle 100000 k≦100000があって、今シーケンス全体を除去することを要求して、現在のシーケンスに対していくつかの操作方式があります.
保証A,B≧0 A,Bge 0 A,B≧0はシーケンス全体の最小費用を除去する.
考え方:現在の区間に特殊点が1つしか残っていない場合はB Bを直接返し、特殊点がなければA A Aを直接返し、そうでなければ題意通りにシミュレーションします.
コード:
#includeD題
転送ドアのタイトルの簡単な説明:n,n≦1 e 5 n,nle 1 e 5 n,n≦1 e 5色(色は最大52,52,52種)の点(n n n nは偶数)を任意に配列することができ、合法的な配列は各色について、すべての色の点が前半または同後半にあることを規定し、現在q q qはq≦100000 qle 100000 q≦100000 q,2つの色x,y x,y x,yを指定するたびに、この2つの色に対応するすべての点が前半または後半にあることを要求し、この条件の下で合法的なシーケンスの個数を尋ねる.
考え方:色ごとの個数を貯金して、01 01リュックサックを作ることを考えて、f i f_i fiは、i i iを絞り出すシナリオ数を表す.このように順序とx,y x,y x,yの制限f n 2 f_を考慮しない{frac n 2}f 2 nはすべての合法的なシーケンス数であり、その後、x、y x、y x、yのペアごとにそれらの寄与をa n s x、y ans_として列挙する.{x,y}ansx,yは終わりです.最後に順序の問題を考慮すると,合法的なシーケンス数に対して明らかに対応できる(n 2!)2 ∗ ∏ i = 0 , 52 i n v f a c c n t i (\frac n2!)^2*\prod_{i=0,52}invfac_{cnt_i} (2n!)2∗∏i=0,52 invfaccti中放法.
コード:
#include
';
}
return 0;
}
E題
転送ドアのテーマは簡単に説明します:あなたに1本の木をあげて、毎回あなたにいくつかの肝心な点と1つの根と1つのmをあげて、あなたにこれらの点を多くのmグループに分けて各グループの任意の2つの数を満たすように要求して祖先の関係がなくて、方案の数を求めます.キー総数≦100000,n≦100000,m≦m i n{n,300}le 100000,nle 100000,mle min{n,300}≦100000,n≦100000,m≦min{n,300}を満たす
構想:1 1がルートである場合を直接考慮し、現在のすべてのキーを抽出して1つの集合を構成し、1つのf i,j f_を記す.{i,j}fi,jは集合中の前i i i個の数をj j j個のグループに分けてパケット方式で題意を満たすシナリオ数,g i g_を表す.i giは集合中のi i iの祖先の個数を表し,明らかにf i,j=f i−1,j−1+f i−1,j∗(j−g i)f_{i,j}=f_{i-1,j-1}+f_{i−1,j}*(j−g_i)fi,j=fi−1,j−1+fi−1,j∗(j−gi)というように,g g配列を毎回考慮するだけでよい.すべての点のd f s dfs dfsシーケンスを作成し、ツリー配列でg g gを維持し、ルートをl c a lca lcaで差分すればよい.
コード:
#include
';
}
return 0;
}