2018第9回ブルーブリッジカップ決勝(C++B組)
6776 ワード
北京の大半を回ったけど楽しかったよ
第一題
お札を両替する
x星の紙幣の額面は100元、5元、2元、1元、計4種類しかない.明ちゃんはx星へ旅行に行きました.彼の手には100元のx星貨幣が2枚しかありません.とても不便で、ちょうどx星銀行を通って小銭に両替しました.明ちゃんは少し強迫症で、200元で両替したお札の中の2元の枚数はちょうど1元の枚数の10倍で、残りはもちろん5元です.銀行のスタッフは少し困っていますが、明ちゃんの要求を満たす前提で、少なくとも何枚の紙幣に両替しなければなりませんか.(5元、2元、1元の額面はすべてあって、0ではありません)
問題解
第二題
タイトル:レーザースタイル
x星の盛大な祝日は雰囲気を高めるために、30台の机光器で一列に並び、宇宙に光柱を打ち出す.デバッグをインストールしたところ、なぜか隣接する2台のレーザが同時に開かないことがわかりました!王は、このようなバグが存在する場合、全部で何種類のレーザー効果を出すことができるか知りたいと思っています.
明らかに、3台の機械しかなければ、全部で5種類のスタイルにすることができます.つまり、すべて閉じる(sorry、この時は音がなくて音があって、これも1種類です)1台を開いて、3種類で2台開いて、1種類だけです.
30台はまずいから、王は君に手伝ってもらうしかない.
30台のレーザで形成できるパターン種数を表す整数を提出する必要がある.
問題解
暴力dfsでいいです.lastBulbLightは前のランプが点灯しているかどうかを示します(1 for switch on,0 for switch off)、結果は2178309です.
第三題
タイトル:グレイコード
グレイコードはnビットのバイナリで数を表す.通常のバイナリ表現とは異なり、隣接する2つの数字が1桁しか異なることが要求される.最初と最後の2つの数字も1桁の差しかないことを要求している.
グレイコードを生成するアルゴリズムはたくさんあります.以下は、符号化全0から生成されるのが一般的である.奇数番目の数が発生した場合、現在の数字の最下位位のみを変更(0は1、1は0)偶数番目の数が発生した場合、まず右端の1つを見つけて、左の数字を変更します.このルールで生成された4ビットのグレイコードシーケンスは、0000 0001 0011 0010 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
以下は実装コードで、論理を詳しく分析し、スクライブ部分に欠けているコードを記入します.
注意:スクライブ部分に欠けている内容を記入するだけで、既存のコードや記号を書き写さないでください.
問題解
暴力の解法しか考えられませんでした
具体的には、aと
第四題
タイトル:時計の調整
明ちゃんはハイエンドの大気レベルの電子時計を買った.彼は時間を調整しようとしている.M 78星雲では、時間の計測単位が地球と異なり、M 78星雲の1時間はn分あります.時計には現在の数を1つ追加できるボタンが1つしかないことはよく知られています.分調整の際、現在表示されている数が0であれば、ボタンを押すと1になり、もう一度押すと2になります.現在の数がn-1の場合、1回押すと0になります.強迫症患者として、明ちゃんは必ず時計の時間を合わせなければならない.時計の時間が現在の時間より1多い場合は、n-1回ボタンを押すと正確な時間に戻ります.明ちゃんは、時計にボタンをもう一つ追加して、現在の数をkにすればいいのかと思っています.もしこの+kボタンがあれば、最適な戦略ボタンに従って、任意の分から別の任意の分に変更して、最大何回押すか知りたいと思っています.注意:+kボタンを押すと、kを加えた数字がn-1を超えると、nが型抜きされます.例えば、n=10、k=6の場合、現在時刻が0であると仮定し、+kボタンを2回連続して押すと、2になる.
「入力フォーマット」の1行2つの整数n,kは、問題のような意味を持つ.
「出力フォーマット」行の1つの整数は、最適なポリシーボタンに従って、1つの時間から別の時間に最大何回押すかを示します.
「サンプル入力」5 3
「サンプル出力」2
「サンプル解釈」時間が正しければ0回押します.そうでなければ押す回数と操作系列の関係は以下の通りである:1:+12:+1,+13:+3 4:+3,+1
「データ範囲」30%のデータに対して0第五題
表題:積み木
明ちゃんは積み木にとても興味があります.彼の積み木はみな同じ大きさの正立方体だ.積み木を積む時、明ちゃんはmブロックの積み木を地盤として選び、テーブルの上に一字並べて、真ん中に隙間を残さず、0階と呼ばれています.その後、明ちゃんは上に1階、2階、......、最大n階まで置くことができます.積み木を置くには、3つのルールに従う必要があります.
ルール1:各積み木は、ある積み木の真上に隣接して置かなければならず、その次の積み木と位置合わせしなければならない.ルール2:同じ層の積み木は連続的に並べなければならず、真ん中に隙間を残してはならない.ルール3:明ちゃんが嫌いな位置に積み木を置くことはできません.
その中で、明ちゃんの嫌いな位置はすべて図面に表示されています.図面はn行あり、下から上への行ごとに積み木の第1層から第n層に対応する.各行にm文字があり、文字は'.'である可能性があります.あるいは「X」で、「X」はこの位置が明ちゃんが好きではないことを示しています.今、明ちゃんは積み木を置く案がいくつあるか知りたいと思っています.彼はブルーブリッジカップに参加したあなたを見つけて、この答えを計算してあげました.この答えは大きいかもしれませんが、100000007(十億零七)の型を取った結果に答えるだけです.注意:敷地に何も置かないのも案の一つです.
【入力フォーマット】入力データの1行目には、図面の大きさを示す2つの正の整数nとmがある.次にn行、各行にm文字があり、図面を記述する.各文字は'.'のみ可能です.あるいは「X」.
【出力フォーマット】1000000007型取りの結果を表す整数を出力します.
【サンプル入力1】2 3..X .X.
【サンプル出力1】4
【サンプル説明1】成功した配置は(ここでOは積み木を置くことを示す):
(1) ..X .X.
(2) ..X OX.
(3) O.X OX.
(4) ..X .XO
【サンプル入力2】3 3..X .X. ...
【サンプル出力2】16
【データ規模約定】10%のデータに対して、n=1、m<=30;40%のデータに対して、n<=10、m<=30;100%のデータに対して、n<=100、m<=100である.
第六題
タイトル:行列の合計
多くの筆記試験の面接の試練を経て、明ちゃんはMacrohard会社に入社することに成功した.今日の明ちゃんの任務はこのような表を満たすことです:表にはn行n列があり、行と列の番号はすべて1から計算します.ここで、i行目jの要素の値はgcd(i,j)の二乗であり、gcdは最大公約数を表し、以下はこの表の前4行の前4列である:1 1 1 1 1 1 1 4 1 4 1 9 1 4 16
明ちゃんは突然奇妙な考えを出して、彼はこの表のすべての要素の和を知りたいと思っています.時計が大きすぎるので、彼はコンピュータの力を借りたいと思っています.
「入力フォーマット」の1行1つの正の整数nの意味が問題になります.
「出力フォーマット」は、すべての要素の和を表す1行1つの数です.答えが大きいので、型(10^9+7)(すなわち、十億零七)の結果を出力してください.
「サンプル入力」4
「サンプル出力」48
「データ範囲」は30%のデータに対して、n<=1000は10%のデータが存在し、n=10^5は60%のデータに対して、n<=10^6は100%のデータに対して、n<=10^7
問題解
O(n^2)累積gcdは満点にはならないに違いないが,ここでは数論の知識を用い,具体的な点はEuler関数([1,p)内のpとの相互質量数を求める関数)である.
転載先:https://www.cnblogs.com/ysherlock/p/9126140.html
第一題
お札を両替する
x星の紙幣の額面は100元、5元、2元、1元、計4種類しかない.明ちゃんはx星へ旅行に行きました.彼の手には100元のx星貨幣が2枚しかありません.とても不便で、ちょうどx星銀行を通って小銭に両替しました.明ちゃんは少し強迫症で、200元で両替したお札の中の2元の枚数はちょうど1元の枚数の10倍で、残りはもちろん5元です.銀行のスタッフは少し困っていますが、明ちゃんの要求を満たす前提で、少なくとも何枚の紙幣に両替しなければなりませんか.(5元、2元、1元の額面はすべてあって、0ではありません)
問題解
// xyz 5，2，1 ，
// 5x + 2y + z =200
// y = 10z
// => 5x + 21z = 200
//
// **74**
#include
int main() {
for(int z=1;;z++){
int remain = 200 - z*21;
if(remain%5==0){
std::cout< 第二題
タイトル:レーザースタイル
x星の盛大な祝日は雰囲気を高めるために、30台の机光器で一列に並び、宇宙に光柱を打ち出す.デバッグをインストールしたところ、なぜか隣接する2台のレーザが同時に開かないことがわかりました!王は、このようなバグが存在する場合、全部で何種類のレーザー効果を出すことができるか知りたいと思っています.
明らかに、3台の機械しかなければ、全部で5種類のスタイルにすることができます.つまり、すべて閉じる(sorry、この時は音がなくて音があって、これも1種類です)1台を開いて、3種類で2台開いて、1種類だけです.
30台はまずいから、王は君に手伝ってもらうしかない.
30台のレーザで形成できるパターン種数を表す整数を提出する必要がある.
問題解
暴力dfsでいいです.lastBulbLightは前のランプが点灯しているかどうかを示します(1 for switch on,0 for switch off)、結果は2178309です.
#include
#define SEARCH_DEEPTH 30
unsigned long long solutionCnt = 0;
void dfs(int current,bool lastBulbLight){
if(current==SEARCH_DEEPTH){
solutionCnt++;
return;
}
if(lastBulbLight==0){
dfs(current+1,1);
dfs(current+1,0);
}else{
dfs(current+1,0);
}
}
int main(){
dfs(0,0);
std::cout< 第三題
タイトル:グレイコード
グレイコードはnビットのバイナリで数を表す.通常のバイナリ表現とは異なり、隣接する2つの数字が1桁しか異なることが要求される.最初と最後の2つの数字も1桁の差しかないことを要求している.
グレイコードを生成するアルゴリズムはたくさんあります.以下は、符号化全0から生成されるのが一般的である.奇数番目の数が発生した場合、現在の数字の最下位位のみを変更(0は1、1は0)偶数番目の数が発生した場合、まず右端の1つを見つけて、左の数字を変更します.このルールで生成された4ビットのグレイコードシーケンスは、0000 0001 0011 0010 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
以下は実装コードで、論理を詳しく分析し、スクライブ部分に欠けているコードを記入します.
#include
void show(int a,int n)
{
int i;
int msk = 1;
for(i=0; i> 1;
}
printf("
");
}
void f(int n)
{
int i;
int num = 1;
for(i=0; i 注意:スクライブ部分に欠けている内容を記入するだけで、既存のコードや記号を書き写さないでください.
問題解
暴力の解法しか考えられませんでした
(a&1)?((a&2)?(a-2):(a+2)):((a&2)?((a&4)?(a-4):(a+4)):((a&4)?((a&8)?(a-8):(a+8)):/*impossible*/a))具体的には、aと
0001、0010、0100、1000は最も右側の1の位置を取り、それからその左側のビットを取得し、1が0に反転すると減少し、そうでなければ更新を加える:他の人の問題解を見て突然思い出し、木状配列lowbit(x)は最も右側の1を取得し、それから左に1ビット移動して現在の値と異なるか、直接結果を出すことができるa^((a&(-a))<<1)第四題
タイトル:時計の調整
明ちゃんはハイエンドの大気レベルの電子時計を買った.彼は時間を調整しようとしている.M 78星雲では、時間の計測単位が地球と異なり、M 78星雲の1時間はn分あります.時計には現在の数を1つ追加できるボタンが1つしかないことはよく知られています.分調整の際、現在表示されている数が0であれば、ボタンを押すと1になり、もう一度押すと2になります.現在の数がn-1の場合、1回押すと0になります.強迫症患者として、明ちゃんは必ず時計の時間を合わせなければならない.時計の時間が現在の時間より1多い場合は、n-1回ボタンを押すと正確な時間に戻ります.明ちゃんは、時計にボタンをもう一つ追加して、現在の数をkにすればいいのかと思っています.もしこの+kボタンがあれば、最適な戦略ボタンに従って、任意の分から別の任意の分に変更して、最大何回押すか知りたいと思っています.注意:+kボタンを押すと、kを加えた数字がn-1を超えると、nが型抜きされます.例えば、n=10、k=6の場合、現在時刻が0であると仮定し、+kボタンを2回連続して押すと、2になる.
「入力フォーマット」の1行2つの整数n,kは、問題のような意味を持つ.
「出力フォーマット」行の1つの整数は、最適なポリシーボタンに従って、1つの時間から別の時間に最大何回押すかを示します.
「サンプル入力」5 3
「サンプル出力」2
「サンプル解釈」時間が正しければ0回押します.そうでなければ押す回数と操作系列の関係は以下の通りである:1:+12:+1,+13:+3 4:+3,+1
「データ範囲」30%のデータに対して0
表題:積み木
明ちゃんは積み木にとても興味があります.彼の積み木はみな同じ大きさの正立方体だ.積み木を積む時、明ちゃんはmブロックの積み木を地盤として選び、テーブルの上に一字並べて、真ん中に隙間を残さず、0階と呼ばれています.その後、明ちゃんは上に1階、2階、......、最大n階まで置くことができます.積み木を置くには、3つのルールに従う必要があります.
ルール1:各積み木は、ある積み木の真上に隣接して置かなければならず、その次の積み木と位置合わせしなければならない.ルール2:同じ層の積み木は連続的に並べなければならず、真ん中に隙間を残してはならない.ルール3:明ちゃんが嫌いな位置に積み木を置くことはできません.
その中で、明ちゃんの嫌いな位置はすべて図面に表示されています.図面はn行あり、下から上への行ごとに積み木の第1層から第n層に対応する.各行にm文字があり、文字は'.'である可能性があります.あるいは「X」で、「X」はこの位置が明ちゃんが好きではないことを示しています.今、明ちゃんは積み木を置く案がいくつあるか知りたいと思っています.彼はブルーブリッジカップに参加したあなたを見つけて、この答えを計算してあげました.この答えは大きいかもしれませんが、100000007(十億零七)の型を取った結果に答えるだけです.注意:敷地に何も置かないのも案の一つです.
【入力フォーマット】入力データの1行目には、図面の大きさを示す2つの正の整数nとmがある.次にn行、各行にm文字があり、図面を記述する.各文字は'.'のみ可能です.あるいは「X」.
【出力フォーマット】1000000007型取りの結果を表す整数を出力します.
【サンプル入力1】2 3..X .X.
【サンプル出力1】4
【サンプル説明1】成功した配置は(ここでOは積み木を置くことを示す):
(1) ..X .X.
(2) ..X OX.
(3) O.X OX.
(4) ..X .XO
【サンプル入力2】3 3..X .X. ...
【サンプル出力2】16
【データ規模約定】10%のデータに対して、n=1、m<=30;40%のデータに対して、n<=10、m<=30;100%のデータに対して、n<=100、m<=100である.
第六題
タイトル:行列の合計
多くの筆記試験の面接の試練を経て、明ちゃんはMacrohard会社に入社することに成功した.今日の明ちゃんの任務はこのような表を満たすことです:表にはn行n列があり、行と列の番号はすべて1から計算します.ここで、i行目jの要素の値はgcd(i,j)の二乗であり、gcdは最大公約数を表し、以下はこの表の前4行の前4列である:1 1 1 1 1 1 1 4 1 4 1 9 1 4 16
明ちゃんは突然奇妙な考えを出して、彼はこの表のすべての要素の和を知りたいと思っています.時計が大きすぎるので、彼はコンピュータの力を借りたいと思っています.
「入力フォーマット」の1行1つの正の整数nの意味が問題になります.
「出力フォーマット」は、すべての要素の和を表す1行1つの数です.答えが大きいので、型(10^9+7)(すなわち、十億零七)の結果を出力してください.
「サンプル入力」4
「サンプル出力」48
「データ範囲」は30%のデータに対して、n<=1000は10%のデータが存在し、n=10^5は60%のデータに対して、n<=10^6は100%のデータに対して、n<=10^7
問題解
O(n^2)累積gcdは満点にはならないに違いないが,ここでは数論の知識を用い,具体的な点はEuler関数([1,p)内のpとの相互質量数を求める関数)である.
#include
#define MAX 10000005
#define MOD_VALUE 1000000007
bool visit[MAX];
unsigned long long prime[MAX];
int primeCnt = 0;
unsigned long long phi[MAX];
unsigned long long sum[MAX];
// +
void eulerFilter(){
phi[1] = 1;
for(int i=2;i<=MAX;i++){
if(!visit[i]){
phi[i] = i-1;
prime[++primeCnt] = i;
}
for(int k=1;k<=primeCnt;k++){
unsigned long long currentPrime = prime[k];
if(i*currentPrime > MAX){
break;
}
visit[i*currentPrime] = true;
if(i % currentPrime == 0){
phi[i* currentPrime] = phi[i] * currentPrime;
break;
}else{
phi[i* currentPrime] = phi[i] * phi[currentPrime];
}
}
}
sum[1] = phi[1];
for(int i=2;i>n;
eulerFilter();
unsigned long long result = 0;
for(int i=1;i<=n;i++){
result = (result+ sum[n/i]*i%MOD_VALUE*i%MOD_VALUE)%MOD_VALUE;
}
std::cout< 転載先:https://www.cnblogs.com/ysherlock/p/9126140.html