0210 第 5 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-5/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-5/
• 题解回放：无

T1. 十二生肖【算法赛】

问题描述

$2024$年是一个美丽的年份，小蓝想知道$2024$是十二生肖中的哪个动物年？

作为他的朋友，请你帮他解答一下（只需告诉他该动物在十二生肖中排行第几即可）。

鼠视为十二生肖中的第$1$位。

注意：答案输出阿拉伯数字。

输入格式

本题为填空题，无需输入即可作答。

输出格式

输出一个数字，表示答案。

T2. 欢迎参加福建省大学生程序设计竞赛【算法赛】

问题描述

$2023$年$13$月$32\sim 33$日，福建省第十一届大学生程序设计竞赛在东南大学如期举办。来自厦门大学、福州大学、集美大学、华侨大学、福建师范大学等$100$所高校的$n$支队伍参赛。

• 华侨大学“红日初升”代表队，以$13$题$960$罚时，夺得冠军（第$1$名）；
• 厦门大学“点分治分点”代表队、福州大学“西南饺子馆”代表队，$12$题$950$罚时，以一模一样的罚时和题数，并列亚军（第$2$名）；
• 福建师范大学“夜幕降临”代表队、福建理工大学“福理重磅出击”代表队、福建农林大学“重生之我是懒狗”代表队，$11$题$1310$罚时，以一模一样的罚时和题数，并列殿军（第$4$名）；
• ……
• 集美大学“抱歉，这没有集美”代表队，$999$发代码提交却没有$1$发通过，最后以$0$题$0$罚时的成绩，惨遭爆零，取得全场最后一名。

前线记者贝贝发来报道。

已知所有队伍的通过题数、罚时，并且保证给出的顺序，符合 ACM 比赛最终榜单：按题数降序排列，当题数相同时，按照罚时升序排序。

贝贝想知道，若将相同题数、相同罚时的队伍归为一类，最终共有多少类队伍？

输入格式

第一行包含一个整数$n(1\le n\le 10^5)$，表示队伍的数量。

接下来的$n$行，每行$2$个整数$a_i,b_i(0\le a_i\le 13,0\le b_i\le 2\times 10^3)$，分表表示第$i$个队伍的通过题数和罚时。

保证给出的顺序符合 ACM 比赛的最终榜单。

输出格式

输出仅一行，包含一个整数，表示队伍的种类数量。

样例输入

7
13 960
12 950
12 950
11 1310
11 1310
11 1310
0 0

样例输出

4

说明

在样例中，共有$4$类队伍：

• $13$题$960$罚时；
• $12$题$950$罚时；
• $11$题$1310$罚时；
• $0$题$0$罚时。

T3. 匹配二元组的数量【算法赛】

问题描述

给定一个长度为$N$的数组$A$。若一对二元组下标$(i,j)$满足以下关系则被称之为匹配二元组：

• $1 \leq i < j \le N$。

• $\dfrac{a_i}{j}=\dfrac{a_j}{i}$​。

请你统计出$A$中匹配二元组的数量。

输入格式

第一行输入一个整数$N(1 \leq N \leq 10^5)$表示数组$A$的长度。

第二行输入$N$个整数$A_1,A_2,A_3,\cdots,A_n(1 \leq A_i \leq 10^5)$表示数组$A$。

输出格式

输出一个整数表示答案。

样例输入

5
5 4 3 2 1

样例输出

2

T4. 元素交换【算法赛】

问题描述

给定一个大小为$2\times N$的二进制数组$A$，其中包含$N$个$0$和$N$个$1$。

现在，你可以交换数组中的任意两个元素。请你计算，至少需要多少次交换操作，才能保证数组中不存在连续的$0$或$1$。

输入格式

第一行包含一个整数$N$（$1\leq N \leq 10^5$），表示数组$A$的长度。

接下来一行，包含$2 \times N$个由空格分隔的二进制数字（$0$或$1$），表示数组$A$。

输出格式

输出一个整数，表示使数组$A$中不存在连续的$0$或$1$所需的最少交换次数。

样例输入

3
1 1 0 0 1 0

样例输出

1

T5. 下棋的贝贝【算法赛】

问题描述

“玄雍”是王者荣耀自走棋（王者模拟战）中一个非常强大的羁绊阵营，由该阵营衍生出了很多玩法，如“玄雍起舞上官”、“玄雍重战”等等。

每一枚玄雍阵营的棋子可以为周围的棋子叠加一层 buff（即增益效果，为攻击增益或防御增益）， 而每个棋子可以被叠加多层 buff 。

image-20240119230728187

本题可能与游戏中的真实玩法有些许差异，请以题目描述为准。

贝贝想知道，当它有且仅有$n$个玄雍棋子可以放置在无限大的棋盘时，所有棋子共计获得的 buff （不区分攻击和防御增益）层数最多是多少？

更形式化的说，贝贝想在一个无限大的平面直角坐标系中$x,y$坐标均为整数的点上放置棋子，且一个坐标仅能放置一枚棋子。约定“邻居”的定义如下：若棋子$a$的坐标为$(x_a,y_a)$，棋子$b$的坐标为$(x_b,y_b)$，若$|x_a-x_b|+|y_a-y_b|=1$，则称两枚棋子相邻，即棋子$a$和$b$互为邻居。

求解放置$n$枚棋子后，所有棋子的邻居数量的总和的最大值是多少。

输入格式

仅一行，包含一个整数$n(1\le n\le 10^{18})$。

