【問題作成記録】2020-7問題作成記録
3601 ワード
筆者は時間が迫っているので,この文章は不完全に書かれているかもしれない.ご了承ください.後で修正するかもしれません.
今月はテンプレートの問題を何度もやったかもしれませんが、習熟度を練習したいと思っています.
次のテーマの叙述はただあなたに大まかなことを教えて、いくつかの下書きの細部の処理に問題があるかもしれません.
シーケンス番号
テーマソース
テーマの概要
簡単な問題解
コメント
1
[P 2742 USACO 5.1]輪乳牛Fencing the Cows/【テンプレート】二次元凸包
個の点を与えて、2次元の凸包を求めます
まず(x)軸に従って、(y)軸に従って並べ替えて、単調スタックでやればいいです.
(y)軸も並べ替えなければなりません
2
[P 1452 USACO 03 FALL]Beauty Contest G/【テンプレート】回転チャック
平面の最も遠い点の対を求めます
まず凸包を求め,次に各辺の踵点を求めればよい.
注意特判(n=2)が必要な場合
3
P 5245【テンプレート】多項式快速べき乗
多項式の高速べき乗を与える
まず
何でもない
4
P 4238【テンプレート】多項式乗算逆
与えられた多項式の乗算逆を求める
ニュートン反復でいい
何でもない
5
P 4725【テンプレート】多項式対数関数(多項式ln)
与えられた多項式(f(x))、求め(ln f(x))
((ln f(x)'=frac{f(x)}{f'(x)})、この式を直接セットすればよい
何でもない
6
[P 4841合宿隊作業2013]都市計画
個の点の無方向の連通図の数量を求めます
無方向連通図数生成関数を(f(x))とすると(exp f(x))は無方向図数となるので多項式(ln)でよい
何でもない
7
P 1429平面直近点対(補強版)
平面の最も近い点の対を求めます
分治すればよいが,テンプレートの問題は多く言わない.
何でもない
8
CF575A Fibonotci
各位置には(s_i)が1つあり、繰返し数列(a_i=s_{i-1}cdot a_{i-1}+s_{i-2}cdot a_{i-2})があり、(s_i)は周期的であるが、周期の法則に合致する位置もある(問題はどれだけであるかを示す).第(n)項を求めます.
非周期部分は線分ツリーを使用して維持し、残りの部分は直接高速べき乗でよい.
何でもない
9
P 4980【テンプレート】Pólya定理
(n)個の点、(n)個の辺の環、各点に染色して、本質の異なる方案数を求める(本質の違いは回転によって他の方案と同じものを得ることができないと定義する)
テンプレートの問題はあまり言わない
何でもない
10
CF161D Distance in Tree
木の上で距離を求めて(k)の点の対数です
テンプレートの問題はあまり言わない
何でもない
11
[P3597 POI2015]WYC
1枚の図は長さが1,2,3の経路があって、第(k)の長い経路の長さを求めます
問題解
何でもない
12
[P 5364 SNOI 2017]プレゼント
\(s_i=2s_{i-1}+i^k\)
問題解
何でもない
13
P 2408異なるサブストリング数
本質的に異なる文字列の個数
SAMの練習
何でもない
14
[P 3975 TJOI 2015]弦論
辞書の順序の第(k)の小さい子の列を求めます
問題解
何でもない
15
[P 5894 IOI 2013]robotsロボット
テーマ叙述
問題解
何でもない
16
P 6577【テンプレート】二分図最大重み完璧マッチング
二分図のすべての完璧なマッチングの中で最も大きいものを求めます
KMアルゴリズムのテンプレートの問題、詳しくは15年のマッチングアルゴリズムについての論文を参照してください
何でもない
17
P 4311兵士占領
(ntimes m)の碁盤は、中に駒を入れます.行ごとに少なくとも(l_i)個、列ごとに少なくとも(c_i)個、障害があり、置くことができません.少なくとも何個の駒を放してようやく要求を満たすことができることを求めます
単純なネットワークフローの問題
何でもない
18
[P 4249 WC 2007]はさみ石布
(n)個の点の有向図、いくつかの辺を加えて、この図の三元環の数が最も多いようにします
問題解
何でもない
19
CF613D Kingdom and its Cities
1本の木にあげて、毎回(k)個の点を選んで、少なくとも木の上の何個の点を削除してこの(k)個の点が連通しないようにします
ダミーツリーテンプレートの問題
何でもない
20
[P 04357 CQOI 2016]K遠点対
いくつかの点をあげて、(k)の遠い点の対を求めます
k-d treeテンプレート問題
何でもない
21
CF786B Legacy
1枚の図をあげて、辺はこのようにです:1つの点は1つの点の辺あるいは1つの区間は1つの点の辺あるいは1つの点は1つの区間の辺に向かって、最短の道を求めます
線分ツリーを使用して図面を最適化すればよい
何でもない
22
[P 5471 NOI 2019]ジャンプ
点の方向の区間は辺につながって、最短のショートを求めます
k−d treeは構築図を最適化し,スタックの代わりにk−d treeを用いてk−d treeに弛緩怠惰マーカーを打つ
何でもない
23
B - Good Triple
1つの01列をあげて、区間のメモリが3つの位置で等差数の列になってしかも値の等しい区間の数量を求めます
区間長(ge 9)であれば必ず可能であることが分かりやすいので、左端点を選択し、列挙して区間長の最小値を計算すればよい.
何でもない
24
A - Increasing by Modulo
略
略
簡単すぎる
25
D - Flights for Regular Customers
テーマ叙述
問題解
何でもない
26
F - Ants on a Circle
テーマ叙述
問題解
何でもない
27
Game of Stones
二人で石を取り、二人がある山の上で一度取ったことがある(s={a_1,a_2,cdots,a_n})という式を設定すると、次の式の数(xotin s)となる.誰が勝つか
SGを計算すればよい.
何でもない
28
Three Circuits
1つの図が3つのオーラ戻り路に分解できるかどうかを判断し、各エッジは1つのオーラ戻り路に属するしかない.
問題解
何でもない
29
A Sequence of Permutations
問題解
何でもない
30
問題解
問題解というリンクには、筆者が作った4つの問題が含まれています.テーマの叙述、出所と問題解はすべてあります.
これらの問題のほかにいくつかの修正された試験問題と124の問題があります.
今月はテンプレートの問題を何度もやったかもしれませんが、習熟度を練習したいと思っています.
次のテーマの叙述はただあなたに大まかなことを教えて、いくつかの下書きの細部の処理に問題があるかもしれません.
シーケンス番号
テーマソース
テーマの概要
簡単な問題解
コメント
1
[P 2742 USACO 5.1]輪乳牛Fencing the Cows/【テンプレート】二次元凸包
個の点を与えて、2次元の凸包を求めます
まず(x)軸に従って、(y)軸に従って並べ替えて、単調スタックでやればいいです.
(y)軸も並べ替えなければなりません
2
[P 1452 USACO 03 FALL]Beauty Contest G/【テンプレート】回転チャック
平面の最も遠い点の対を求めます
まず凸包を求め,次に各辺の踵点を求めればよい.
注意特判(n=2)が必要な場合
3
P 5245【テンプレート】多項式快速べき乗
多項式の高速べき乗を与える
まず
lnに回数を乗じてexpでよい何でもない
4
P 4238【テンプレート】多項式乗算逆
与えられた多項式の乗算逆を求める
ニュートン反復でいい
何でもない
5
P 4725【テンプレート】多項式対数関数(多項式ln)
与えられた多項式(f(x))、求め(ln f(x))
((ln f(x)'=frac{f(x)}{f'(x)})、この式を直接セットすればよい
何でもない
6
[P 4841合宿隊作業2013]都市計画
個の点の無方向の連通図の数量を求めます
無方向連通図数生成関数を(f(x))とすると(exp f(x))は無方向図数となるので多項式(ln)でよい
何でもない
7
P 1429平面直近点対(補強版)
平面の最も近い点の対を求めます
分治すればよいが,テンプレートの問題は多く言わない.
何でもない
8
CF575A Fibonotci
各位置には(s_i)が1つあり、繰返し数列(a_i=s_{i-1}cdot a_{i-1}+s_{i-2}cdot a_{i-2})があり、(s_i)は周期的であるが、周期の法則に合致する位置もある(問題はどれだけであるかを示す).第(n)項を求めます.
非周期部分は線分ツリーを使用して維持し、残りの部分は直接高速べき乗でよい.
何でもない
9
P 4980【テンプレート】Pólya定理
(n)個の点、(n)個の辺の環、各点に染色して、本質の異なる方案数を求める(本質の違いは回転によって他の方案と同じものを得ることができないと定義する)
テンプレートの問題はあまり言わない
何でもない
10
CF161D Distance in Tree
木の上で距離を求めて(k)の点の対数です
テンプレートの問題はあまり言わない
何でもない
11
[P3597 POI2015]WYC
1枚の図は長さが1,2,3の経路があって、第(k)の長い経路の長さを求めます
問題解
何でもない
12
[P 5364 SNOI 2017]プレゼント
\(s_i=2s_{i-1}+i^k\)
問題解
何でもない
13
P 2408異なるサブストリング数
本質的に異なる文字列の個数
SAMの練習
何でもない
14
[P 3975 TJOI 2015]弦論
辞書の順序の第(k)の小さい子の列を求めます
問題解
何でもない
15
[P 5894 IOI 2013]robotsロボット
テーマ叙述
問題解
何でもない
16
P 6577【テンプレート】二分図最大重み完璧マッチング
二分図のすべての完璧なマッチングの中で最も大きいものを求めます
KMアルゴリズムのテンプレートの問題、詳しくは15年のマッチングアルゴリズムについての論文を参照してください
何でもない
17
P 4311兵士占領
(ntimes m)の碁盤は、中に駒を入れます.行ごとに少なくとも(l_i)個、列ごとに少なくとも(c_i)個、障害があり、置くことができません.少なくとも何個の駒を放してようやく要求を満たすことができることを求めます
単純なネットワークフローの問題
何でもない
18
[P 4249 WC 2007]はさみ石布
(n)個の点の有向図、いくつかの辺を加えて、この図の三元環の数が最も多いようにします
問題解
何でもない
19
CF613D Kingdom and its Cities
1本の木にあげて、毎回(k)個の点を選んで、少なくとも木の上の何個の点を削除してこの(k)個の点が連通しないようにします
ダミーツリーテンプレートの問題
何でもない
20
[P 04357 CQOI 2016]K遠点対
いくつかの点をあげて、(k)の遠い点の対を求めます
k-d treeテンプレート問題
何でもない
21
CF786B Legacy
1枚の図をあげて、辺はこのようにです:1つの点は1つの点の辺あるいは1つの区間は1つの点の辺あるいは1つの点は1つの区間の辺に向かって、最短の道を求めます
線分ツリーを使用して図面を最適化すればよい
何でもない
22
[P 5471 NOI 2019]ジャンプ
点の方向の区間は辺につながって、最短のショートを求めます
k−d treeは構築図を最適化し,スタックの代わりにk−d treeを用いてk−d treeに弛緩怠惰マーカーを打つ
何でもない
23
B - Good Triple
1つの01列をあげて、区間のメモリが3つの位置で等差数の列になってしかも値の等しい区間の数量を求めます
区間長(ge 9)であれば必ず可能であることが分かりやすいので、左端点を選択し、列挙して区間長の最小値を計算すればよい.
何でもない
24
A - Increasing by Modulo
略
略
簡単すぎる
25
D - Flights for Regular Customers
テーマ叙述
問題解
何でもない
26
F - Ants on a Circle
テーマ叙述
問題解
何でもない
27
Game of Stones
二人で石を取り、二人がある山の上で一度取ったことがある(s={a_1,a_2,cdots,a_n})という式を設定すると、次の式の数(xotin s)となる.誰が勝つか
SGを計算すればよい.
何でもない
28
Three Circuits
1つの図が3つのオーラ戻り路に分解できるかどうかを判断し、各エッジは1つのオーラ戻り路に属するしかない.
問題解
何でもない
29
A Sequence of Permutations
問題解
何でもない
30
問題解
問題解というリンクには、筆者が作った4つの問題が含まれています.テーマの叙述、出所と問題解はすべてあります.
これらの問題のほかにいくつかの修正された試験問題と124の問題があります.