复盘｜2023多校新生周赛二

信息奥赛 C++
信息奥赛复盘
发布日期:   2023-10-23
文章字数:   3.7k
阅读时长:   14 分
阅读次数:  

信息奥赛复盘｜2023多校新生周赛二（2023.10.22）

比赛信息 📚

时间：2023 年 10 月 22 日 18:00 - 21:00

竞赛链接：http://10.7.95.2/contest/1301/problems（仅ZJNU内网登录）

ACM集训队讲解视频：/

个人情况 ✍️

本周个人排名：25/76

AC情况：3/7

比赛时间：2023.10.22（18：00 - 21:00）

T1 大模拟题，无时间做 ❌

T2 大四老人已经忘了椭圆离心率公式 ❌

T3 贪心，签到题 ✅

T4 前缀和 + 暴力枚举 ✅

T5 T4的困难版，赛场上未相处优化方法 ❌

T7 全场花了最长时间的题，尝试DFS，贪心，数学等方法均失败，最后尝试动态规划打表（数据范围大一点就不能这样做了），勉强 AC ✅

T8 总感觉题目非常眼熟，但是不会做 ❌

总体来看，这次周赛状态一般，而且题目也偏难， 😀

题目列表 🧑🏻‍💻

题目名称 难度
T1 - 飞飞玩以太战线 🟡
T2 - 飞飞的椭圆 🟡
T3 - 飞飞爱取模 🟢
T4 - 飞飞当黑客easy 🟢
T5 - 飞飞当黑客hard 🟡
T6 - 飞飞猜数字 🟡
T7 - 飞飞的书架 🟡
T8 - 飞飞的小游戏 🟡

题解 🚀

A - 飞飞玩以太战线

题目信息 📚

【题目描述】

机房里的大家最近都开始玩《崩坏星穹铁道》了，飞飞发现以太战线里的AI太聪明了，他希望能够自己写一个 AI 程序，能够控制比赛的输赢。

现在雪碧和可乐正在用这个 AI 对战，现在飞飞想知道最后的赢家是谁。

AI规则

  • 规则

    • 玩家情况：
      • 玩家 xuebi，有 $n$ 个怪物
      • 玩家 kele，有 $m$ 个怪物
      • 双方玩家初始各自有 $3$ 个战技点，最大为 $5$
    • 怪物属性：
      • $id$：每个玩家怪物的编号，双方怪物各自按照输入顺序依次从 $1$ 开始编号
      • $hp$：血量
      • $energy$：终结技能量，初始为 $0$
      • $speed$：速度
      • $atk1$：普通攻击造成的伤害，可以恢复攻击方 $1$ 点战技点
      • $atk2$：战技造成的伤害，需要消耗攻击方 $1$ 点战技点
      • $atk3$：终结技造成的伤害，需要消耗该怪物 $3$ 点 $energy$
    • 攻击规则：
      • $t$，双方玩家最大游戏轮数，若某一时刻 $t \gt 0$，但场上已经没有怪物能够攻击则游戏结束，或者 $t=0$ 则游戏结束
      • 一轮，每个怪物一轮最多释放普通攻击或者战技一次，若此轮已经没有怪物能够攻击，则当前轮结束，即令 $t:=t-1$
      • 怪物 $hp \le 0$ 被判定为死亡，即无法被攻击或者进行攻击
      • 所有怪物按照 $speed$ 攻击，$speed$ 大的优先，若 $speed$ 相同，则玩家 $xuebi$ 的怪物优先，若是同一个玩家的怪物，则 $id$ 小的优先
      • 怪物释放普通攻击或者战技为都会使得该怪物的 $energy + 1$
      • 双方玩家的怪物进行任何攻击时会自动选择敌方当前存活的编号最小的怪物
      • 若怪物攻击时，攻击方玩家有战技点，则优先释放战技，否则进行普通攻击
      • 若任一怪物的 $energy \ge 3$，则立即释放终结技并令 $energy=0$
    • 胜负规则：
      • 游戏结束后，场上存活怪物多的玩家胜利
      • 若数量相同，则各自怪物 $hp$ 总和多的胜利
      • 若 $hp$ 总和相同，则玩家 xuebi 胜利
