题目名称	育华义卖	育华选购	育华文创	育华调查	育华灯控	育华演习
题目类型	传统型
目录	charity	dessert	craft	survey	light	drill
可执行文件名
输入文件名	charity.in	dessert.in	craft.in	survey.in	light.in	drill.in
输出文件名	charity.out	dessert.out	craft.out	survey.out	light.out	drill.out
每个测试点时限	2.0 秒
内存限制	512 MiB	512 MiB	512 MiB	512 MiB	512 MiB
测试点数目	20
测试点是否等分	是

T1

育华义卖

题目描述

育华学校举办校园义卖活动。 学校一共准备了 $N$ 种义卖代金券。对于第 $i$ 种代金券，单张的价值为 $A_i$ 元，一共有 $B_i$ 张。

现在有一名同学想要恰好凑出总价值 $X$ 元去购买义卖商品。 代金券不能找零，可以选择部分代金券完全不使用，每张代金券最多使用一次。 请判断这名同学能不能从这些代金券里面挑选若干张，使得总价值恰好等于 $X$。

输入格式

第一行两个整数 $(N,X)$。 接下来 $N$ 行，每行两个整数 $A_i,B_i$。

N X
A_1 B_1
A_2 B_2
...
A_N B_N

输出格式

若可以凑出恰好 $X$ 元，输出 Yes；否则输出 No。

样例输入 #1

2 19
2 3
5 6

样例输出 #1

Yes

样例输入 #2

2 18
2 3
5 6

样例输出 #2

No

样例输入 #3

3 1001
1 1
2 1
100 10

样例输出 #3

Yes

样例解释

样例1：选取2张价值2元的代金券，3张价值5元的代金券，$2\times 2 +5\times3 =19$，可以凑出。 样例2：无论怎样挑选代金券，都无法恰好凑出18元。 样例3：允许某些代金券一张也不选用。

数据范围

测试点编号	分值	$N$	$X$	$A_i$	$B_i$	特性
1-1	5	$(N=1)$	$\le 100$	$\le 100$	$\le 50$	仅1种代金券
2-2		$\le 10$		$\le100$	$\le50$
3-4	10	$\le20$	$\le 1000$
5-8	20	$\le50$	$\le 10^4$		$B_i=1$	0‑1背包
9-14	30				$\le50$
15-20			$X=10^4$

• $1 \le N \le 50$
• $1 \le X \le 10^4$
• $1 \le A_i \le 100$
• $1 \le B_i \le 50$
• 保证所有 $A_i$ 互不相同。

T2

育华选购

题目描述

育华食堂推出多款甜品，一共有 $N$ 份甜品。 第 $i$ 份甜品的品类为 $F_i$，美味值为 $S_i$（保证 $S_i$ 为偶数）。

你准备从中挑选两份甜品品尝。总满意度计算规则如下： 设两份甜品的美味值为 $(s,t)$，满足 $s \ge t$。

• 如果两份甜品品类不一样：总满意度 = $s + t$
• 如果两份甜品品类一样：总满意度 = $s + \dfrac{t}{2}$

请求出能够得到的最大总满意度。

输入格式

第一行一个整数 $N$。 接下来 $N$ 行，每行两个整数 $F_i,S_i$。

N
F_1 S_1
F_2 S_2
...
F_N S_N

输出格式

输出最大总满意度。

样例输入 #1

4
1 4
2 10
2 8
3 6

样例输出 #1

16

样例输入 #2

4
4 10
3 2
2 4
4 12

样例输出 #2

17

样例解释

样例1：选择第2份（品类2，美味10）与第4份（品类3，美味6），品类不同，总满意度 $(10+6=16)$，这是最优答案。 样例2：选择第1份、第4份，两份同为品类4，美味值 $(12,10)$，总满意度 $12+\dfrac{10}{2}=17$。

数据范围

测试点编号	分值	$N$	特性
1-2	10	$\le 100$
3-4		$\le 2000$
5-6		$\le 10^5$	所有甜品品类全部互不相同
7-8
9-20	60	$\le 3\times10^5$

• $2 \le N \le 3\times 10^5$
• $1 \le F_i \le N$
• $2 \le S_i \le 10^9$
• $S_i$ 保证是偶数。

T3

育华文创

题目描述

育华文创社团要拼接出目标文案 $T$。 一开始手里的文本 $S$ 为空。

一共有编号 $1,2,\dots,N$ 的 $N$ 个素材袋。 第 $i$ 个素材袋里面装有 $A_i$ 段文本素材：$S_{i,1},S_{i,2},\dots,S_{i,A_i}$。

你需要按顺序处理 $1$ 到 $N$ 每一个素材袋，对每个袋子二选一执行操作：

• 花费 $1$ 社团积分：从该袋子中挑选恰好一段素材，接在当前文本 $S$ 的末尾。
• 不花费积分：什么都不做。

