Namomo Spring Camp 2022 Div1 每日一题记录 (Week 9)

发表于 2022-04-23 更新于 2024-07-02 分类于算法竞赛，题解本文字数： 2.3k 阅读时长 ≈ 8 分钟

Namomo Spring Camp 2022 Div1 每日一题记录 (2022.04.23-2022.04.29)

最小生成数

题目链接

3 s, 512 MB

题目描述

$n$ - $1$ 个点，从 $2$ 到 $n$, 点 $a$ 与点 $b$ 的边权为 $lcm(a,b)$, 求出 $n-1$ 个点的最小生成树

输入格式

第一行一个数字 $T$

接下来 $T$ 行 $1$ 个整数 $n$

输出格式

一个数，表示答案

样例输入

1
2
3

2
2
6

样例输出

1
2

0
26

数据规模

所有数据保证 $T , 2n 1e7 $

解题思路

复杂度

代码参考

Show code

数列

题目链接

1 s, 1024 MB

题目描述

小琪非常喜欢数列，因此她出了一道数列问题

有两个整数 $d,m$ , 找到这样的数列 $a$, 满足如下条件

数列 $a$ 的长度为 $n, n \ge 1$
$1 \le a_1 < a_2 < \quad ... \quad < a_n \le d$
定义数组一个长度为 $n$ 的数组 $c$: $c_1 = a_1$ , $\forall i > 1, c_i = c_{i-1} \oplus a_i$ , $\oplus$ 表示二进制异或。数组 $c$ 应该满足 $c_1 < c_2 < \quad ... \quad < c_n$ 的限制条件

请你求出满足条件的数列有多少个？由于结果较大，请输出答案模 $m$ 的结果

输入格式

第一行一个数字 $\quad t \quad (1 \le t \le 100)$ , 表示测试数据数

接下来 $t$ 行，每行 $2$ 个整数 $\quad d, m \quad (1 \le d, m \le 10^9)$

注意: $m$ 不一定是质数

输出格式

输出包括 $t$ 行，每行一个整数表示答案

样例输入

样例输出

1
2
3

17
23
29

数据规模

所有数据保证 $1\leq t \leq 100, 1 \leq d,m \leq 10^9$

解题思路

复杂度

代码参考

Show code

宝箱

题目链接

1 s, 1024 MB

题目描述

$X$ 坐标轴上有 $N$ 个钥匙和 $N$ 个宝箱，玩家初始位置为 $x = 0$, 每一步可以走到 $x + 1$ 或者 $x - 1$

当玩家到达一个有钥匙的位置时，他可以将钥匙捡起。当玩家到达一个有宝箱的位置时，他可以选择使用一个钥匙将宝箱打开

试求出玩家最少需要走多少步才能打开所有宝箱

注：同一个位置可以同时出现宝箱和钥匙，但同一位置不会出现超过一个宝箱或超过一个钥匙

输入格式

第一行一个正整数 $N$, 表示宝箱和钥匙的个数

接下来一行 $N$ 个正整数 $b_1, b_2, ... , b_n$. 其中 $b_i$ 表示宝箱 $i$ 的位置

第三行 $N$ 个正整数 $c_1, c_2, ... , c_n$. 其中 $c_i$ 表示钥匙 $i$ 的位置

输出格式

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

数据范围

对于所有数据，满足 $1 \leq N \leq 10^5$, $1 \leq b_i, c_i \leq 10^9$. 且保证 $b_1 < b_2 < ... < b_n$. $c_1 < c_2 < ... < c_n$

样例输入 1

1
2
3

4
1 6 7 12
3 5 10 11

样例输出 1

样例输入 2

1
2
3

2
1 2
1 1000000000

样例输出 2

1	1999999998

解题思路

复杂度

代码参考

Show code

【模板】最小瓶颈生成树 (数据加强版)

题目链接

2 s, 1024 MB

题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，每条边有一个权值，定义瓶颈路权值为某一条从点 $i$ 到 $j$ 的路径上的最大权值，有 $q$ 个询问，每次询问给出两个点 $(s,t)$, 求从 $s$ 到 $t$ 的最小瓶颈路权值

保证图联通

输入格式