【输入】

第一行包含一个整数 $T$，表示测试数据组数。

对于每组数据：

第一行包含三个整数 $n, m, t$，分别表示玩家 xuebi 和玩家 kele 的怪物数量以及最大游戏轮数。

后面 $n$ 行，每行包含五个整数 $hp, speed, atk1, atk2, atk3$，表示玩家 xuebi 的怪物属性。

后面 $m$ 行，每行包含五个整数 $hp, speed, atk1, atk2, atk3$，表示玩家 kele 的怪物属性。

  • $1 \le T, n, m \le 100$
  • $1 \le t, hp, speed, atk1, atk2, atk3 \le 1000$
  • $\sum t \le 1000$
  • $\sum n + m \le 200$
【输出】

一行一个整数，表示答案。

【数据范围】

共 $T$ 行。如果玩家 xuebi 胜利，输出 xuebi，如果玩家 kele 胜利，输出 kele。

【输入样例1】
2
1 1 100
2 3 1 1 1
2 2 1 1 1
1 1 100
4 3 1 1 1
5 2 1 1 1
【输出样例1】
xuebi
kele

题目解析 🍉

【题目分析】
【C++代码】✅

B - 飞飞的椭圆

题目信息 📚

【题目描述】

飞飞最近爱上了椭圆，于是他想考考你关于椭圆的一些性质。

给定一个椭圆上的 $n$ 个点（其中一定包含椭圆的四个顶点）。

问该椭圆的离心率。

【输入】

第一行一个整数 $n$ $(4 \le n \le 5 \times 10^3)$。

接下来 $n$ 行，每行两个浮点数 $x_i, y_i$ $(-2000 \le x_i, y_i \le 2000)$。

【输出】

一行一个浮点数表示答案。

【输入样例1】
4
5 0
-5 0
0 3
0 -3
【输出样例1】
0.800000000000
【输入样例2】
4
3.330127018922 4.500000000000
-5.330127018922 -0.500000000000
0.500000000000 -0.598076211353
-2.500000000000 4.598076211353
【输出样例2】
0.800000000000

题目解析 🍉

【题目分析】
【C++代码】✅

C - 飞飞爱取模

题目信息 📚

【题目描述】

飞飞有一个从 $1$ 到 $n$ 的序列 $a$，现在他可以把这个序列重新排列。

请问重新排列后 $\sum\limits_{i=1}^{n} (a_i \bmod i)$ 的最大值是多少。

【输入】

第一行一个正整数 $n$，表示序列长度。

【输出】

一个整数表示答案。

【数据范围】

$1 \le n \le 10^9$

【输入样例1】
2
【输出样例1】
3

题目解析 🍉

【题目分析】

已知 $x \bmod i = c$，则有 $0 \le c \le i-1$

所以对于 $\sum\limits_{i=1}^{n} (a_i \bmod i)$，若每个位置都能取到 $i-1$，则取模之和最大。

以下排列满足该要求：n,1,2,...,n-1

故总和为：$1 + 2 + … + n-1 = n * (n-1) / 2$

PS：注意 $n$ 的范围，需要开 long long

【C++代码】✅
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
LL n; // 注意开long long

int main() {
    cin >> n;
    cout << n * (n - 1) / 2 << endl;

    return 0;
}

D - 飞飞数人数

题目信息 📚

【题目描述】

飞飞是一名黑客，但是他运气不佳，选课时段来临时，他选的课全都掉了，因此他想要侵入浙江师范大学教务网报复那些抢他课的欧皇。