要求处理完所有袋子之后，拼接得到的文本 $S$ 完全等于目标文案 $T$。 求需要消耗的最少社团积分；如果无论如何都无法拼出 $T$，输出 -1。

输入格式

第一行给出目标串 $T$ 和整数 $N$。 之后依次给出每一个素材袋的信息： 对于第 $i$ 个袋子，先给整数 $A_i$，随后跟随 $A_i$ 个字符串，代表袋内的素材。

T N
A_1 S_{1,1} S_{1,2} … S_{1,A_1}
A_2 S_{2,1} S_{2,2} … S_{2,A_2}
……
A_N S_{N,1} S_{N,2} … S_{N,A_N}

输出格式

输出达成目标需要的最少积分，无法完成输出 -1。

样例输入 #1

abcde 3
3 ab abc abcd
4 f c cd bcde
2 e de

样例输出 #1

2

样例输入 #2

abcde 3
2 ab abc
3 f c bcde
1 e

样例输出 #2

-1

样例输入 #3

aaabbbbcccc 6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

样例输出 #3

4

样例解释

样例1：

• 处理第1个素材袋，选取素材abc，花费1积分，此时 $S=\texttt{abc}$。
• 处理第2个素材袋，什么都不做。
• 处理第3个素材袋，选取素材de，花费1积分，此时 $S=\texttt{abcde}$。 总花费2积分，可以完成任务。

样例2：无论怎么选取素材，都无法拼出目标字符串abcde，输出 -1。

数据范围

测试点编号	分值	$T$	$N$	特性
1-2	10	$\le 10$
3-6	20	$\le 50$
7-10		$\le 100$		每个袋子只有1个字符串
11-20	50

• $1\le |T| \le 100$
• $1\le N \le 100$
• $1\le A_i \le 10$
• 每段素材字符串长度 $1\sim10$，全部由小写英文字母构成。

T4

育华调查

题目描述

育华社团在做成员数据统计。给定正整数 $(N,K,M)$。

对于每一个 $x$（$1 \le x \le N$），请你求解如下问题：

构造一个非空多重集合，集合里面的元素只能取自 ${1,2,\dots,N}$； 对于集合内每一个数字，它出现的次数满足：大于等于 $0$，小于等于 $K$。

求：满足条件，并且集合元素的平均值恰好等于 $x$ 的多重集合总数量，答案对质数 $M$ 取模。

依次输出 $(x=1),2,\dots,N$ 对应的答案。

输入格式

第一行三个整数 $(N,K,M)$。

N K M

输出格式

输出一行 $N$ 个整数 $c_1,c_2,\dots,c_N$。 其中 $c_x$ 代表平均值等于 $x$ 的合法非空多重集合数目对 $M$ 取模的值。

样例输入 #1

3 1 998244353

样例输出 #1

1 
3 
1

样例输入 #2

1 2 1000000007

样例输出 #2

2

样例输入 #3

10 8 861271909

样例输出 #3

8 
602 
81827 
4054238 
41331779 
41331779 
4054238 
81827 
602 
8

样例解释

样例1：每个数字最多出现1次，多重集合不能为空。

• $(x=1)$：仅 ${1}$，共 $1$ 种。
• $(x=2)$：${2},{1,3},{1,2,3}$，共 $3$ 种。
• $(x=3)$：仅 ${3}$，共 $1$ 种。

样例2：数字 $1$ 最多出现 $2$ 次；合法集合：${1},{1,1}$，一共 $2$ 种。

数据范围

测试点编号	分值	$N$	$K$	特性
1-2	10	$\le 5$	$\le5$
3-5	15	$\le 30$	$\le30$
6-9	20	$\le100$	$\le1$	每个元素最多选一次
10-13			$\le2$
14-20	35		$\le100$

• $1 \le N,K \le 100$
• $10^8 \le M \le 10^9+9$
• $M$ 保证为素数

T5

育华灯控

题目描述

育华教室有 $n$ 盏电灯。 初始状态下，所有电灯全部处于关闭状态（记为 $a_i=0$）。

我们有一份理想目标状态数组 $b$，$b_i\in{0,1}$，代表第 $i$ 盏灯希望达到的状态，$1$ 代表打开，$0$ 代表关闭。

现在手里一共有 $q$ 种可选操作，每种操作对应一个区间 $([(l,r)])$：执行该操作，会把编号 $l\sim r$ 的所有电灯强制打开（置为1）。 每个操作可以选择执行或者不执行；操作可以选任意多个，顺序不影响最终结果。

执行若干操作之后，统计有多少盏灯实际状态与目标状态不一致。请求出这个不一致数量的最小值。

输入格式

第一行一个整数 $n$，代表灯的数量。 第二行 $n$ 个整数，为目标数组 $b_1,b_2,\dots,b_n$。 第三行一个整数 $q$，代表可选操作的数量。 接下来 $q$ 行，每行两个整数 $(l,r)$，代表一次可选的区间置1操作。

