第十屆藍橋杯c++B組省賽部分題目

剛開始想會很糾結怎麼把重複的給去掉，例如1000+1001+18和1001+1000+18。

後來想到3個數有6種排列方式，是以隻要除掉6（A33=6）就可以了。

#include<iostream>
using namespace std;
bool f1(int);
int main(void)
{
	int count = 0;
	for (int i = 1; i < 2019; ++i)
	{
		for (int j = 1; j < 2019; ++j)
		{
			int k = 2019 - i - j;
			if (k < 1)
				continue;
			if (i != j && i != k && j != k)
				if (f1(i) && f1(j) && f1(k))
					++count;
		}
	}
	if (count % 6 != 0)
		cout << "有問題" << endl;
	cout << count / 6 << endl;
	return 0;
}
bool f1(int k)
{
	int remainder = 0;
	while (k > 10)
	{
		remainder = k % 10;
		if (remainder == 2 || remainder == 4)
			return 0;
		k /= 10;
	}
	if (k == 2 || k == 4)
		return 0;
	return 1;
}
           

剛剛回顧省賽題目的時候，看到有人把第三個數也用循環列舉出來，結果運作了十多秒，這個例子告訴我們o(n3)代碼太有風險了，于是我就又打了一遍這個代碼，第三個數用2019減去前兩個數。

剛看到有人把這題做的非常複雜，是以我又來了，準備寫一寫。

我的思路就是：先把輸入的數排好序（剛剛看到有人竟然說最左邊那個就是最小，最右邊就是最大），然後計算每兩個相鄰數之間的差，找出差的最小值即是公差。然後再（max-min）/公差即是答案。這道題好像也完全不關乎什麼算法，國中數學就夠用吧。。是以我感覺省賽就是跟數學關系比較多。

#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
	int a[10000];		//還不是很熟悉容器，以後改
	int N = 0;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> a[i];
	}
	sort(a, a + N);
	int k = a[1] - a[0];	//k是公差
	for (int i = 0; i < N-1; ++i)
	{
		if (a[i + 1] - a[i] < k)
			k = a[i + 1] - a[i];
	}
	//cout << (a[N - 1] - a[0]) / k;	檢驗過後發現比答案小1，數學功底不夠好
	cout << (a[N - 1] - a[0]) / k + 1;
	return 0;
}