第十届蓝桥杯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;
}