PDF《WC2018 模拟赛》

WC2018 模拟赛 Niro BC January 27,

2018 题目标题 诗歌 猫咪 花朵 源代码文件名 poem.

cpp/c/pas cat.cpp/c/pas flowers.cpp/c/pas 输入文件名 poem.in cat.in flowers.in 输出文件名 poem.out cat.out flowers.out 时间限制 2s 2s 6s 空间限制 512M 512M 512M 是否有部分分 否否否题目类型 传统 传统 传统 比较方式 传统 传统 传统 C 语言编译命令 gcc -o %s %s.c -O2 C++ 编译命令 g++ -o %s %s.cpp -O2 Pascal 编译命令 fpc %s.pas -O2 注意事项: ? 评测环境为 Ubuntu 16.04 LTS,64 位,Lemon. ? 评测使用的编译器为 gcc/g++ 4.8.5,fpc 3.0.0. ? 我的题目十分简单,比赛期间若提前 AK 离场,请不要过于高调,以免 影响其他选手的心态,谢谢合作.

1 Problem A : 诗歌 (poem) 题目描述 小F是一个爱写诗的小姑娘. "我能看一看你写的诗吗? " "看吧,别念出来哦,我会害羞的. " 小F慵懒地坐在午后的阳光下,她在写诗,可是似乎没有什么灵感. 她用手指勾勒着远方绵延的山,就写关于远方的诗吧. 远方的山总共有 N 个山峰,从左往右第 i 个山峰有一个高度 Hi.小F认为一个三元组 (i, j, k) 可以写成一首诗,当且仅当

1 ≤ i < j < k ≤ N 且Hi ? Hj = Hj ? Hk. 小F和大 F 生活的国家――Fairy 国地形十分奇特,保证 H1...N 一定是一 个1...N的排列. 小F想写诗给大 F 看,但是不知道自己能不能写成,于是她想问问你. 输入格式 第1行1个正整数 N,表示山峰的数量. 第2行N个正整数 H1...N ,表示从左往右每座山峰的高度,保证是个

1 . . . N 的排列. 输出格式

1 行1个字符串 YES 或NO,表示小 F 能否写出一首诗,即是否存在三元组 (i, j, k) 满足

1 ≤ i < j < k ≤ N 且Hi ? Hj = Hj ? Hk. 输入样例

1 4

1 3

4 2 输出样例

1 NO 样例解释

1 不存在符合条件的三元组.

2 输入样例

2 5

1 5

2 4

3 输出样例

2 YES 样例解释

2 有2个符合条件的三元组. 第1个是 (1, 3, 5),此时 Hi = 1, Hj = 2, Hk = 3. 第2个是 (2, 4, 5),此时 Hi = 5, Hj = 4, Hk = 3. 所以此时符合条件的三元组存在,应当输出 YES. 数据范围 对于所有数据,保证

3 ≤ N ≤

3 *

105 . 下表为各个 Subtask 的额外限制与得分,空格表示该项无额外限制.你只有通 过一个 Subtask 的所有数据才能得到该 Subtask 的分. Subtask 编号 N 特殊限制 分值

1 ≤

300 19

2 ≤

3000 22

3 59

3 Problem B : 猫咪 (cat) 题目描述 大F想养猫. "你喜欢小猫咪吗? " "喵. " "你变成猫了吗? " "喵! " 大F喜欢小猫咪,大F想养很多很多小猫咪,但是大 F 的想象力十分匮乏, 她希望小 F 来帮她为猫咪们取名字. 小F也喜欢小猫咪,小F也想养许多许多小猫咪,但是小 F 有强迫症,如 果养了 K 只猫咪,名字分别是非空字符串 S1, S2, . . . SK,她希望对于所有的

2 ≤ i ≤ K,Si 是Si?1 的双子串.另外,小F还希望 S1 是她自己给定的字符 串T的子串. 诶,我们刚刚提到了双子串.字符串 A 被称作 B 的双子串,意思是说, A 作为 B 的子串,在B中的不同位置出现了至少

2 次.比如说,ABC 是ZZABCZZABCZZ 的双子串,ABA 是ABABA 的双子串(这里的两次出现有 重叠部分,这是允许的) ,而AAB 不是 AABAB 的双子串. 小F想养尽量多的猫咪,所以小 F 想要找到尽量大的 K,使得存在 S1, S2,SK 满足条件. 输入格式 一行一个字符串 T,仅含小写字母. 输出格式 一个整数,可能的 K 的最大值. 输入样例