在入侵的过程中，飞飞得到了一串密钥，这个密钥是一个长度为 $n$ 的序列，为了破解这个密钥，他必须求出序列中一段连续子序列的最大平均值，且这个连续子序列的长度不小于 $k$。

众所周知，飞飞不屑于做这种简单的问题，于是他把这个问题扔给了你，如果你能解决这个体力活，他将不再嘲笑你。

【输入】

第一行两个正整数 $n,k$。

第二行 $n$ 个整数表示这个序列。

  • $1 \le k \le n \le 5000$
  • $1 \le a_i \le 5000$
【输出】

一个浮点数表示答案，四舍五入保留 $2$ 位小数。

【输入样例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++代码】筛选法 ✅
【C++代码】gcd法 ✅

D - 飞飞当黑客easy

题目信息 📚

【题目描述】

飞飞是一名黑客，但是他运气不佳，选课时段来临时，他选的课全都掉了，因此他想要侵入浙江师范大学教务网报复那些抢他课的欧皇。

在入侵的过程中，飞飞得到了一串密钥，这个密钥是一个长度为 $n$ 的序列，为了破解这个密钥，他必须求出序列中一段连续子序列的最大平均值，且这个连续子序列的长度不小于 $k$。

众所周知，飞飞不屑于做这种简单的问题，于是他把这个问题扔给了你，如果你能解决这个体力活，他将不再嘲笑你。

【输入】

第一行两个正整数 $n,k$。

第二行 $n$ 个整数表示这个序列。

【输出】

一个浮点数表示答案，四舍五入保留 $2$ 位小数。

【输入样例1】
4 3
3 4 1 2
【输出样例1】
2.67
【输入样例2】
8 6
4 7 9 5 8 1 9 10
【输出样例2】
7.00
【数据范围】

$1 \le k \le n \le 5000$

$1 \le a_i \le 5000$

题目解析 🍉

【题目分析】
【C++代码】✅

E - 飞飞当黑客hard

题目信息 📚

【题目描述】

飞飞是一名黑客，但是他运气不佳，选课时段来临时，他选的课全都掉了，因此他想要侵入浙江师范大学教务网报复那些抢他课的欧皇。

在入侵的过程中，飞飞得到了一串密钥，这个密钥是一个长度为 $n$ 的序列，为了破解这个密钥，他必须求出序列中一段连续子序列的最大平均值，且这个连续子序列的长度不小于 $k$。

众所周知，飞飞不屑于做这种简单的问题，于是他把这个问题扔给了你，如果你能解决这个体力活，他将不再嘲笑你。

【输入】

第一行两个正整数 $n,k$。

第二行 $n$ 个整数表示这个序列。

【输出】

一个浮点数表示答案，四舍五入保留 $2$ 位小数。

【输入样例1】
4 3
3 4 1 2
【输出样例1】
2.67
【输入样例2】
8 6
4 7 9 5 8 1 9 10
【输出样例2】
7.00
【数据范围】

$1 \le k \le n \le 10^5$

$1 \le a_i \le 5000$

题目解析 🍉

【题目分析】
【C++代码】✅

F - 飞飞猜数字

题目信息 📚

【题目描述】

雪碧让飞飞猜一个 $n$ 位数，各位数字之和为 $m$，飞飞想要知道他最多要猜多少次才能猜到答案。

现在他把这个问题交给你，请你写一个程序，告诉他最后的答案。

【输入】

第一行一个整数 $T$ $(1\le T \le 10^4)$ 表示数据的组数。

接下来 $T$ 行，每行两个正整数 $n,m$ $(1 \le n, m \le 9)$。

【输出】

输出 $T$ 行，每行一个整数表示答案。

【输入样例1】
2
1 1
2 1
【输出样例1】
1
1

题目解析 🍉

【题目分析】
【C++代码】✅

G - 飞飞的书架

题目信息 📚

【题目描述】

飞飞新买了一个书架，宽度为 $L$。飞飞想要在书架上从左往右放上书。

