NOTES · 学习笔记
第十七届蓝桥杯省赛 B 组:整数对计数与队伍分组
题目
整数对计数
我们看这道题,简化一下题目就变成了:给定一个 N = 2026202520242023。
x + y = N,x < y;我们要求满足这几个条件的 <x, y> 有几个。
这道题我们可以直接根据数学逻辑去解决。
我们来举几个例子:
假设 N = 5(奇数),x = 0、1、2,满足条件的一共有 3 组。
假设 N = 6(偶数),x = 0、1、2,满足条件的一共有 3 组。
所以我们能推出公式:(N + 1) / 2。
我们来观察一下,满足条件的 x 是从 0 开始的。因为要求 x < y,又有 x + y = N,所以 y = N - x。
代入条件 x < y,得到 x < N - x,整理后得到 2x < N。
也就是说,x 最大只能取到小于 N / 2 的整数,因此 x 的取值范围是 0 ≤ x < N / 2。
因为 x 从 0 开始,所以满足条件的组合数量为 (N + 1) / 2。
#include <iostream>
using namespace std;
int main()
{
long long N = 2026202520242023;
long long count = (N + 1) / 2;
cout << count;
return 0;
}队伍分组
我们看这道题,提取一下有效信息,N 表示有 N 种不同的位置,例如 N = 5 表示有 5 种不同位置,N = 6 表示有六种不同位置。
还包括一个数组 vector,这个数组中的数字加起来就是总人数。看题,我们要判断是否能将所有人员分配到不同的位置进行比赛,且不能落下任何一人。
所以要满足的条件就是:1,总人数 % 5 == 0,因为 5 人一组。2,Ai <= k,每个位置的人数为 Ai。假设 Ai 为 2,就表示玩这个位置的人有两个人,那么 Ai = 2。如果某个位置需要 2 个人,那么至少需要 2 支队伍才能满足这个位置的人员需求。如果总共有 3 支队伍,那么这个位置最多只能有 3 个人,否则就会有队伍缺少该位置的参赛人员。
我们先来看第一个条件:
总人数必须能够被 5 整除,因为每支队伍需要 5 个人。如果总人数不能被 5 整除,那么就无法将所有人分成完整的队伍,必然会有人无法参加比赛。
接下来是第二个条件。
假设总人数为 sum,那么能够分成的队伍数量就是:int k = sum / 5。
每个位置需要的人数为 A[i]。因为每支队伍都需要有一个人参加每个位置的比赛,所以如果某个位置需要的人数超过了队伍数量,那么就会出现队伍没有人参加这个位置的情况。因此,必须满足 A[i] <= k。
当这两个条件都满足时,就可以将所有人员分配到不同的位置进行比赛,不会落下任何一人。
所以我们可以得出结论:如果 sum % 5 != 0,那么不能完成分组;如果存在 A[i] > k,那么也不能完成分组;只有两个条件都满足,才能完成分组。
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
int N;
scanf("%d", &T);
while (T > 0) {
scanf("%d", &N);
vector<int> A(N);
for (int i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
T--;
int sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i];
}
if (sum % 5 != 0) {
cout << "F" << endl;
} else {
int k = sum / 5;
bool ok = true;
for (int i = 0; i < N; i++) {
if (A[i] > k) {
ok = false;
break;
}
}
if (ok == true) {
cout << "T" << endl;
} else {
cout << "F" << endl;
}
}
}
return 0;
}