【ブルーブリッジ】2020年第11回ブルーブリッジカップC/C++B組校内模擬試合のプログラミングテーマとやり方の参考

シミュレーションの後に書いた内容はプログラミングのテーマと個人の答えのために書いたやり方は個人を代表しているだけで、理解、複雑度などの要素が間違っている可能性があります.参考にしてください.皆さんの交流と勉強を歓迎して、解法を討論します!
第5題の元音補音問題説明小明はhelloのような単語に非常に興味を持っており、この単語はちょうど4つのセグメントに分けることができ、第1セグメントは1つ以上の補音アルファベットからなり、第2セグメントは1つ以上の元音アルファベットからなり、第3セグメントは1つ以上の補音アルファベットからなり、第4セグメントは1つ以上の元音アルファベットからなる.単語を1つ与えて、この単語もこの単語かどうかを判断して、yesを出力してください.そうしないとnoを出力してください.母音アルファベットはa,e,i,o,uの5つを含み,その他はいずれも補音アルファベットである.入力フォーマットは、小文字の英字のみを含む単語を含む行を入力します.出力フォーマットは答えを出力します.yesかnoです.サンプル入力lanqiaoサンプル出力yesサンプル入力worldサンプル出力no評価例規模と約束すべての評価例に対して、単語中のアルファベット個数は100を超えない.構想:文字列は[子音][母音][子音][母音]の4つのwhileを区別して循環して1つのwhileを歩き終わって4つのブロックを歩かなければならなくて、しかも文字列の末尾まで歩かなければならなくて要求に合致しません:1)文字列の1つ目は母音2)前の3つのブロックを歩く時すでに文字列の末尾に着きました3)4つのブロックを歩き終わっても文字列の末尾まで行かなかった

#include
#include
using namespace std;
bool letter(string str)
{
	string yuan = "aeiou";
	if (yuan.find(str[0]) != yuan.npos)
		return false;
	int i = 0;
	while (i < str.size() && yuan.find(str[i]) == yuan.npos)
		i++;
	if (i == str.size())
		return false;
	while (i < str.size() && yuan.find(str[i]) != yuan.npos)
		i++;
	if (i == str.size())
		return false;
	while (i < str.size() && yuan.find(str[i]) == yuan.npos)
		i++;
	if (i == str.size())
		return false;
	while (i < str.size() && yuan.find(str[i]) != yuan.npos)
		i++;
	if (i == str.size())
		return true;
	return false;
}
int main()
{
	string str;
	while (cin >> str)
	{
		cout << (letter(str) ? "yes" : "no") << endl;
	}
	return 0;
}

6番目の問題の数ビット増加逆シーケンス問題は、正の整数を記述し、任意の数ビットが右隣の数ビットより大きくなければ、1つの数ビット増加数と呼ばれ、例えば1135は1つの数ビット増加数であり、1024は1つの数ビット増加数ではない.正の整数nを与えて、整数の1からnの中で何個の数桁の増加する数がありますか?入力フォーマット入力の最初の行には整数nが含まれます.出力フォーマット出力行には、答えを表す整数が含まれます.サンプル入力30サンプル出力26評価サンプル規模と40%の評価サンプルについて、1<=n<=1000と約束した.80%の評価例では、1<=n<=100000であった.すべての評価例について、1<=n<=1000000である.考え方:ビット単位の比較数ビットの増加

#include
using namespace std;
bool up(int n)
{
	int t = 9;
	while(n)
	{
		if(n%10>t)
			return false;
		t = n%10;
		n /= 10;
	}
	return true;
}
int main()
{
	int n,i,count = 0;
	while (cin >> n)
	{
		for(i = 1;i<=n;i++)
		{
			if(up(i))
				count++;
		}
		cout << count << endl;
	}
	return 0;
}

第7題増分三元グループの中心問題は、数列a[1],a[2],...,a[n]において、下付きi,j,kが0を満たすために与えられた数列を記述する.入力フォーマット入力の最初の行には整数nが含まれます.2行目はn個の整数a[1],a[2],...,a[n]を含み,隣接する整数間はスペースで区切られ,与えられた数列を表す.出力フォーマット出力行には、答えを表す整数が含まれます.サンプル入力5 1 2 5 3 5サンプル出力2サンプルは、a[2]およびa[4]が三元群の中心である可能性があることを示す.評価例の規模は、50%の評価例に対して、2<=n<=100、0<=数列の数<=1000と約束されている.すべての評価例について、2<=n<=1000、0<=数列の数<=10000である.構想:暴力の前探しは現在のビットより小さいと後探しは現在のビットより大きい使用例の規模が大きい場合、時間がタイムアウトする可能性がある最適化:動的計画で最長上昇サブシーケンスと逆順最長下降サブシーケンスの同一位置最長上昇サブシーケンス長と逆順最長下降サブシーケンス長がいずれも1より大きい場合カウント+1

