2019第10回ブルーブリッジカップ大会青少年創意プログラミング省試合C++組試験問題解析

1、水下探知機水下探知機は湖に潜入して任意の水深で科学的に探求することができる.湖水の最大深さはhメートルであり、すなわち湖底での水面までの距離であり、0<=h<=100である.プローブの最初の水下深さはsメートルで、0<=s<=100である.プローブが水面にない(現在の深さが0より大きい)場合、各u命令は1メートル浮上させることができ、プローブが水面にある場合、u命令は無効である;プローブが湖底にない場合(現在の深さがhより小さい)場合、各d命令は1メートル沈下させることができ、プローブが湖底にある場合、d命令は無効である.無効な命令が実行されると、プローブは何の操作もせずに次の命令を実行し続ける.プログラミング実装:所与のh、s、および命令シーケンスに従って(文字u、dからなる文字列で、長さが100を超えない)完全な命令シーケンスを実行した後、プローブの水中深さを求める.入力:第1行:hとs、スペースで区切られる.0<=s<=h<=100第2行:長さが100を超えない命令文字列、列にはアルファベットuまたはd出力のみが含まれる:プローブの命令実行後の水中深さを表す数字.サンプル入力:9 1 uduuddサンプル出力:2サンプルデータ分析:考察知識:基礎文法、文字列、サイクル、条件判断参照コード:

#include 
#include 
using namespace std;
int main(int argc, char *argv[])
{
	int h,s;
	scanf("%d %d",&h,&s);
 	char n[101];
 	scanf("%c",n);
 	int l=strlen(n);
 	for(int i=0;i0)s--;
	 	else if(n[i]=='d')
	 		if(s

2、猫は魚を食べます明らかに家は1番の駅から出発して、車で旅行に行って、全部でnつの駅を通って、順番に2、3......nです.大好きな子猫を連れてきたのに、各サイトでは子猫に魚を1匹提供して食事をします(1番乗り場を含む).1番乗り場以外は1番乗り場で買った魚しか食べられません.他の乗り場では現地で買った魚も食べられますし、以前通った乗り場で車載冷蔵庫に預けた魚も買えます.しかし車載冷蔵庫で消費した電気エネルギーはガソリンから来ているので、魚ごとに冷蔵庫で次の乗り場に保存する費用は各駅のガソリン価格と関係があります.問題を簡略化するために、私は私たちは約束した:(1)車がある駅を出たとき、ガソリンタンクの中にはこの駅のガソリンが入ったばかりだった.(2)車載冷蔵庫は道中必要なすべての魚を収容することができる.すなわち、1匹あたりの費用には購入時の費用も含まれ、冷蔵庫で魚を保存する費用も含まれる.プログラミングは実現する:子猫が魚を食べる総代価を下げるために、事前にインターネットでこのnサイトの魚の価格とガソリンの価格を調べたのに.それによって各サイトが1匹の魚を買う費用とそのサイトから下までを算出する1駅に1匹の魚を冷蔵庫で保存する費用.この道で猫が魚を食べる最小の総費用を計算してもらえますか?入力:最初の行:サイト数n,1次のn行:行ごとに2つのスペースで区切られた正の整数.出力:最小総費用、正の整数です.サンプル入力:5 6 3 7 1 3 8 3 9 5サンプル出力:29参照コード:

#include 
#include 
using namespace std;
int m[100][3];
int main(int argc, char *argv[])
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&m[i][1],&m[i][2]);
	int sum=0,min=99999;
	for(int i=1;i<=n;i++){
		if(min>m[i][1]) min=m[i][1];
		sum+=min;
		min+=m[i][2];
	}
	printf("%d
",sum);
	return 0;
}

3、ベストブランドn個の審査員を選出して投票し、m個の商品の中でベストブランドを選出する.選考は多輪淘汰制を採用し、すなわち、毎回投票し、最も得票が少なかった候補ブランドを淘汰する(得票が並んで最も少なかったブランドを一緒に淘汰する).このように1ラウンドで淘汰され、最後に1つのブランドしか残っていなければ選考に成功する.しかし、ある投票で当時淘汰されなかったすべての候補ブランドが(2つ以上のブランド)ともに最も票を得たのは、選考に失敗したということです.もし選考に成功したら、当選ブランド番号を出力します.そうでなければ、最終選考時の唯一の票数の反対数を出力します.選考の流れの中で、各審査員の態度は1つの序列で表すことができます.例えば、m=5の場合、ある審査員の選考態度の序列は:3、5、1、2、4で、このことを表します審査員:優先的に3番を投げ、3番が淘汰された場合は5番を投げ、3と5が淘汰された場合は1を投げ、3、5、1が淘汰された場合は2を投げ、4番しか残っていない場合は4番ブランドの票を投じます.票の序列には棄権を表すことができ、0で表すことができる.例えば、m=5の場合、ある審査員の選考態度の序列は:3、5、0である場合、その審査員:3番を優先的に投げ、3番が淘汰された場合は5番を投げ、その他の場合はいかなるブランドの票も投げない.プログラミングの実現:プログラムを作って、各ラウンドの投票の過程をシミュレートして、選考結果を得てください.入力:1行目:m(0出力:選考結果.サンプル1入力:3 4 123 213,132,210サンプル1出力:1サンプル2入力:3 4 321,213,231サンプル2出力:-2サンプルデータ分析:考察知識:文字列、バケツソート、シミュレーションアルゴリズム参照コード:

#include
#include
#include
#include
using namespace std;
const int M=15,N=1010;
int g[N][M];//         
int piao[M];//    
int st[M];//      
bool success=true;
int last_piaoshu;
int last_pinpai; 
int n,m;//n    m   
void pingxuan()
{
	while(1){
		memset(piao,0,sizeof(piao));
		for(int i=1;i<=n;i++)
			for(int j=1;jmax && !st[i])max=piao[i];
		}
		if(max>min){//           
			for(int i=1;i>m>>n;
	for(int i=1;i<=n;i++){
		string str;
		cin>>str;
		for(int j=0;j

4、最大买い物优遇恵さんはスーパーがセール中だと闻いて、最大优遇の买い物计画を立てます.恵ちゃんの体力はw単位の重量を上げることができ、V単位の体積を入れることができるショッピングバッグもあり、各割引商品の重量、体積、この商品の実際の割引金額を詳しく知っています.彼女は自分の体力の限界とショッピングバッグの容積の限界の中で、できるだけ多くのショッピングの優遇を受けたいと思っています.スーパーではこれらの割引商品はそれぞれ1つしか購入できないと規定されています.プログラミング実装:プログラムを作成して、商品を購入する計画を立てて、小恵が得ることができる最大の優遇金額と実際に購入すべき各商品の番号を求めてください.入力:1行目:w、v、n(nは商品の種類数)の順で、すべての数値は100を超えない正の整数次のn行:各行に3つの整数があり、ある商品の重量、体積、譲渡金額の順で、数値間はスペースで分かれています.すべての数値は100を超えない正の整数出力:1行目:小恵が得ることができる最大譲渡金額2行目:小から大に並ぶ商品番号の順で、番号は1から、番号間はスペースで分かれています.2行目の出力シーケンスが一意でない場合は、その最小辞書シーケンスが出力されます.サンプル入力:10 9 4 8 3 6 5 4 3 7 7 4サンプル出力:9 2 4サンプルデータ分析:考察知識:ダイナミックプランニング、2次元費用のリュック問題、01リュック問題に加えて費用次元状態遷移方程式:yh[i][j][k]=max(yh[i-1][j][k],yh[i-1][j-w[i]][k-v[i]+n[i])古典01リュック問題解(https://blog.csdn.net/qq_38410730/article/details/81667885)
全体の考え方:1.まず後ろから前へ押して、最大の利益を得て、具体的な方案(最短の問題を真似て、後ろから前へ)を形成します.2.更に前から後ろへ押して、具体的な方案の辞書の順序の参考コードを得ます:

#include
#include
#include
using namespace std;
const int N=110;
int w[N],v[N],p[N];
int f[N][N][N];
int main()
{
	//freopen("shopping.in","r",stdin);
	int W,V,n;
	cin>>W>>V>>n;
	for(int i=1;i<=n;i++) cin>>w[i]>>v[i]>>p[i];
	//    ，      
	for(int i=n;i>=1;i--){
		for(int j=0;j<=W;j++)
			for(int k=0;k<=V;k++){
				f[i][j][k]=f[i+1][j][k];
				if(j>=w[i] && k>=v[i])
					f[i][j][k]=max(f[i][j][k],f[i+1][j-w[i]][k-v[i]]+p[i]);
				}
	}
	cout<=w[i] && k>=v[i] && f[i][j][k]==f[i+1][j-w[i]][k-v[i]]+p[i]){
			cout<

5、迷宮は1つのn行m列の文字アレイを1つの迷宮と見なし、迷宮はL、Q、B、Sの中の大文字(ブルーブリッジカップの中国語ピンインの頭文字).最初は、任意の「L」文字から隣の「Q」文字に移動し、それから「Q」文字から隣の「B」文字に移動し、それから「B」文字から隣の「S」文字に移動することができます.......そうすれば、あなたは「LQBS」を歩いたことがあります.文字列.次に、この「S」のアルファベットから、隣接する「L」のアルファベットに移動することもできます.......上記の動作を繰り返すと、「LQBS」のシーケンスを絶えず通過することができます.隣接とは、上、下、左、右の4つの方向のみを含み、L->Q、Q->B、B->S、S->Lのみであることに注意してください.選択の出発点が異なるため、迷路の中で何度も「LQBS」を歩いたり、限られた「LQBS」を歩いたり、一度も歩けない可能性があると想像できる.プログラミング実装:プログラムを作成して、与えられた迷路の中で、私たちは最大何回「LQBS」を歩くことができますか?入力:最初の行:正の整数n,m、迷宮の規模がn行m列であることを示し、0次のn行:各行m個の題意に合致するアルファベット、アルファベット間にスペースがない.出力:整数.すなわち、迷路の中で「LQBS」、出力-1を無制限に通過できれば、出力は「LQBS」の最大回数を通過することができる.サンプル1入力:1 2 LQサンプル1出力:0サンプル2入力:3 LSB QBQ BSLサンプル2出力:-1サンプル3入力:4 BLQB BBQS SBQL QQQサンプル3出力:2サンプルデータ分析:考察知識:検索と回朔筆者の学習者は検索と回朔アルゴリズムを一時的に学んでいないため、循環遍歴類似貧挙アルゴリズムを用いて問題解参考コードを行う:

#include
#include
#include
using namespace std;
const int N=110;
char g[N][N];
int f[N][N];
int n,m;
bool wuxian;
int mstep,step=1;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; 
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<0||xx>n-1||yy<0||yy>m-1)continue;//    
		if((g[x][y]=='L' && g[xx][yy]=='Q')||(g[x][y]=='Q' && g[xx][yy]=='B')||
		(g[x][y]=='B' && g[xx][yy]=='S')||(g[x][y]=='S' && g[xx][yy]=='L')){
			if(f[xx][yy]){
				wuxian=true;
				return ;
			}
			f[xx][yy]=1;
			step++;
			mstep=max(mstep,step);
			dfs(xx,yy);
			f[xx][yy]=0;
			step--;
		} 	
	}
	return ;
} 
int main()
{
	//freopen("LQBS3.in","r",stdin);
	cin>>n>>m;
	for(int i=0;i>g[i];
	for(int i=0;i