n
b_1 b_2 … b_n
q
l_1 r_1
l_2 r_2
……
l_q r_q

输出格式

输出一个整数：操作完成后，实际灯光和目标灯光不一致位置的最小数目。

样例输入 #1

3
1 0 1
1
1 3

样例输出 #1

1

样例输入 #2

3
1 0 1
2
1 1
3 3

样例输出 #2

0

样例输入 #3

3
1 0 1
2
1 1
2 3

样例输出 #3

1

样例输入 #4

5
0 1 0 1 0
1
1 5

样例输出 #4

2

样例输入 #5

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7

样例输出 #5

3

样例输入 #6

15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13

样例输出 #6

5

样例输入 #7

10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9

样例输出 #7

1

样例解释

样例1： 可选操作只有把 $([1,3])$ 全部置1。执行后灯状态为 $([1,1,1])$。 目标 $(b=([1,0,1]))$，第2盏灯不一致，总代价为1。

样例2： 选择操作 $([1,1])$、$([3,3])$。灯光变为 $([1,0,1])$，与目标完全匹配，不一致数量为0。

数据范围

测试点编号	分值	$n$	$q$	特性
1-2	10	$\le 100$
3-4		$\le 2000$
5-6		$\le 10^5$		所有操作左端点均为1
7-8				所有操作右端点均为n
9-10
11-12				操作区间互不相交
13-14		$\le 2\times10^5$		$b_i$ = 0,1,0,1...
15-20	30

• $1\le n,q \le 2\times 10^5$
• $1\le l_i \le r_i \le n$
• 所有给出的 $[l_i,r_i]$ 互不相同。

T6

育华演习

题目背景

育华社团开展模拟演习训练任务。

题目描述

有 $n$ 名社团成员排成一整排。初始时第 $i$ 名成员的耐久值为 $a_i$。

你可以进行若干轮演习攻击，也可以一轮都不执行。 每一轮攻击可以选定一段连续区间 $([l,r])$，将区间内每名成员的耐久值减去 $1$；每进行一轮攻击需要消耗 $m$ 点社团经费。

全部攻击结束之后： 如果第 $i$ 名成员耐久值 $\le 0$，你可以获得 $b_i$ 的演习积分。注意积分只会获取一次；受演习设定影响，$b_i$ 有可能是负数。

设一共执行了 $k$ 轮攻击，攻击结束后第 $i$ 名成员剩余耐久为 $c_i$。令 $p_i=1$ 当且仅当 $c_i \le 0$，否则 $p_i=0$。 你需要最大化： $\left(\sum_{i=1}^n p_i \times b_i\right) - m\times k$ 只输出这个总收益的最大值即可。

输入格式

本题有多组测试数据。 第一行一个正整数 $T$，代表数据组数。

每组数据： 第一行两个整数 $(n,m)$，成员数量，单次攻击消耗的经费。 之后 $n$ 行，每行两个整数 $a_i,b_i$，代表第 $i$ 位成员的初始耐久值、击败后获得的演习积分。

T
n m
a_1 b_1
a_2 b_2
……
a_n b_n
……（多组数据）

输出格式

对每组测试用例输出一行一个整数，表示总收益的最大值。

样例输入 #1

3
5 1
1 3
2 5
1 4
3 3
5 1
3 2
1 5
1 -100
1 5
3 2
1 5
1 -1
1 5

样例输出 #1

12
6
7

样例解释

第一组数据最优方案：执行3轮攻击，分别选取区间 $([1,5],[2,4],[4,4])$。 攻击结束后耐久序列 $(0,0,-1,0,4)$。 获得积分：$b_1+b_2+b_3+b_4=15$，总经费消耗 $3\times 1=3$，总收益 $15-3=12$。

第二组数据最优方案：执行2轮攻击，选取 $([1,1])$、$([3,3])$。

第三组数据最优方案：执行1轮攻击，选取 $([1,3])$。

数据范围

$\sum n$ 表示一个测试点内全部测试数据的 $n$ 之和。

• $1\le T \le 5\times 10^5$
• $1\le n,\sum n \le 5\times 10^5$
• $1\le m \le 10^9$
• $1\le a_i \le 10^9$
• $-10^9 \le b_i \le 10^9$

共20个测试点，每个测试点分值相等，总分100分，单测试点5分。

测试点编号	分值	$\sum n \le$	特殊性质
$1$	$5$	$5\times10^5$	A
$2\sim4$	$15$	$5,000$	B
$5\sim8$	$20$		无
$9\sim12$		$10^5$
$13\sim17$	$25$	$2\times 10^5$
$18\sim20$	$15$	$5\times 10^5$

特殊性质A：所有 $b_i\ge 0$。 特殊性质B：所有 $a_i \le (5,000)$。