输出格式

仅一行，包含一个整数，表示答案。

样例输入

3

样例输出

4

T6. 方程【算法赛】

问题描述

给定$n,k$，已知有如下条件：

$$x + \frac{1}{x} = k$$

请求解如下式子的值：

$$x^{n}+ \frac{1}{x^{n}}$$

由于答案可能很大，请输出答案对$10^{9} +7$取模后的值。

输入格式

第一行，包含一个正整数$T(1 \leq T \leq 10^3)$，表示测试用例的数量。

每个测试用例仅一行，包含两个正整数$n,k(1\le n,k\le 10^9)$。

输出格式

对于每个测试用例，输出一行一个整数，表示答案对$10^{9} +7$取模后的值。

样例输入

1
2 2

样例输出

2

T7. 学《博弈论》的贝贝【算法赛】

问题描述

BeiBei 和 NingNing 这次带上 LinLin 一起玩博弈游戏，三人在一个含有$n$个结点的无向完全图上玩“斗地主”的游戏，三人按照 LinLin、BeiBei、NingNing 的顺序轮流进行各自回合的操作。

初始时，图中仅有一个棋子位于$1$号结点，LinLin 属于地主阵营，BeiBei 和 NingNing 属于农民阵营，每回合所执行的步骤如下：

1. 当前回合的选手，让棋子走一条还未被删除的边。若无法完成该操作，则当前选手所在的阵营判负，游戏结束。
2. 将当前回合选手走过的边永久删除掉。

LinLin 、BeiBei 和 NingNing 都想要各自所在的阵营获胜，三个人都足够聪明，请你判断最后游戏获胜的阵营。

输入格式

第一行，包含一个正整数$T(1\le T\le 10^5)$，表示测试用例的数量。

每个测试用例仅一行，包含一个正整数$n(3\le n\le 10^{18})$。

输出格式

对于每个测试用例，输出一行字符串表示最后的获胜者。

若地主阵营获胜，则输出 "LinLin" ，否则输出 "BeiBei & NingNing" 。

样例输入

1
3

样例输出

BeiBei & NingNing

T8. 学《数论》的贝贝【算法赛】

问题描述

贝贝立志要打败周三金，成为集美大学最强的数论选手，于是他向周三金发起了挑战，有如下方程：

$$(a+c)\times b=ac$$

其中$a,b,c$均为正整数，且$b$的大小已知。

贝贝认为求解该不定方程的解的数量对周三金来说太简单了，于是让他求解如下问题：

$$\sum_{(a+c)\times b=ac}\ \sum_{d\mid \max(a-b,1)}\varphi(d)\mu(\dfrac{\max(a-b,1)}{d})$$

但是周三金还是不到 1s 就秒了这题，于是他将这题丢给了聪明的你。

注：

• 其中“ $\mid$ “为整除符号，$d\mid n$表示$d$为$n$的约数。
• $\varphi(n)$ 表示欧拉函数，表示与$n$互质的数的个数。即$\varphi(n)=\sum_{i=1}^n [\gcd(n,i)=1]$，其中$\gcd(n,i)$表示$n$和$i$的最大公约数，而$[\quad]$为艾弗森括号，括号中的表达式为真时返回$1$，否则返回$0$。
• $\mu(n)$ 表示莫比乌斯函数，它的定义如下：
  • 若 $\exists d>1$且$d^{2} \mid n$，则$\mu (n)=0$；
  • 否则 $\mu(n) = (-1)^{\omega(n)}$，其中$\omega(n)$表示$n$的本质不同质因子个数。

输入格式

因为$b$的值可能会很大，故采用如下方式读入：

第一行，包含一个正整数$m(1\le m\le 100)$。

第二行，包含$m$个整数$b_1,b_2,\cdots b_m(1\le b_i\le 10^{18})$。

那么有$b=\prod_{i=1}^{m} b_i$，其中$\prod$表示连乘符号，即$b=b_1\times b_2\times \cdots \times b_m$。

输出格式

仅一行，包含一个整数，为题目所求答案。

由于这个值可能很大，故将答案取模$998244353$后输出。

样例输入

1
6

样例输出

12

T9. 学《树论》的贝贝【算法赛】

问题描述

给定一棵$n$个节点的树，按照$1\sim n$编号，每条边的边权为$w_i$，

• 当一条链恰好包含$k$条边时，我们约定其长度为$k$。

• 设某条链上所有边权按位与起来的值为$V$，那么且我们称这条链的幸运值$g$为：最大能整除$V$的二次幂$g=2^i$。

那么我们约定$f(k)$为：这棵树上所有恰好含$k$条边的链的幸运值$g$的最小值。

请计算$f(1),f(2),\cdots,f(n-1)$。

• 特别地，若树中不存在长度为$k$的链，则$f(k)=-1$。

输入格式

第一行，包含一个正整数$n(1\le n\le 10^5)$，表示树的结点数量。

接下来的$n-1$行，每行$3$个整数$u_i,v_i,w_i$，表示$u_i$和$v_i(1\le u_i,v_i\le n)$之间存在一条边权为$w_i(1\le w_i<2^{60})$的无向边。

数据保证任意一条链的所有边权按位与起来的值均大于$0$。

输出格式

共$n-1$行，第$i$行包含一个整数，表示$f(i)$的值。

样例输入

6
1 2 5
1 3 7
4 6 14
3 5 5
3 4 13

样例输出

1
1
1
4
-1