YLT C++ 4级 2025.09

N5758 [CIE 202509 四级 T1] 替换

题目描述

有一个包含 $N$ 个正整数 $A_1, A_2, \cdots, A_N$ 的数列 $A$。
接下来将进行 $Q$ 次操作：
在第 $i$ 次操作中，将数列中所有值为 $B_i$ 的元素替换为 $C_i$。
请针对每次操作（$1 \le i \le Q$），输出操作后数列 $A$ 的所有元素之和 $S_i$。

输入格式

第一行，一个整数 $N$；
第二行，$N$ 个整数 $A_1, A_2, ..., A_N$；
第三行，一个整数 $Q$；
接下来 $Q$ 行，每行两个整数 $B_i, C_i$。

输出格式

输出 $Q$ 行，每行一个整数 $S_i$，表示每次操作后的数列总和。
注意：$S_i$ 可能超出 $32$ 位整数范围。

样例

样例 1
输入：

4
1 2 3 4
3
1 2
2 4
3 4

输出：

11
15
16

样例 2
输入：

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

输出：

16
18
21
25
5

提示

【数据范围】

• $1 \le N, Q, A_i, B_i, C_i \le 10^5$，
• $B_i \ne C_i$。

N5759 [CIE 202509 四级 T2] 无法整除的数

题目描述

给定一个长度为 $N$ 的数列 $A$。
请计算满足以下条件的下标 $i$（$1 \le i \le N$）的数量：
对于任意 $j$（$1 \le j \le N$ 且 $i \ne j$），元素 $A_i$ 不能被 $A_j$ 整除。

输入格式

第一行，一个整数 $N$；
第二行，$N$ 个整数表示 $A_1, A_2, ..., A_N$。

输出格式

输出一个整数，表示满足条件的下标数量。

样例

样例 1
输入：

5
2 3 9 11 19

输出：

4

样例 2
输入：

10
11 18 45 28 8 19 89 86 2 4

输出：

5

提示

【数据范围】

• 所有输入均为整数
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^6$

N5760 [CIE 202509 四级 T3] 咖啡机

题目描述

一台自动咖啡机按以下规则接单：制作一杯咖啡需要 $c$ 秒，只有当前订单制作完成后，才能处理下一个订单。如果在制作期间，接到新订单，则做忽略处理。
有 $n$ 位顾客下单，其中第 $i$ 位顾客的下单时间为第 $t_i$ 秒，保证所有下单时间均不重复。
这台咖啡机最多能完成多少杯订单？

输入格式

第一行，两个整数表示 $n,c$；
第二行，$n$ 个整数表示 $t_1,t_2,t_3,...,t_n$。

输出格式

这台咖啡机最多能完成多少杯订单。

样例

样例 1
输入：

6 5
1 3 12 10 8 7

输出：

3

样例 2
输入：

3 2
0 2 4

输出：

3

样例 3
输入：

10 3
0 3 4 9 15 12 6 17 19 20

输出：

7

提示

【数据范围】

$1 \le n \le 100$
$1 \le c \le 1000$
$0 \le t_i \le 1000$

N5761 [CIE 202509 四级 T4] 字符数对

题目描述

给定一个由字符 $o$ 和 $x$ 组成的长度为 $N$ 的字符串 $S$。
请计算满足以下所有条件的整数对 $(l,r)$ 的数量：

• $1 \le l \le r \le N$；
• 在字符串 $S$ 的子串 $S[l..r]$（从第 $l$ 个字符到第 $r$ 个字符）中，同时包含 $o$ 和 $x$ 两种字符。

输入格式

第一行，一个整数 $N$；
第二行，一个字符串 $S$。

输出格式

输出满足条件的整数对的数量。

样例

样例 1
输入：

4  
oxxo
5

输出：

5

样例 2
输入：

7  
xoxooxx

输出：

19

提示

【数据范围】

• $1 \le N \le 10^{6}$；
• $S$ 仅由字符 $o$ 和 $x$ 组成。