他有两种书，第一种厚度是 $1$，第二种厚度是 $h$。他的书有两种颜色，黑色和白色。黑色的书可以是 $1$ 或 $h$，白色的书厚度只能是 $1$。出于美观的目的，他放书必须按照黑白交替放，并且最左边和最右边都要是黑色。

他必须至少放一本书。最左边的书必须放在书架最左边。

他想知道他有多少种放书的方案。(可以不用放满书架)

【输入】

一行两个整数 $L, h$。

【输出】

一行一个整数表示答案。

答案可能非常大，请输出对 $998244353$ 取模后的结果。

【数据范围】

$2 \le h \le L \le 10^6$

【输入样例1】
4 2
【输出样例1】
5
【输入样例2】
100 7
【输出样例2】
19795286

题目解析 🍉

【题目分析】
【C++代码】✅

H - 飞飞打比赛

题目信息 📚

【题目描述】

飞飞在机房里闲来无事，他准备了一些小游戏来取悦自己。

作为飞飞的好朋友，他给了你其中一个游戏并希望你能快速做出它，游戏规则如下：

给你一个 $n \times m$ 的 $\text{0/1}$ 矩阵，目标是判断是否能把所有矩阵元素全部变成 $0$，你可以进行如下操作：

  • 选择一个格子，并将以该格子为中心的十字区域进行 $\text{0/1}$ 变换（即 $0$ 变成 $1$，$1$ 变成 $0$，注意十字区域不能超出 $0/1$ 矩阵）。

  • 十字区域：对于点 $(x,y)$，十字区域表示 $(x,y),(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ ,并且这五个位置存在。

因为飞飞看起来很开心，所以你只需要将最后结果以 YES 或者 NO 的形式告诉他。

【输入】

第 $1$ 行包含两个整数 $n, m$ $(1 \le n, m \le 1000)$。

第 $2$ 行到 $n+1$ 行，每行包含 $m$ 个整数，表示这个 $\text{0/1}$ 矩阵。

【输出】

一行，为 YES 或 NO，表示原矩阵是否可以通过转换变成全 $0$ 矩阵。

【输入样例1】
4 5
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
【输出样例1】
YES
【输入样例2】
4 5
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
【输出样例2】
NO

题目解析 🍉

【题目分析】

比赛时看错了题干要求，以为不满足十字的格子也能操作，实际上只有内部的点才可以进行操作，边界上（$row_1,row_n,col_1,col_m$）是不能进行操作的。

从 $(2, 2)$ 点开始，扫描 $row_2$，若发现 $row_1$ 对应点为1，就对当前点做一次十字翻转，消去上面一行的 1。

依次往下递推，最后检查一遍矩阵有无1即可。

【复盘后的优化代码】✅
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int n, m;
int g[N][N]; // 存储矩阵
int dir[5][2] = {{0,  0},  // 十字翻转的五个方向
                 {0,  -1},
                 {0,  +1},
                 {+1, 0},
                 {-1, 0}};

// 做一次十字翻转
void matrix_reverse(int i, int j) {
    for (int k = 0; k < 5; k++) {
        g[i + dir[k][0]][j + dir[k][1]] = 1 - g[i + dir[k][0]][j + dir[k][1]];
    }
}

void solve() {
    // 读取矩阵
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    // 从第二行开始，一行行消除上一行存在的1
    for (int i = 2; i <= n - 1; i++) {
        for (int j = 2; j <= m - 1; j++) {
            if (g[i - 1][j]) matrix_reverse(i, j);
        }
    }

    bool flag = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j]) {
                flag = false;
                break;
            }
        }
    }
    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}
文章作者: Rickyの水果摊
文章链接: https://ricky2333.github.io/2023/10/23/fu-pan-2023-duo-xiao-xin-sheng-zhou-sai-er/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Rickyの水果摊 !
信息奥赛 C++
赏
  目录