1 qaqaqzz 输出样例

1 3

4 样例解释

1 S1='qaqaqzz' S2='qaq' S3='q' 输入样例

2 dabcabcabcabca 输出样例

2 5 样例解释

2 S1='abcabcabcabca' S2='abcabcabca' S3='abcabca' S4='abca' S5='a' 输入样例

3 abracadabra 输出样例

3 3 样例解释

3 S1='abracadabra' S2='abra' S3='a' 数据范围 对于所有数据,保证

1 ≤ N = |T| ≤

2 *

105 ,S 仅含小写字母. 下表为各个 Subtask 的额外限制与得分,空格表示该项无额外限制.你只有通 过一个 Subtask 的所有数据才能得到该 Subtask 的分.

5 Subtask 编号 N 特殊限制 分值

1 ≤

50 5

2 ≤

4000 24

3 当K取到最大值时,存在一种 S1...K 的取法使

17 得对于所有

1 ≤ i ≤ K,Si 都是 T 的前缀

4 54

6 Problem C : 花朵 (flowers) 题目描述 小F的生日还有一个多月,大F早早地准备起了礼物. "你想要什么礼物呀?嗯... 要不要好吃的? " "才不要呢,我想要好看的花,永远不会凋谢的花. " 小F和大 F 一起生活的国家――Fairy 国,可以抽象成一棵 N 个节点的树, 每个节点就是一个城市,编号为

1 . . . N. 大F要游历各个城市,为心爱的小 F 寻找好看的花. Fairy 国的每个城市都有一座山,山上有恰好一朵永远不会凋谢的花,编号 为i的城市的花的美丽值为 Bi.大F要在 N 个城市中选出恰好 M 个,并摘 来这 M 个城市中的 M 朵花送给小 F.可是呢,如果树上的一条边连接的两个 城市的花都被摘去,这条边就会塌陷,Fairy 国就会陷入分裂,大F作为一个善 良的人,不希望这样的情况发生.所以,一种摘法合法,当且仅当对于每条边, 这条边相连的两个节点的花不被同时摘去. 大F希望小 F 快乐,小F的快乐程度将是摘来的 M 朵花的美丽程度的积. 大F今天闲着没事,想要求出对于所有合法的摘法,小F的快乐程度之和对

998244353 取模的结果. 输入格式 第1行2个正整数 N 和M,表示节点的个数与大 F 要为小 F 摘的花的朵数. 第2行N个整数 B1...N ,表示 N 朵花的美丽程度. 接下来 N ?

1 行,每行两个正整数,描述树上的一条边,保证形成一棵树. 输出格式

1 个整数,表示对于所有合法的摘法,小F的快乐程度之和对

998244353 取模 的结果. 输入样例

1 5

3 3

5 4

8 1

1 1

2 1

3 2

4 2

5 7 输出样例

1 616 样例解释

1 有2种选法,选的点集分别是 {1, 4, 5} 和{3, 4, 5},所以答案是

3 *

8 *

11 +

4 *

8 * 11,即616. 输入样例

2 15

6 9

1 0

2 7

2 4

5 9

3 2

1 9

3 1

0 7

12 3

4 3

15 8

2 14

7 14

8 14

3 15

6 1

11 1

7 11

9 14

8 5

10 5

13 15 输出样例

2 8214265 样例解释

2 这个样例解释,真要写起来的话就会很长,所以我不解释了,你自己写个暴力 看看题意有没有理解错吧 QAQ,辛苦啦. 数据范围 对于所有数据,保证

1 ≤ M ≤ N ≤

8 *

104 ,0 ≤ Bi < 998244353. 下表为各个 Subtask 的额外限制与得分,空格表示该项无额外限制.你只有通 过一个 Subtask 的所有数据才能得到该 Subtask 的分.

8 Subtask 编号 N M 特殊限制 分值

1 ≤

500 7

2 ≤

4000 15

3 ≤

10 15

4 对于所有 i(1 ≤ i < N),读入的第 i 条边是 (i, i + 1)

18 5 对于所有 i(1 ≤ i < N),读入的第 i 条边是 (1, i + 1)

20 6

25 9