【蓝桥杯】第十五届C++B组省赛

试题A：握手问题

我和其他49个人握手，第二个人和其他48个人握手，第三个和其他47个人握手…到倒数第7个人时不再握手。结果是：1024。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int tol = 0;
    for (int i = 49; i >= 7; i--)
        tol += i;
    cout << tol << endl;
    return 0;
}

试题B：小球反弹

结果是：1100325199.77

#include <bits/stdc++.h>
using namespace std;

int main()
{
	long long t = 1, x = 343720, y = 233333, dx = 15, dy = 17;
	while (true)
	{
		if ((t * dx) % x == 0 && (t * dy) % y == 0) break;
		t++;
	}
	printf("%.2f\n", 2 * sqrt(dx * dx + dy * dy) * t);
	return 0;
}

试题C：好数

用一个值标记奇数位还是偶数位。

#include <bits/stdc++.h>
using namespace std;

bool check(int n)
{
    int i = 1; // 标记奇数位还是偶数位
    while (n)
    {
        if (i % 2 != n % 2) return false;
        i++;
        n /=10;
    }
    return true;
}

int main()
{
    int n, ret = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        if (check(i)) ret++;
    }
    cout << ret << endl;
    return 0;
}

试题D：R格式

// 样例输入
2 3.14

// 样例输出
13

算是高精度乘法，首先将字符串逆序方便计算，记录下小数点的位置，后面四舍五入要用，做乘法的时候需要处理好进位，最后四舍五入的时候也要处理进位。
当我们记录下小数点的位置把小数点去掉后，相应数的位置就发生的改变，需要注意映射关系。

#include <bits/stdc++.h>
using namespace std;

void mul(vector<int>& D)
{
   int t = 0;//记录进位
   for (int i = 0; i < D.size(); i++)
   {
       t += D[i] * 2;
       D[i] = t % 10;
       t /= 10;
   }
   if (t) D.push_back(1);
}
void add(vector<int>& D, int pos)
{
    int t = 1;
    for (int i = pos; i < D.size(); i++)
    {
        t += D[i];
        D[i] = t % 10;
        t /= 10;
    }
    if (t) D.push_back(1);
}
int main()
{
    int n;
    string d;
    cin >> n >> d;
    reverse(d.begin(), d.end());
    int pos = d.find('.');// 记录下小数点的位置
    vector<int> D;
    for (char ch : d)
        if (ch != '.')
            D.push_back(ch - '0');
    while (n--) mul(D);
    if (D[pos - 1] >= 5) add(D, pos);
    for (int i = D.size() - 1; i >= pos; i--)
        cout << D[i];
    return 0;
}

试题E：宝石组合

// 样例输入
5
1 2 3 4 9

// 样例输出
1 2 3

试题F：数字接龙

// 样例输入
3 3
0 2 0
1 1 1
2 0 2

// 样例输出
41255214

很明显的dfs，初始化向量坐标的时候按照题目要求初始化，方便记录路径。
用四维数组判断是否交叉，两个方向都要判断。

#include <bits/stdc++.h>
using namespace std;

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 20;
int a[N][N];
bool used[N][N], f[N][N][N][N];
int n, m;
string ret;

bool dfs(int i, int j)
{
	if (i == n - 1 && j == n - 1) return ret.size() == n * n - 1;
	used[i][j] = true;
	for (int k = 0; k < 8; k++)
	{
		int x = i + dx[k],  y = j + dy[k];
		if (x < 0 || x >= n || y < 0 || y >= n) continue;
		if ((a[i][j] + 1) % m != a[x][y] || used[x][y]) continue;
		if (f[i][y][x][j] || f[x][j][i][y]) continue;
		
		f[i][j][x][y] = true;
		ret += k + '0'; 
		if (dfs(x, y)) return true;
		ret.pop_back();
		f[i][j][x][y] = false;
	}
	used[i][j] = false;
	return false;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)	
			cin >> a[i][j];
	if (dfs(0, 0)) cout << ret << endl;
	else cout << -1 << endl;
	return 0;
}

试题G：爬山

// 样例输入
4 1 1
4 5 6 49

// 样例输出
18

试题H：拔河

// 样例输入
5
10 9 8 12 14

// 样例输出
1

用前缀和数组统计出所有子区间的和，然后排升序，统计出相邻子区间和的最小值。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e3 + 10;
ll a[N], pre[N];
ll n, ret = LLONG_MAX;
vector<ll> v;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i]; // 计算前缀和数组 
	}
	for (int r = 2; r <= n; r++)
		for (int l = 1; l < r; l++)
			v.push_back(pre[r] - pre[l]);
	sort(v.begin(), v.end()); // 对所有子区间和排序 
	for (int i = 1; i < v.size(); i++)
		ret = min(ret, abs(v[i] - v[i - 1])); // 找到相邻两个子区间和最小值 
	cout << ret << endl; 
	return 0;
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~