信息奥赛复盘｜2023多校新生周赛一（2023.10.21）
比赛信息 📚
时间：2023 年 10 月 21 日 18:00 - 21:00
竞赛链接：http://10.7.95.2/contest/1299/problems（仅ZJNU内网登录）
ACM集训队讲解视频：/
个人情况 ✍️
本周个人排名：25/187
AC情况：6/7
比赛时间：2023.10.21（18：00 - 21:00）
T1、T2 是经典走楼梯问题，递推即可 AC ✅
T3、T4 是关于矩阵的思维题，思考良久，才发现相关规律 AC ✅
T5 是关于逆序对的问题，调试良久（long long 一生之敌），最后 AC ✅
T6 数据范围较小，使用二进制枚举 AC （赛后尝试dfs暴力搜索）✅
T7 大模拟题，考察结构体、STL容器合理运用以及模拟功底，赛场写完大部分代码，但是调试时间不够，未能 AC ❌（赛后完善部分代码后 AC）
总体来看，这次周赛给自己的提升还是很大的，继续加油 😀
题目列表 🧑🏻💻
| 题目名称 | 难度 |
|---|---|
| T1 - 飞飞走楼梯（Easy） | 🟢 |
| T2 - 飞飞走楼梯（Hard） | 🟢 |
| T3 - 飞飞的水题 | 🟡 |
| T4 - 飞飞数人数 | 🟡 |
| T5 - 飞飞逆序对 | 🟡 |
| T6 - 飞飞的佳肴 | 🟡 |
| T7 - 飞飞打比赛 | 🟡 |
题解 🚀
A - 飞飞走楼梯（Easy）
题目信息 📚
【题目描述】
飞飞在为参加 ACM 集训队而努力刷题，但是现在他遇到了一个难题，你能否帮帮他。
飞飞目前位于第 $0$ 级台阶上，他想要前往第 $n$ 级台阶。飞飞每一步可以向上走一级台阶或者两级台阶。
问飞飞恰好走到第 $n$ 级台阶的不同方法数。
【输入】
一行一个正整数 $n$ $(1 \le n \le 10)$。
【输出】
一行一个整数，表示答案。
【数据范围】
$1 \le n \le 10$
【输入样例1】
1【输出样例1】
1【输入样例2】
2【输出样例2】
2题目解析 🍉
【题目分析】
签到题，经典递推之走楼梯。（数据范围较小，无需开 long long）
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[15], n;
int main() {
// 递推
a[1] = 1, a[2] = 2;
for (int i = 3; i <= 10; i++) {
a[i] = a[i - 1] + a[i - 2];
}
cin >> n;
cout << a[n] << endl;
return 0;
}B - 飞飞走楼梯（Hard）
题目信息 📚
【题目描述】
飞飞在为参加 ACM 集训队而努力刷题，但是现在他遇到了一个难题，你能否帮帮他。
飞飞目前位于第 $0$ 级台阶上，他想要前往第 $n$ 级台阶。飞飞每一步可以向上走一级台阶，两级台阶或者四级台阶。
问飞飞恰好走到第 $n$ 级台阶的不同方法数。
【输入】
一行一个正整数 $n$ $(1 \le n \le 70)$。
【输出】
一行一个整数，表示答案。
【数据范围】
$1 \le n \le 70$
【输入样例1】
1【输出样例1】
1【输入样例2】
2【输出样例2】
2题目解析 🍉
【题目分析】
签到题，经典递推之走楼梯。（数据范围较大，需开 long long）
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 72;
LL a[N], n;
int main() {
// 递推
a[1] = 1, a[2] = 2, a[3] = 3, a[4] = 6;
for (int i = 5; i <= 71; i++) {
a[i] = a[i - 1] + a[i - 2] + a[i - 4];
}
cin >> n;
cout << a[n] << endl;
return 0;
}C - 飞飞的水题
题目信息 📚
【题目描述】
飞飞有 $1$ 个矩阵，每次飞飞可以选择矩阵中任意的一个位置作为起点，每次可以往前走一步，或者向左/右旋转 $90^{\circ}$，但过程中不能走出这个矩阵。
现在飞飞想要知道，对于 $n \times m$ 的矩阵，从任意起点开始，走完整个矩阵所需要的最少的旋转次数。
【输入】
第一行有一个正整数 $K$ $(1 \le K \le 50000)$，表示有 $K$ 个测试样例。
接下来 $K$ 行，每行两个正整数 $n, m$ $(1 \le n, m \le 10^6)$。
【输出】
共 $K$ 行，每行一个正整数，表示走完整个矩阵所需要的最少的旋转次数。
【数据范围】
$1 \le K \le 50000$
$1 \le n, m \le 10^6$
【输入样例1】
4
1 1
2 2
3 3
3 4【输出样例1】
0
2
4
4题目解析 🍉
【题目分析】
对于 $n <= m$ 的情况，只需按照如下方式走即可（@为转弯处）
-----@
@----@
@-----$num_@ = (n - 1) * 2$
对于 $n > m$ 的情况，交换 $n$ 和 $m$ 的值，转换成 $n < m$ 的情况即可
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
void solve() {
cin >> n >> m;
if (n > m) swap(n, m);
cout << (n - 1) * 2 << endl;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}D - 飞飞数人数
题目信息 📚
【题目描述】
飞飞作为ACM集训队未来的体育委员，飞飞负责本次集训队的方阵练习。
已知集训队共有 $n \times m$ 名队员，飞飞准备将所有队员排成一个 $ n \times m$ 的矩阵，飞飞站在矩阵的左下角。
对于任意一名队员，若他与飞飞的连线之间没有其他的队员，则飞飞可以看到该名队员。
请问飞飞能看到的队员数量有多少？
【输入】
一行两个整数 $n, m$ $(1 \le n, m \le 10^3)$。
【输出】
一行一个整数，表示答案。
【输入样例1】
4 4【输出样例1】
9题目解析 🍉
【题目分析】
法一：采用类似于「埃氏色」那样的筛选法，确认一个元素可以被看见后，消去它后面所有的”倍数“即可。
法二：找数学性质。
点 $(x, y)$ 与 $(0, 0)$ 构成的直线为$ y = kx$，同一条直线上的点均满足 $y = kx$。
如点 $(2, 6)$ 和 $(1, 3)$ 均满足 $y = 3x$。
但是 $(2, 6)$ 是 $(1, 3)$ 的倍数（$\because gcd(2, 6) = 2 \ne 1$），所以 $(2, 6)$ 不能被看见。
而 $ (1, 3)$ 不是任何点的倍数（$\because gcd(1, 3) = 1$），所以 $(1, 3)$ 可以被看见。
因此我们只需要统计 $gcd(x, y) = 1$ 的点即可
【C++代码】筛选法 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int n, m;
bool b[N][N];
int main() {
cin >> n >> m;
// 只有一个人时
if (n == 1 && m == 1) cout << 0 << endl;
else if (n == 1 || m == 1) cout << 1 << endl; // 只有一行人或者一列人时
else {
b[0][0] = true; // 自己无法被看见
int cnt = 0;
// 类似于埃氏筛选法
// 若当前元素未被筛去，则说明可以被看见，cnt++，并将该元素后面的所有（同一直线上）元素筛去
// 若当前元素已被筛去，则说明无法被看见
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 若当前元素未被筛去，则说明可以被看见，cnt++，并将该元素后面的元素筛去
if (!b[i][j]) {
cnt++;
// 该元素与原点（0，0）的横纵坐标差为disx = i，disj = j
int disx = i, disy = j;
// 后面点的坐标为（i，j）不断累加（disx，disy）的（tx，ty）
int tx = disx + i, ty = disy + j;
while (tx <= n - 1 && ty <= m) { // （tx，ty）为边界内的合法点
b[tx][ty] = true;
tx += disx, ty += disy;
}
}
}
}
cout << cnt << endl;
}
return 0;
}【C++代码】gcd法 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
int main() {
cin >> n >> m;
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (__gcd(i, j) == 1) cnt++; // C++自带__gcd()函数
// PS: 0和非零数a的最大公约数为a（正好符合只有(0，1)和(1，0)才能被看见的题干要求）
// PS: 0和0的最大公约数在数学上无定义，但是在计算机编程中，会返回0（正好符合自己看不到自己的题干要求）
}
}
cout << cnt << endl;
return 0;
}E - 飞飞逆序对
题目信息 📚
【题目描述】
飞飞特别喜欢逆序对，他想利用逆序对来考考你。
现在需要你构造一个长度为 $n$ 的全排列，使其逆序对个数恰好为 $m$。
【输入】
一行两个正整数 $n, m$ $(1 \le n \le 10^5, 0 \le m \le \dfrac{n (n - 1)}{2})$。
【输出】
一行 $n$ 个整数，表示一个长度为 $n$ 的全排列。
答案不唯一，任意一组符合条件的解均会被判定为正确。
数据保证一定有解。
【输入样例1】
3 2【输出样例1】
3 1 2题目解析 🍉
【题目分析】
比赛时看见逆序对，第一个想法是「归并排序求逆序对数量」，想着暴力枚举所有全排列，然后统计每个排列的逆序对数量是否为m。（但是很显然，该数据范围下，会 TLE ❌）
因此分析相关性质，发现如下可行做法：
如 $n=8, m=15$
- 将 $8$ 提前，就可以构造 $8 - 1 =7$ 个逆序对，$m = m - 7 = 8$
1 2 3 4 5 6 7 8→8 1 2 3 4 5 6 7
- 将 $7$ 提前就又可以构造 $7 -1 = 6$ 个逆序对，$m = m - 6 = 2$
8 1 2 3 4 5 6 7→8 7 1 2 3 4 5 6
- $m = 2 < 6 - 1$ ，因此不需要把 6 提到最前面，再往前提 $m = 2$ 位即可。
8 7 1 2 3 4 5 6→8 7 1 2 3 6 5 4
根据以上思路书写代码，再调试一下边界值即可AC。（注意 $m$ 可能爆 int）
【C++代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m;
int main() {
cin >> n >> m;
// maxv指向当前最后一位数字
LL maxv = n;
// 把maxv提到最前面，可以构造maxv-1个逆序对
// 不断用该方法，减小m
while (m >= maxv - 1 && maxv > 0) {
// 输出当前最后一位数字
cout << maxv << " ";
m = m - maxv + 1;
maxv--;
}
// while结束后，已经构造了 n,n-1,n-2,...,1,2,3,...maxv
// 此时m<maxv-1,说明不需要把max提到最前面，只需要放到前面m个位置即可
// 即构造n,n-1,n-2,...,1,2,3,...maxv,4,5,...maxv-1
if (m < maxv - 1) {
// 输出1,2,3...
for (int i = 1; i <= maxv - m - 1; i++) cout << i << " ";
// 输出maxv
cout << maxv << " ";
// 输出4,5,...,maxv-1
for (int i = maxv - m; i <= maxv - 1; i++) cout << i << " ";
}
return 0;
}F - 飞飞的佳肴
题目信息 📚
【题目描述】
佳肴就是非常美味的菜的意思，佳肴最关键的是选择好原料。
飞飞现在有 $N$ 种原料，每种原料都有酸度 $S$ 和苦度 $B$ 两个属性，当选择多种原料时，总酸度为每种原料的酸度之积，总苦度为每种原料的苦度之和。
正如大家所知，佳肴是既不酸也不苦的，因为要保证所选的原料使得总酸度和总苦度差值的绝对值最小。
由于佳肴不能只有水，所以必须至少选择一种原料。
【输入】
输入第一行包含一个整数 $N$ $(1 \le N\le 10)$，表示原料的种数。
接下来 $N$ 行，每行包含两个用一个空格隔开的整数，分别表示酸度和苦度。
【输出】
输出总酸度和总苦度最小的差值。
【数据范围】
$1 \le N\le 10$
输入数据保证总酸度大小不超过 $10^{15}$，每个原料的苦度不超过 $10^{14}$。
【输入样例1】
2
3 8
5 8【输出样例1】
1【输入样例2】
4
1 7
2 6
3 8
4 9【输出样例2】
1题目解析 🍉
【题目分析】
数据范围较小，DFS暴搜 或者 二进制枚举均可。
【C++代码】
DFS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 12;
LL s[N], b[N];
int n;
LL dis = 1e16 + 10;
// flag 保证至少有一个原料
void dfs(int step, LL s_sum, LL b_sum, int flag) {
if (step == n + 1) {
if (flag == 1) {
dis = min(dis, abs(s_sum - b_sum));
}
return;
}
// 选择第step个原料
dfs(step + 1, s_sum * s[step], b_sum + b[step], 1);
// 不选择第step个原料
dfs(step + 1, s_sum, b_sum, flag);
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i] >> b[i];
// 从第1个原料开始搜索
dfs(1, 1, 0, 0);
cout << dis << endl;
return 0;
}二进制枚举
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 12;
LL s[N], b[N];
LL dis = 1e17;
int n;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i] >> b[i];
// 二进制枚举
int sum = 2 << n; // sum为总的方案数 1 ~ 2^10-1
for (int i = 1; i < sum; i++) {
LL s_sum = 1, b_sum = 0;
// 二进制分解i
int t = i;
for (int j = 1; j <= n; j++) {
int status = t % 2;
t /= 2;
if (status)
s_sum *= s[j], b_sum += b[j];
}
dis = min(dis, abs(s_sum - b_sum));
}
cout << dis << endl;
return 0;
}G - 飞飞打比赛
题目信息 📚
【题目描述】
飞飞参加了第十九届浙江师范大学大学生程序设计竞赛，飞飞用他强势的后台拿到了比赛的提交记录。
已知他拿到了 $n$ 条提交记录，每条提交记录由提交时间 $T$，队伍名称 $S$，题号 $H$，提交状态 $X$ 组成，飞飞的队伍名称为“feifei”，请你告诉飞飞他最终的过题数、罚时以及排名。
ACM赛制
比赛实时评测并返回结果，单次提交的结果如果错误会有 $20$ 分钟的加罚时间。
每个题目只有在所有数据点全部正确后才能得到分数。
比赛排名根据做题数来评判，做题数相同的，根据总用时来评判。总用时是每题用时的和。
每题的罚时是从比赛开始到第一次通过该题的分钟数与该题通过前的加罚时间之和。
比赛的总罚时是所有通过的题目的罚时。
【输入】
一行两个正整数 $n,m$，分别表示提交记录的数量与题目的数量。
接下来 $n$ 行，每行按照顺序输入一个整数、一个字符串、一个正整数、一个字符串，分别表示提交时间 $T$，队伍名称 $S$，题号 $H$，提交状态 $X$。
- $1 \le n \le 10^4$
- $1 \le m \le 20$
- $0 \le T \le 300$
- $|S| \le 13$
- $1 \le H \le m$
- 提交状态取值分别为：
AC：表示该题目通过TLE：表示代码时间超限，题目未通过，并算作加罚MLE：表示代码空间超限，题目未通过，并算作加罚CE：表示代码编译错误，题目未通过，不算作加罚RE：表示代码出现运行时错误，题目未通过，并算作加罚WA：表示答案错误，题目未通过，并算作加罚PE：表示输出格式错误，题目未通过，并算作加罚
【输出】
一行三个整数，按照顺序分别表示飞飞的过题数、罚时以及排名。
因为飞飞的能力太强了，如果有人和飞飞的过题数与罚时相同，则飞飞能得到比他们更高的排名（即数字更小）。
【输入样例1】
7 5
284 uytftuapvcrm 3 MLE
12 uytftuapvcrm 1 CE
167 feifei 4 AC
181 feifei 1 AC
297 uytftuapvcrm 4 AC
71 uytftuapvcrm 1 MLE
107 feifei 4 WA【输出样例1】
2 368 1【提示】
如果一支队伍在同一时间，对同一题目，有不同的提交，则按照数据输入顺序进行排序。
例如 feifei 在时间 $10$ 分钟的时候 在题目 $1$ 中提交了两次代码，分别获得 AC 和 WA。
如果数据读入为：10 feifei 1 AC10 feifei 1 WA
则表示 feifei 是先 AC 了一次，其后又 WA 了一次。
反之，如果数据读入为：10 feifei 1 WA10 feifei 1 AC
则表示 feifei 是先 WA 了一次，其后又 AC 了一次。
同时保证 feifei 有提交记录。
题目解析 🍉
【题目分析】
大模拟题，考察结构体、STL容器合理运用以及模拟功底。
【复盘后的优化代码】✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10, M = 25;
// 定义每一次提交
typedef struct submit {
int sub_id; // 提交的序号
int sub_time; // 提交时间
string name; // 提交队伍名称
int p_id; // 题目id
string status; // 评测状态
} Submit;
Submit submits[N];
// 所有提交重新排序的规则
bool cmp(Submit s1, Submit s2) {
if (s1.sub_time == s2.sub_time) {
return s1.sub_id < s2.sub_id;
} else {
return s1.sub_time < s2.sub_time;
}
}
// 定义每一支队伍
typedef struct team {
int is_ac[M]; // M道题目是否AC，如is_ac[5]=1表示第5题已AC
int ac_sum; // 当前AC的题目总数
int p_time[M]; // M道题各自的罚时
int p_time_sum; // 总罚时
int rank; // 队伍排名
} Team;
Team teams[N];
unordered_map<string, Team> mp; // mp根据队伍名称存储相关数据
int n, m;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> m;
// 读取n条评测信息
for (int i = 1; i <= n; i++) {
submits[i].sub_id = i;
cin >> submits[i].sub_time >> submits[i].name >> submits[i].p_id >> submits[i].status;
}
sort(submits + 1, submits + n + 1, cmp); // 将评测信息按照要求排序
// 按照时间顺序，读取每一条评测信息，更新teams数据
int time, number;
string tname, status;
for (int i = 1; i <= n; i++) {
time = submits[i].sub_time, number = submits[i].p_id, tname = submits[i].name, status = submits[i].status;
// 当前提交为"AC"，需要检查该队伍是否已在之前已经AC此题
if (status == "AC") {
if (mp[tname].is_ac[number] == 0) { // 检查该队伍是否已在之前已经AC此题
mp[tname].ac_sum++; // 更新该队总AC题数
mp[tname].is_ac[number] = 1; // 更新该题AC状态
mp[tname].p_time[number] += time; // 计算该题总罚时
mp[tname].p_time_sum += mp[tname].p_time[number]; // 更新该队总罚时
}
} else if (status == "MLE" || status == "WA" || status == "TLE" || status == "RE" || status == "PE") {
if (mp[tname].is_ac[number] == 0) { // 如果此前这道题未AC，添加罚时
mp[tname].p_time[number] += 20;
}
}
}
// 取出所有队伍信息，计算feifei的排名
string s = "feifei";
for (auto it: mp) {
string name = it.first;
Team t = it.second;
// 取出的队伍ac数 > feifei
if (t.ac_sum > mp[s].ac_sum) {
mp[s].rank++; // feifei排名往后延一位
} else if (t.ac_sum == mp[s].ac_sum && t.p_time_sum < mp[s].p_time_sum) {
// 取出的队伍ac数 = feifei 但是总罚时 < feifei
mp[s].rank++; // feifei排名往后延一位
}
}
// 输出feifei的数据
cout << mp[s].ac_sum << " " << mp[s].p_time_sum << " " << mp[s].rank + 1 << endl;
return 0;
}