#include
#include
using namespace std;
int main()
{
	int n,i,t,count = 0;
	while (cin >> n)
	{
		vector<int> v(n);
		for(i = 0;i<n;i++)
			cin>>v[i];
		for(i = 1;i<n-1;i++)
		{
			int three = 0;
			for(t = 0;t<i;t++)
			{
				if(v[t]<v[i])
				{
					three++;
					break;
				}
			}
			for(t = i+1;t<n;t++)
			{
				if(v[t]>v[i])
				{
					three++;
					break;
				}
			}
			if(three == 2)
			{
				count++;
			}
		}
		cout << count << endl;
	}
	return 0;
}

第8題の長草問題は明ちゃんに空き地があることを説明して、彼はこの空き地をn行m列の小さい塊に分けて、各行と各列の長さはすべて1です.明ちゃんはその中のいくつかの小さな空き地を選んで、草を植えて、他の小さな塊は依然として空き地を維持しています.これらの草は成長が速く、毎月、草は外に少し生えています.もし小さな塊が草を植えたら、自分の上、下、左、右の4つの小さな空き地に広がり、この4つの小さな空き地は草のある小さな塊になります.明ちゃんに、kヶ月後の空き地に草があるところを教えてください.入力フォーマット入力の最初の行は、2つの整数n,mを含む.次にn行、各行にm文字が含まれ、初期の空き地状態を表し、文字間にスペースがない.小数点であれば空き地、アルファベットgであれば草を植えたことを表す.次に整数kを含む.出力フォーマットはn行を出力し、各行にm文字を含み、kヶ月後の空き地の状態を表す.小数点であれば空き地、アルファベットgであれば草が生えていることを示します.サンプル入力4 5.g......g......2サンプル出力ggg.gggg. ggggg .ggg. 評価例の規模と約束は30%の評価例に対して,2<=n,m<=20であった.評価例の70%に対して2<=n,m<=100であった.すべての評価例について、2<=n、m<=1000、1<=k<=1000である.構想:空き地の配列を遍歴して、暴力は芝生の周囲の空き地を変えて芝生の時間の複雑度n^3で、用例の規模が大きい時、時間がタイムアウトするかもしれません

#include
#include
using namespace std;
int main()
{
	int m,n,i,j,k;
	while (cin >> n >> m)
	{
		vector< vector<char> > v(n,vector<char>(m));
		for(i = 0;i<n;i++)
			for(j = 0;j<m;j++)
				cin >> v[i][j];
		cin>>k;
		while(k--)
		{
			vector< vector<char> > t = v;
			for(i = 0;i<n;i++)
			{
				for(j = 0;j<m;j++)
				{
					if(v[i][j] == 'g')
					{
						if(i-1>=0)
							t[i-1][j] = 'g';
						if(i+1<n)
							t[i+1][j] = 'g';
						if(j-1>=0)
							t[i][j-1] = 'g';
						if(j+1<m)
							t[i][j+1] = 'g';
					}
				}	
			}
			v = t;
		}
		for(i = 0;i<n;i++)
		{
			for(j = 0;j<m;j++)
				cout << v[i][j];
			cout << endl;
		}
	}
	return 0;
}

第9題シーケンス数問題説明明さんは、以下の条件を満たす正の整数シーケンスの数を知りたいと思っています.第1項はnである.　　2. 第2項はnを超えない.　　3. 3番目の項目から、各項目は前の2つの項目の差の絶対値より小さい.与えられたnに対して、条件を満たすシーケンスがどれだけあるかを計算してください.入力フォーマット入力行には整数nが含まれます.出力フォーマットは、答えを表す整数を出力します.答えは大きいかもしれませんが、答えを10000で割った余りを出力してください.サンプル入力4サンプル出力7サンプル説明以下は条件を満たすシーケンスである:4 1 4 1 4 1 4 2 4 4 2 1 4 4 4 4 4評価用例規模と約束20%評価用例に対して、1<=n<=5;50%の評価例について、1<=n<=10;80%の評価例について、1<=n<=100;すべての評価例について、1<=n<=1000である.考え方:dfsは後ろに行けばいい後続の再帰が多すぎて演算ができない結果、私は30まで走って50%を超えることができるサンプルを走ることができませんでした.

