YLT C++ 8级 2026.06

N5854 [CIE 202606 八级 T1] 产品研发

题目描述

一家公司正在研发一款新产品。该产品共有 $K$ 项关键性能指标，初始时所有指标均为 $0$。公司的最终目标是让每一项指标都不低于 $P$。
研发团队提出了 $N$ 个独立的改进方案。第 $i$ 个方案一旦实施，会同时为第 $j$ 项指标（$1\le j\le K$）带来 $A_{i,j}$ 的提升，但实施该方案需要投入 $C_i$ 的研发成本。每个方案最多只能执行一次。
你需要判断：是否存在一系列方案的选择，使得所有指标均达到或超过 $P$？如果存在，请给出最小的总研发成本；如果不存在，输出 $-1$。

输入格式

第一行，三个整数 $N,K,P$，分别表示方案数量、指标数量和目标阈值。
接下来 $N$ 行，每行 $K+1$ 个整数 $C_i,A_{i,1},A_{i,2},\ldots,A_{i,K}$，分别表示第 $i$ 个方案的成本, 以及执行后各指标的提升值。

输出格式

输出一个整数，表示达成目标所需的最小总成本。若无法达成，输出 $-1$。

样例

样例 1
输入：

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

输出：

9

样例 2
输入：

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

输出：

-1

提示

数据范围：

• $1 \le N \le 100$，
• $1 \le K,P \le 5$，
• $0 \le A_{i,j} \le P$，
• $1 \le C_i \le 10^9$。

N5855 [CIE 202606 八级 T2] 传话对象

题目描述

在一个公司里，有 $n$ 名员工，编号 $1$ 到 $n$。每名员工都有一个“传话对象”，即第 $i$ 名员工只会把消息告诉第 $t_i$ 名员工（允许告诉自己）。现在，从每名员工出发，依次沿着传话对象传递消息，可以证明经过有限步后，消息一定会回到一个已经传过消息的员工。
请你分别计算：从第 $i$ 名员工开始，需要传递多少步后，才会第一次遇到一个已经传过消息的员工。

输入格式

第一行，一个整数 $n$。
第二行，$n$ 个整数 $t_1,t_2,\ldots,t_n$，表示第 $i$ 名员工的传话对象。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示从第 $i$ 名员工出发的答案。

样例

样例 1
输入：

4
2 1 1 4

输出：

2
2
3
1

提示

数据范围：
$1 \le n \le 5\times10^5$。

N5856 [CIE 202606 八级 T3] 能量护盾

题目描述

在一处被宇宙射线笼罩的星域中，你驾驶着一艘小型探索飞船，需要从坐标 $(x_s,y_s)$ 航行到坐标 $(x_t,y_t)$。
飞船可以以速度 $1$ 向任意方向移动，自身视为一个点。
星域中分布着 $N$ 个圆形能量护盾，第 $i$ 个护盾的圆心为 $(x_i,y_i)$，半径为 $r_i$。护盾之间可能相互重叠，也可能存在包含关系。
飞船一旦进入某个护盾的内部，就能免受宇宙射线的伤害。若一个点不在任何护盾内部，则飞船会持续受到宇宙射线的照射。
你的目标是：在从起点到终点的航行过程中，尽可能减少受到宇宙射线照射的总时间。
请你计算这个最小照射时间。

输入格式

第一行，四个整数 $x_s,y_s,x_t,y_t$，分别表示起点和终点的坐标。
第二行，一个整数 $N$，表示圆形护盾的数量。
接下来 $N$ 行，每行三个整数 $x_i,y_i,r_i$，描述第 $i$ 个护盾的圆心坐标和半径。

输出格式

输出一个实数，表示受到宇宙射线照射的最小时间，保留 $10$ 位小数。

样例

样例 1
输入：

-2 -2 2 2
1
0 0 1

输出：

3.6568542495

样例 2
输入：

-2 0 2 0
2
-1 0 2
1 0 2

输出：

0.0000000000

样例 3
输入：

4 -2 -2 4
3
0 0 2
4 0 1
0 4 1

输出：

4.0000000000

提示

数据范围：

• $-10^9 \le x_s,y_s,x_t,y_t \le 10^9$，
• $(x_s,y_s)\ne(x_t,y_t)$，
• $1 \le N \le 1000$，
• $-10^9 \le x_i,y_i \le 10^9$，
• $1 \le r_i \le 10^9$。

N5857 [CIE 202606 八级 T4] 图书馆

题目描述

某城市有 $n$ 条东西向街道和 $n$ 条南北向街道，构成一个 $n\times n$ 的街区网格。
每个交叉路口处恰好建有一座图书馆，且每一行、每一列的交叉路口都恰好有一座图书馆。
已知第 $i$ 座图书馆的坐标 $(x_i,y_i)$ 表示它位于第 $x_i$ 条东西向街道与第 $y_i$ 条南北向街道的交汇处。
城市规划师想要知道：有多少个正方形区域（由连续的若干条东西向街道和连续的若干条南北向街道围成），使得该区域内每一行、每一列也恰好各有一座图书馆？

输入格式

第一行，一个整数 $n$。
第二行，$n$ 个整数 $x_1,x_2,\ldots,x_n$，表示第 $i$ 座图书馆的东西向街道编号。
第三行，$n$ 个整数 $y_1,y_2,\ldots,y_n$，表示第 $i$ 座图书馆的南北向街道编号。
输入保证：$1\le x_i,y_i\le n$，且每行每列恰好只有一座图书馆。

输出格式

输出一个整数，表示满足条件的正方形区域个数。

样例

样例 1
输入：

7
1 2 3 4 5 6 7
4 3 1 6 2 5 7

输出：

10

提示

数据范围：

• $1 \le n \le 10^5$，
• $1 \le x_i,y_i \le n$。
• 输入保证每行每列恰好有一座图书馆。