C++ブルーブリッジカップアルゴリズム訓練のK好数
9120 ワード
C++ブルーブリッジカップテーマ解説まとめ(継続更新)
VIP試験問題K好数
リソースの制限
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
自然数NのK進数表現のうち任意の隣接する2桁が隣接する数字でない場合,この数はK好数であると述べる.LビットK進数の中でK良い数の数を求めます.例えばK=4,L=2の場合,すべてのK好数は11,13,20,22,30,31,33の計7個である.この数が多いので、1000000007を型抜きした値を出力してください.
入力フォーマット
入力には、2つの正の整数、KおよびLが含まれます.
出力フォーマット
10,000,000,000,007の型取り後の答えの値を示す整数を出力します.
サンプル入力
4 2
サンプル出力
7
データ規模と約定
30%のデータに対してKL<=106;
50%のデータに対してK<=16,L<=10であった.
100%のデータに対して,1<=K,L<=100であった.
問題を解く構想.
まず意味を理解することが大切ですが、なぜかというと、サンプルの4進2桁、4進はそれぞれ0123で構成されているので、ここで2桁だと0123の配列組合せA 2 4 A_{2}^{4}A 24種の可能性があり,その中の好数については{00,02,03,11,13,20,22,30,31,33}が10個あるが,進数の先頭が0にならないため,00,01,03は無効であるため,答えは7個であることが意味理解である.
以下は構想で、構想の話、きっと単純な法則を探すことを通じて(通って)ことができなくて、比較的にそんなに大きい進数はきっと現実的ではありませんて、例えば50進数、50に対して余剰を取って、0-49の数字、どのように1位を計算して問題になって、ここで私達はテーマのタイプによって、動態の計画の方法を使って処理することができて、まず動態の計画の核心が状態と状態の方程式であることを理解します
ここでは題意に基づいて2次元配列を構築し,dp[l][k],lはビット数,kは進数を表し,私が採用したdp法は前の数の最後のビット数に基づいて再帰を行い,dp[i][j]は長さi,末尾がjの場合の好数を表し,長さi+1の数に対して,長さiの数の後に新しい値n u m∈(0,k−1)numin(0,k−1)num∈(0,k−1)を挿入し,この値を現在の長さiの数の最後の桁数と比較すると,最後の桁数j!=n u m − + 1 j!=num_{-}^{+}1 j!=num−+1であれば良い数であるが、これらのすべての基礎はdp[i][j]に確立されており、前の数が継承した良い数であり、次の長さ+1の数が前者の基礎を継承し、更新され続ける.ここでは状態の変化を数式で表す.
$dp[i][m]=\sum^{j=k-1}_{j=0}dp[i-1][j]$,0からk-1までの各ケースを計算する
詳細:初期化の際に注意しなければならないのは、何進数にかかわらず、誰を最後にしても、長さが1であれば、その良い数は1 である.は最後に0の先頭でない場合を処理しなければならないが、このプロセスは長さが1の場合、0の先頭の数の良い0の数が1の場合があるので、ここでは次にどのように計算しても0の先頭の場合、出力するときに一緒に計算できない がある.
じょうたいず
次に、4 2の入力を例とするフローを示すとともに、dp[l][0]に対して0の先頭からの配列結合数であるため、出力は直感的に解釈できない.
j=0
j=1
j=2
j=3
i=1
1
1
1
1
i=2
0+1+1+1
0+1+1
0+1+1
0+1+1+1
の原因となる
jが0の場合:好数は00,02,03で対応するdp[1][0]=1なので3回加算
jが1の場合:好数は11,13で対応するdp[1][1]=1なので2回加算
jが0の場合:好数は20,22,対応するdp[1][0]=1なので2回加算
jが0の場合:好数は30,31,33,対応するdp[1][0]=1なので3回加算
コードC++
まとめ
私は普段もほんの少しのダイナミックプランニングの基礎知識を知っているだけで、ここでは正直最初は考えられませんでしたが、最初はテーマさえ読めませんでしたが、1日余り魚を触ってもここのdp方法の原理を理解していました.理解の状態方程式に基づいて、それぞれのサブ構造から私たちが必要とする結果を得ました.これがこの問題の解法です.それぞれの長さの良い数は間違いなく(0,k-1)というk類の結果で、このk類の結果を計算し続ける限り、私たちが必要とする答えが得られる.
VIP試験問題K好数
リソースの制限
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
自然数NのK進数表現のうち任意の隣接する2桁が隣接する数字でない場合,この数はK好数であると述べる.LビットK進数の中でK良い数の数を求めます.例えばK=4,L=2の場合,すべてのK好数は11,13,20,22,30,31,33の計7個である.この数が多いので、1000000007を型抜きした値を出力してください.
入力フォーマット
入力には、2つの正の整数、KおよびLが含まれます.
出力フォーマット
10,000,000,000,007の型取り後の答えの値を示す整数を出力します.
サンプル入力
4 2
サンプル出力
7
データ規模と約定
30%のデータに対してKL<=106;
50%のデータに対してK<=16,L<=10であった.
100%のデータに対して,1<=K,L<=100であった.
問題を解く構想.
まず意味を理解することが大切ですが、なぜかというと、サンプルの4進2桁、4進はそれぞれ0123で構成されているので、ここで2桁だと0123の配列組合せA 2 4 A_{2}^{4}A 24種の可能性があり,その中の好数については{00,02,03,11,13,20,22,30,31,33}が10個あるが,進数の先頭が0にならないため,00,01,03は無効であるため,答えは7個であることが意味理解である.
以下は構想で、構想の話、きっと単純な法則を探すことを通じて(通って)ことができなくて、比較的にそんなに大きい進数はきっと現実的ではありませんて、例えば50進数、50に対して余剰を取って、0-49の数字、どのように1位を計算して問題になって、ここで私達はテーマのタイプによって、動態の計画の方法を使って処理することができて、まず動態の計画の核心が状態と状態の方程式であることを理解します
ここでは題意に基づいて2次元配列を構築し,dp[l][k],lはビット数,kは進数を表し,私が採用したdp法は前の数の最後のビット数に基づいて再帰を行い,dp[i][j]は長さi,末尾がjの場合の好数を表し,長さi+1の数に対して,長さiの数の後に新しい値n u m∈(0,k−1)numin(0,k−1)num∈(0,k−1)を挿入し,この値を現在の長さiの数の最後の桁数と比較すると,最後の桁数j!=n u m − + 1 j!=num_{-}^{+}1 j!=num−+1であれば良い数であるが、これらのすべての基礎はdp[i][j]に確立されており、前の数が継承した良い数であり、次の長さ+1の数が前者の基礎を継承し、更新され続ける.ここでは状態の変化を数式で表す.
$dp[i][m]=\sum^{j=k-1}_{j=0}dp[i-1][j]$,0からk-1までの各ケースを計算する
詳細:
じょうたいず
次に、4 2の入力を例とするフローを示すとともに、dp[l][0]に対して0の先頭からの配列結合数であるため、出力は直感的に解釈できない.
j=0
j=1
j=2
j=3
i=1
1
1
1
1
i=2
0+1+1+1
0+1+1
0+1+1
0+1+1+1
の原因となる
jが0の場合:好数は00,02,03で対応するdp[1][0]=1なので3回加算
jが1の場合:好数は11,13で対応するdp[1][1]=1なので2回加算
jが0の場合:好数は20,22,対応するdp[1][0]=1なので2回加算
jが0の場合:好数は30,31,33,対応するdp[1][0]=1なので3回加算
コードC++
#include
// cout<
// }
// cout<
// }
cout<<res;
return 0;
}
まとめ
私は普段もほんの少しのダイナミックプランニングの基礎知識を知っているだけで、ここでは正直最初は考えられませんでしたが、最初はテーマさえ読めませんでしたが、1日余り魚を触ってもここのdp方法の原理を理解していました.理解の状態方程式に基づいて、それぞれのサブ構造から私たちが必要とする結果を得ました.これがこの問題の解法です.それぞれの長さの良い数は間違いなく(0,k-1)というk類の結果で、このk類の結果を計算し続ける限り、私たちが必要とする答えが得られる.