#include
using namespace std;
void dfs(int n,int &count,int a,int b)
{
	count %= 10000;
	int i,t = (a-b)>0 ? (a-b) : (b-a);
	if(t <2){		
		return;
	}
	for(i = 1;i<t;i++)
	{
		count++;
		dfs(n+1,count,i,a);
	}
	return;
}
int main()
{
	int m,n,i,j,k;
	while (cin >> n)
	{
		int count = 0;
		for(i = 1;i<=n;i++)
		{
			count++;
			dfs(1,count,i,n);
		}
		cout<<count<<endl;
	}
	return 0;
}

第10題選番組問題説明明ちゃんはパーティーを組織して、全部でnつの番組を準備しました.そしてパーティーの時間は限られていて、彼は最終的にその中のm番組を選ぶしかありません.このn番组は明ちゃんが想定した顺番で与えられたもので、顺番は変えられない.明ちゃんは、観客の夜の好きさと前のいくつかの番組の美しさには非常に大きな関係があることを発見しました.彼は選んだ最初の番組ができるだけきれいになることを望んでいます.その前提の下で、2番目の番組ができるだけきれいになることを望んでいます.明ちゃんは各番組にきれいな値を定義しました.明ちゃんがm番組を選んで、彼の要求を満たすのを助けてください.入力フォーマット入力の第1行は、番組の数と選択する数を表す2つの整数n,mを含む.2行目はn個の整数を含み,各番組の見栄え値の順である.出力フォーマット出力1行にm個の整数を含み、選択した番組の見栄え値である.サンプル入力5 3 3 1 2 5 4サンプル出力3 5 4サンプル説明第1,4,5番組を選択した.評価用例の規模と約束は30%の評価用例に対して、1<=n<=20である.60%の評価例について、1<=n<=100;全ての評価例について、1<=n<=100000、0<=番組の見栄え<=100000である.構想:この問題の説明はあまり明確ではなく、サンプルが欠けて問題を検証している.テーマについて(第1番组はできるだけきれいにして、その前提の下で第2番组はできるだけきれいにして、顺次類推します)私は2つの考えがあります第1番组はすべてできるだけ大きくて、それでは小さいのを取り除いていいで、顺位は前のm个の大きい数を取ってサンプルの配列の3 1 1 2 2 5 3によって顺位した后の1 2 3 5第2番组は毎回番组の数を満たすことができる情况の下で最大のサンプルの数を选びますグループ3 1 1 2 5 3 0-2から最大3 1-3から最大5 4から最大3の2つの解法でサンプル回答が得られた3 5評価不足のためデータ規模が大きく影響する可能性がある

#include
#include
#include
using namespace std;
int main()
{
	int m,n,i;
	while (cin >> n >> m)
	{
		vector<int> v(n);
		for(i = 0;i<n;i++)
			cin>>v[i];
		vector<int> t(v);
		sort(t.begin(),t.end());
		vector<int>::iterator it = v.begin();
		for(i = 0;i<n-m;i++)
		{
			while(it!=v.end())
			{
				if(t[i] == *it)
					break;
				it++;
			}
			v.erase(it);
		}
		for(i = 0;i<m-1;i++)
			cout<<v[i]<<" ";
		cout<<v[m-1]<<endl;
	}
	return 0;
}

int main()
{
	int m, n, i;
	while (cin >> n >> m)
	{
		vector<int> v(n);
		vector<int> res(m);
		int j = 0;
		for (i = 0; i < n; i++)
			cin >> v[i];
		vector<int>::iterator it = v.begin();
		while (m)
		{
			vector<int> t(it, v.end() - m+1);
			sort(t.begin(), t.end());
			res[j++] = t[t.size() - 1];
			while (it != v.end())
			{
				if (t[t.size() - 1] == *it)
					break;
				it++;
			}
			if (it != v.end())
				it++;
			m--;
		}
		for (i = 0; i < res.size()-1; i++)
			cout << res[i] << " ";
		cout << res[res.size() - 1] << endl;
	}
	return 0;
}