第十五届蓝桥杯C++B组省赛总结

A 握手问题

简单模拟，答案为：1204 5pts

B 小球反弹

数学，最重要的一点，不考虑反弹，一直让小球走，直到达到一个顶点，它就会反弹回去。
所以问题就变成了扩展这些方块，直到满足小球的角度，让小球能达到另一个顶点。
\(233333 \times 15 a= 343720 \times 17b\)
解出来 a 和 b就知道我们要延长多少块了，这里需要约分，建议使用最大公约数求一下，然后直接用勾股定理，这里用excel很好求。
答案：1100325199.77 5pts

C 好数

暴力可过，时间复杂度 \(O(7\times10^7)\) 10pts

int check(int x)
{
	int cnt = 1;
	while (x)
	{
		int p = x % 10;
		if (cnt % 2) 
		{
			if (p % 2 == 0) return false;
		}
		else 
		{
			if (p % 2 == 1) return false;
		}
		x /= 10;
		cnt++;
	}
	return true;
}

void solve()
{
	cin >> n;	
	int res = 0;
	for (int i = 1; i <= n; i++)
		if (check(i)) res++;
	cout << res;
}

D R格式

高精度+快速幂，但是没必要，5分而已 5pts

// 5分代码
long long n;
double p;
void solve()
{
	cin >> n >> p;
	double res = p * pow(2, n);
	cout << (long long)(res + 0.5);
}

E 宝石组合

好像是分解质因数，比赛时看不出来，直接暴力3循环拿30% 4.5pts
这里的公式可以化简，化简后就没有最小公倍数了，只有最大公约数。

const int N = 100010;
int a[N];
int n;

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int calc(int a, int b, int c)
{
	return gcd(a, c) * gcd(b, c) / gcd(a * b / gcd(a, b), c);
}

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	
	int res = 0;
	int maxa, maxb, maxc;
	for (int i = 1; i <= n - 2; i++)
		for (int j = i + 1; j <= n - 1; j++)
			for (int k = i + 2; k <= n; k++)
			{
				if (res < calc(a[i], a[j], a[k]) && i != j && j != k && i != k)
				{
					maxa = a[i];
					maxb = a[j];
					maxc = a[k];
					res = calc(a[i], a[j], a[k]);
				}
			}
	cout << maxa << ' ' << maxb << ' ' << maxc;
}

F 数字接龙

看数据范围，一眼暴力dfs
dfs的条件很多，很多细节，比赛时写的代码在民间测试只过了60%不知道哪里错了 8pts

const int N = 15;

int g[N][N], dist[N][N];
bool st[N][N];
int n, k;

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

bool dfs(int x, int y, int op, int cnt)
{
	if (x == n && y == n && cnt == n * n)
	{
		return true;
	}
	
	for (int i = 0; i < 8; i++)
	{
		int a = dx[i] + x, b = dy[i] + y, c = (op + 1) % k;
		if (a < 1 || a > n || b < 1 || b > n) continue;
		if (st[a][b]) continue;
		if (g[a][b] != c) continue;
		if (a + b < x + y) continue;
		
		st[a][b] = true;
		dist[x][y] = i;
		if (dfs(a, b, c, cnt + 1)) return true;
		st[a][b] = false;
	}
	return false;
}

void solve()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> g[i][j];
	
	st[1][1] = true;
	if (!dfs(1, 1, 0, 1))
	{
		cout << -1 << endl;
		return;
	}
	
	int i = 1, j = 1;
	while (!(i == n && j == n))
	{
		int p = dist[i][j];
		cout << p;
		i = i + dx[p];
		j = j + dy[p];
	}
}

G 爬山

听说是错题，我用的优先队列在民间数据上测试AC了 20pts

priority_queue<int> heap;
int n, p, q;
void solve()
{
	cin >> n >> p >> q;
	while (n--)
	{
		int x;
		cin >> x;
		heap.push(x);
	}
	while (p --)
	{
		int t = heap.top();
		heap.pop();
		t = sqrt(t);
		heap.push(t);
	}
	while (q--)
	{
		int t = heap.top();
		heap.pop();
		t /= 2;
		heap.push(t);
	}
	int res = 0;
	while (heap.size())
	{
		res += heap.top();
		heap.pop();
	}
	cout << res;
}

H 拔河

看错题了，以为是人必须选完，但是可以有人不选的 0pts