YLT C++ 7级 2025.09

N5770 [CIE 202509 七级 T1] 数字之和

题目描述

给定一个数字字符串 $n$，定义一次操作为：移除字符串中一个非空子串，并将剩余部分拼接形成新数字。
求所有可能操作方案生成的新数字之和，结果对 $10^{9}+7$ 取模。

输入格式

一行字符串 $n$。

输出格式

一个整数，表示所有方案生成数字之和取模后的结果。

样例

样例 1
输入：

1003

输出：

339

样例 2
输入：

123

输出：

52

提示

$1 \le \lvert n \rvert \le 10^{5}$，$\lvert n \rvert$ 表示字符串长度。

N5771 [CIE 202509 七级 T2] 花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换！
最初，所有 $N$ 辆花车排成一行，花车 $i$ 位于第 $i$ 位。变换程序由 $K$ 个位置对 $(a_1,b_1),(a_2,b_2),\ldots,(a_K,b_K)$ 描述。表演过程中：

• 第 $1$ 分钟：位置 $a_1$ 与 $b_1$ 的花车交换位置。
• 第 $2$ 分钟：位置 $a_2$ 与 $b_2$ 的花车交换位置。
• $\ldots$
• 第 $K$ 分钟：位置 $a_K$ 与 $b_K$ 的花车交换位置。
• 第 $K+1$ 分钟：重新从 $(a_1,b_1)$ 开始交换（即位置 $a_1$ 与 $b_1$ 交换）。
• 第 $K+2$ 分钟：位置 $a_2$ 与 $b_2$ 交换。
• 如此无限循环……
  请计算每辆花车在整个表演过程中能到达的不同位置数量。

输入格式

第一行输入 $N,K$。
接下来 $K$ 行每行包含 $a_i,b_i$（$1 \le a_i < b_i \le N$）。

输出格式

输出 $N$ 行，第 $i$ 行为花车 $i$ 能到达的不同位置数量。

样例

样例 1
输入：

5 4
1 3
1 2
2 3
2 4

输出：

4
4
3
4
1

提示

【样例解释】

• 花车 $1$ 可到达位置 $\{1,2,3,4\}$。
• 花车 $2$ 可到达位置 $\{1,2,3,4\}$。
• 花车 $3$ 可到达位置 $\{1,2,3\}$。
• 花车 $4$ 可到达位置 $\{1,2,3,4\}$。
• 花车 $5$ 始终在位置 $5$（未移动）。

【数据范围】

• $1 \le K \le 2 \times 10^{5}$
• $2 \le N \le 10^{5}$

N5772 [CIE 202509 七级 T3] 公平

题目描述

有多干所精英学院和 $N$ 名天才学员（编号 $1$ 到 $N$）。
每名学员 $i$ 拥有能力值 $A_i$ 和初始所属学院 $B_i$。
联盟定期进行学员调院操作（共 $Q$ 次）：第 $j$ 次操作将学员 $C_j$ 调到学院 $D_j$。
联盟公平指数定义为：对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。
请计算每次调院操作后的联盟公平指数。

输入格式

第一行：$N$ $Q$。
接下来 $N$ 行：每行 $A_i$ $B_i$，表示学员 $i$ 的能力值和初始学院。
接下来 $Q$ 行：每行 $C_j$ $D_j$，表示将学员 $C_j$ 调到学院 $D_j$。

输出格式

$Q$ 行：每行一个整数，表示每次操作后的公平指数。

样例

样例 1
输入：

6 3  
8 1  
6 2  
9 3  
1 1  
2 2  
1 3  
4 3  
2 1  
1 2

输出：

6  
2  
6

样例 2
输入：

2 2  
4208 1234  
3056 5678  
1 2020  
2 2020

输出：

3056  
4208

提示

【数据范围】

• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le C_j \le N$
• $1 \le B_i, D_j \le 2 \times 10^5$
• 输入均为整数。
  每次转园操作会改变所属学院。

N5773 [CIE 202509 七级 T4] 树总距求解

题目描述

给定一棵包含 $N$ 个顶点的树。顶点编号为 $1$ 至 $N$，第 $i$ 条边（$1 \le i \le N-1$）连接顶点 $a_i$ 与顶点 $b_i$。
对于树中任意两个顶点 $u$ 和 $v$（满足 $u < v$），定义距离 $d(u,v)$ 为连接 $u$ 和 $v$ 的简单路径上的边的数量。
请计算所有满足 $u < v$ 的顶点对 $(u,v)$ 的距离 $d(u,v)$ 的总和。

输入格式

第一行，一个整数表示 $N$。
接下来的 $N-1$ 行，每行两个整数 $a_i, b_i$。

输出格式

输出所有满足 $u < v$ 的顶点对 $(u,v)$ 的距离 $d(u,v)$ 的总和。

样例

样例 1
输入：

3
1 2
2 3

输出：

4

样例 2
输入：

5
1 2
1 3
1 4
1 5

输出：

16

提示

【数据范围】

• $2 \le N \le 10^{5}$
• $1 \le a_i, b_i \le N$