【第15届蓝桥杯】软件赛CB组省赛

个人主页：Guiat
归属专栏：算法竞赛真题题解

正文

总共8道题。

A. 握手问题（填空题）

【题目】握手问题

【分析】
纯考察数学中简单排列组合。考虑相互握手的43人：（43 * 42） / 2；考虑剩下7人与43人分别握手：7 * 43；两者相加即最终答案。

【答案】1204

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void solve() { cout << 1204 << '\n'; }

int main() { IOS; solve(); return 0; }

B. 小球反弹（填空题）

【题目】小球反弹

【分析】
考察高中简单物理思维。小球从左上角出发最终回到左上角，说明水平和竖直位移分别是长和宽的偶数倍。又速率之比为位移之比（15：17），可写双重循环控制总过程中长和宽的倍数暴力求解即可。

【答案】1100325199.77

【AC_Code】

#include <iostream>
#include <iomanip>
#include <cmath>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e4;
int L = 343720, W = 233333;

int solve()
{
	for (int i = 2; i <= N; i += 2) for (int j = 2; j <= N; j += 2)
	{
		if (L * i * 17 == W * j * 15)
		{
			cout << fixed << setprecision(2) << sqrt(pow(L * i, 2) + pow(W * j, 2)) << '\n';
			return 0;
		}
	}
}

int main() { IOS; solve(); }

C. 好数

【题目】好数

【分析】
考察模拟。写一个check函数判断是否为好数：逆向思维 ①奇数位为偶数时，返回false；②偶数位为奇数时返回false；①②包含了不满足的所有情况，都不满足最后返回true。其中digit（位数）的使用很关键（在check函数开头设置为1，否则可能会错误累加），还有不要出现悬空else的情况。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, cnt, digit;

bool check(int i)
{
	digit = 1;
	while (i)
	{
		if (digit % 2 == 1) { if ((i % 10) % 2 == 0) return false; }
		else if ((i % 10) % 2 != 0) return false;
		digit ++; i /= 10;
	}
	return true;
}

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

int main()
{
	IOS; solve();
	
	return 0;
}

D. R格式

【题目】R 格式

【分析】
一道模拟题。“将浮点数乘以2 ^ n”这句话可以看出数据很大，考虑用数组模拟高精度算法（低精度乘以高精度）。大体思路是将浮点数d处理成字符串，将字符串反转方便处理小数部分，之后依次乘2，进行模拟，最后判断四舍五入，倒序输出答案。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); 

using namespace std;

const int N = 1e6 + 10;
int n, pos, len, ans[N]; string d;

void solve()
{
	cin >> n >> d; reverse(d.begin(), d.end());
	pos = d.find('.'); d.erase(pos, 1); len = d.size();
	for (int i = 0; i < len; i ++) ans[i + 1] = d[i] - '0';
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= len; j ++) ans[j] *= 2;
		for (int j = 1; j <= len; j ++) ans[j + 1] += ans[j] / 10, ans[j] %= 10;
		if (ans[len + 1]) len ++;
	}
	if (ans[pos] >= 5) ans[pos + 1] ++;
	for (int i = pos + 1; i <= len; i ++) ans[i + 1] += ans[i] / 10, ans[i] %= 10;
	if (ans[len + 1]) len ++;
	for (int i = len; i > pos; i --) cout << ans[i]; cout << '\n';
}

int main()
{
	IOS; solve();
	
	return 0;
}

E. 宝石组合

【题目】宝石组合

【分析】
有些地方不太明白，先给出代码。

【AC_Code】

#include <iostream>
#include <vector>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int MAXN = 1e5 + 10; int n, h[MAXN]; vector<int> fac[MAXN];

void solve()
{
    cin >> n; for (int i = 1; i <= n; ++ i) cin >> h[i];
    sort(h + 1, h + 1 + n);
    for (int i = 1; i <= n; ++ i) for (int j = 1; j * j <= h[i]; ++j)
	{
        if (h[i] % j == 0)
		{
            fac[j].push_back(h[i]);
            if (h[i] / j != j) fac[h[i] / j].push_back(h[i]);
        }
    }
    for (int i = MAXN; i >= 1; -- i)
	{
        if (fac[i].size() >= 3)
		{
            int a = fac[i][0], b = fac[i][1], c = fac[i][2];
            if (__gcd(__gcd(a, b), c) == i) { cout << a << " " << b << " " << c << "\n"; return; }
        }
    }
}

int main()
{
    IOS; solve();

    return 0;
}

F. 数字接龙

【题目】数字接龙

【分析】
不会，先给出代码。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 15;
int n, k, nums[N][N],
dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 },
dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
string nber; bool vis[N][N], check[N][N][N][N];

bool dfs(int a, int b)
{
    if (a == n - 1 && b == n - 1) return nber.size() == n * n - 1;
    vis[a][b] = true;
    for (int i = 0; i < 8; i ++)
    {
        int x = a + dx[i], y = b + dy[i];
        if (x < 0 || x >= n || y < 0 || y >= n) continue;
        if (vis[x][y]) continue;
        if (nums[x][y] != (nums[a][b] + 1) % k) continue;
        if (i % 2 && (check[a][y][x][b] || check[x][b][a][y])) continue;
        check[a][b][x][y] = true; nber += i + '0';
        if (dfs(x, y)) return true;
        nber.pop_back(); check[a][b][x][y] = false;
    }
    vis[a][b] = false;
    return false;
}

void solve()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) cin >> nums[i][j];
    if (!dfs(0, 0)) cout << -1 << '\n';
    else cout << nber << '\n';
}

int main()
{
    IOS; solve();
    
    return 0;
}

G. 爬山

【说明】疑似为错题，直接跳过。

H. 拔河

【题目】拔河

【分析】

【AC_Code】

#include <iostream>
#include <set>
#include <cmath>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;

const int N = 1e3 + 10;
int n; ll a[N], res = 1e9; multiset<long long> s;

ll minn(ll a, ll b) { if (a < b) return a; else return b; }

void solve()
{
    cin >> n; 
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) s.insert(a[j] - a[i - 1]);
    for (int i = 1; i <= n - 1; i++)
    {
        for (int j = i; j <= n; j++)
        {
            auto k = a[j] - a[i - 1]; s.erase(s.find(k));
        }
        for (int j = 1; j <= i; j++)
        {
            auto k = a[i] - a[j - 1]; auto p = s.lower_bound(k);
            if (p != s.end()) res = minn(res, abs(*p - k));
            if (p != s.begin()) p--, res = minn(res, abs(*p - k));
        }
    }
    cout << res << '\n';
}

int main()
{
    IOS; int _ = 1; // cin >> _; 
    while (_ --) solve();
    
    return 0;
}

结语
感谢您的阅读！期待您的一键三连！欢迎指正！