第一行包含两个正整数 $n(1\leq n\le 10^5)$ 和 $m (1\leq m\leq \min(10^6, \frac{n \times (n-1)}{2})$, 表示点数和边数

第二行到第 $m+1$ 行包含三个整数 $x,y,d(0\leq d\leq 10^9)$, 表示 $x$ 和 $y$ 之间连有一条权值为 $d$ 的无向边

第 $m+2$ 包含一个正整数 $q(1\leq q\leq 10^6)$, 表示询问的次数，后面 $q$ 行每行两个正整数 $s,t(1\leq s, t\leq n)$, 分别表示起点和终点

输出格式

对于每次询问，每行输出一个整数，表示最小的瓶颈路权值

注意：由于本道题输入输出规模过大，请注意 IO 优化

样例输入

样例输出

解题思路

复杂度

代码参考

Show code

Mouse Hunt (CF1027D)

题目链接

1 s, 128 MB

题目描述

有编号从 $1$ 开始的 $n$ 个房间，有一只老鼠将会出现在某个房间中

当老鼠在某一时刻位于房间 $i$ $(1 \leq i \leq n)$ 时，它将在下一时刻抵达房间 $p_i$ (如果 $i = p_i$ 则代表老鼠不会离开 $i$ 房间)

已知在第 $i$ 个房间布置捕鼠夹的价格是 $w_i$, 求最少需要花费多少能够使得无论老鼠从哪个房间出现，都会抵达有老鼠夹的房间

输入格式

第一行输入一个整数 $n$ $(1 \leq n \leq 200000)$

第二行输入 $n$ 个整数 $w_i$ $(1 \leq w_i \leq 10000)$ 为在第 $i$ 个房间布置捕鼠夹的成本

第三行输入 $n$ 个整数 $p_i$ $(1 \leq p_i \leq n)$ 为在 $i$ 房间的老鼠即将抵达的房间编号

输出格式

输出一个整数，为满足条件的最小花费

输入样例 1

1
2
3

5
1 2 3 2 10
1 3 4 3 3

输出样例 1

输入样例 2

1
2
3

4
1 10 2 10
2 4 2 2

输出样例 2

输入样例 3

1
2
3

7
1 1 1 1 1 1 1
2 2 2 3 6 7 6

输入样例 3

样例解释

在第一组样例里可以选择房间 1 和房间 4 布置捕鼠夹。如果老鼠从房间 1 出现，则会被房间 1 的捕鼠夹捕获，否则会被房间 4 的捕鼠夹捕获

在第二组样例里可以在房间 2 布置捕鼠夹，老鼠从任意房间出现，都会被房间 2 的捕鼠夹捕获

这是第三组样例中老鼠可能的行动轨迹:

1→2→2→…;
2→2→…;
3→2→2→…;
4→3→2→2→…;
5→6→7→6→…;
6→7→6→…;
7→6→7→…;

所以可以在房间 2 和房间 6 布置捕鼠夹

解题思路

复杂度

代码参考

Show code

矩形划分

题目链接

1 s, 1024 MB

题目描述

给定一个左下角位于 $(0 , 0)$ 右上角位于 $(n , m)$ 的矩形，矩形的四条边都与坐标轴平行，你需要将它划分成尽可能多的块数

划分的规则如下:

每次会给出两个点 $p , q$ , 你需要在点 $p , q$ 之间连一条线来划分矩形，保证 $p , q$ 分别在矩形的一组对边上，即要么分别在左右边界上，要么分别在上下边界上
连的线并不要求是直线，可以是曲线，但不能与自己有交点，不能与矩形边界有除 $p , q$ 以外的交点
两条线最多有一个交点，如果有交点，那么一定是在交点处交叉
线的两端在同一组对边上的线互不相交
保证给出的所有点两两不同

输出最多可以划分多少块

输入格式

第一行两个整数 $n,m$ , 含义如题面所示. $(1 \leq n , m \leq 10^9)$

第二行两个整数 $x , y$ , 表示有 $x$ 对位于左右边界的点和 $y$ 对位于上下边界的点. $(1 \leq x \leq min(m + 1 , 10^5) , 1 \leq y \leq min(n + 1,10^5))$

接下来 $x$ 行，每行两个整数 $a , b$ 分别表示位于左边界和右边界的点的纵坐标. $(0 \leq a , b \leq m)$

接下来 $y$ 行，每行两个整数 $c , d$ 分别表示位于下边界和上边界的点的横坐标. $(0 \leq c , d \leq n)$

输出格式

输出一行一个整数，表示最大的划分块数

样例输入

样例输出

样例解释

按照上图的划分方式可以得到最多的块数，13 块

解题思路

复杂度

代码参考

Show code

等差数列 (51Nod 1055)

题目链接

1 s, 1024 MB

题目描述

给定一个大小为 $n$ 的集合 $\{S\}$, 你可以从中挑选若干个数组成等差数列，求最长的等差数列长度

输入描述

一行一个整数 $n\leq 5000$

接下来一行 $n$ 个整数 $|S_i| <{2^{31}} $, 描述集合 $\{S\}$ 中的元素

输出描述

一行一个整数，描述最长的等差数列的长度

样例输入

1 2	10 14 1 3 5 6 8 9 10 12 13

样例输出

样例解释

等差数列包括 (仅包括两项的不列举)

1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14

其中 6 8 10 12 14 最长，长度为 5

原题链接

戳我

解题思路

复杂度

代码参考

Show code