#PQJ926x4051. QOJ 926_4051

    ID: 3062 传统题 1500ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2022 统一省选字符串

QOJ 926_4051

NOI2022 省选 DAY1 学术社区(community) 学术社区(community) .小I .的.温.馨.提.示:.在.题.目.描.述.中.有.形.式.化.的.题.面,.你.可.以.选.择.跳.过.题.目.背.景。.同.时 .请.仔.细.将.本.题.的.除.题.目.背.景.以.外.的.所.有.内.容.进.行.完.整.阅.读.后.再.进.行.做.题。 【题目背景】 小I 是一个喜欢OI 的选手,不过,与其说小I 喜欢OI,不如说小I 喜欢的是他最 经常使用的OJ——FCCOJ——上的趣味功能:学术社区。虽说名字叫学术社区,但小 I 和网友们能够谈论的东西远不止学术。每天学术社区里总会出现不少吸引小I 注意的 帖子。今天小I 在学术社区冲浪时发现了一个这样的帖子: builtin_clz:萌新求助,学术社区这题,本机AC 提交RE builtin_ctz:builtin_clz楼下 jinkela:builtin_ctz楼下 builtin_ctz:builtin_clz楼上 builtin_clz:能不能别魔怔了,大家正经回答问题 OrzTourist:builtin_clz楼下 OrzTourist:OrzTourist楼下 builtin_clz:怎么没有人回答问题,我生气了! builtin_clz:builtin_clz楼上 builtin_clz:builtin_clz楼下 builtin_clz:builtin_clz楼上 builtin_clz:builtin_clz楼下 …… 虽然这个名叫builtin_clz 的网友因为没有人回答他的学术问题被激怒了,但这 个有趣的发言方式让小I 乐呵了许久,这说明人类的悲欢并不相通。不过当小I 刷新界 面想要往下浏览大家的回复时,却发现学术社区的管理员因为这个帖子过于灌水把它删 除了。 为了恢复这个有趣的帖子,小I 对着网页缓存倒腾了许久,还原出了这个帖子的每 条消息。然而因为神秘原因,消息的顺序被打乱了,且缓存中没有每条消息发送的时间, 因而小I 没有办法还原原始帖子中消息的顺序。 秉承“遇到困难睡大觉”精神的小I 决定随便给帖子里的消息排个顺序,不过深受 “XXX楼上”“XXX楼下”这种发言形式吸引的小I 还是希望重排之后有尽可能多的这种 形式的消息的表达是符合帖子的实际情况的。然而小I 是一个只会水社区不会做题的 OI 选手,所以小I 求助于你。 第9 页 共14 页

NOI2022 省选 DAY1 学术社区(community) 当然了,小I 知道直接将帖子中的原始信息丢给你对你来说是不方便的,所以他对 信息进行了一些规范化处理,详见题目描述中的形式化题意。.同.时.由.于.学.术.社.区.的.特.殊 .规.定,.帖.子.中.的.消.息.满.足.一.定.特.殊.限.制,.详.见.题.目.描.述.最.后。 【题目描述】 .以.下.涉.及.的.所.有.字.符.串.判.等.操.作.都.对.大.小.写.敏.感,.例.如loushang、Loushang、 LOUSHANG .是.互.不.相.同.的.字.符.串。 小I 正在整理学术社区中的一个帖子。帖子中共有N 个网友发过消息,他们的网 名分别为n1, n2, · · · , nN。帖子中总共有M 条消息,对于第i 条消息,我们用三个字符 串si,1, si,2, si,3 构成的三元组描述它,其中si,1 表示这条消息发出者的网名,而si,2 和 si,3 描述这条消息的内容。 对于第i 条消息,我们通过如下方式定义其属于.楼.下.型.消.息、.楼.上.型.消.息、.学.术.消 .息中的哪一种: • 若字符串si,3 为louxia,且si,2 恰好与给出的某个网名相同(注意si,2 = si,1 是 允许的),则称这条消息是.楼.下.型.消.息,si,2 对应这条消息提到的网友; • 若字符串si,3 为loushang,且si,2 恰好与给出的某个网名相同(注意si,2 = si,1 是允许的),则称这条消息是.楼.上.型.消.息,si,2 对应这条消息提到的网友; • 若以上两个条件都不满足,则称这条消息是.学.术.消.息。 定义一个对所有消息的重排方案为一个1 到M 的排列a1, a2, a3, · · · , aM,表示第 一条消息是(sa1,1, sa1,2, sa1,3),第二条消息是(sa2,1, sa2,2, sa2,3),依此类推。 对于一个重排方案a1, a2, · · · , aM 中的第i(1 ≤i ≤M) 条消息(sai,1, sai,2, sai,3),如 下定义其是否是.符.合.实.际.情.况.的: • 若这条消息是.楼.下.型.消.息,则这条消息是.符.合.实.际.情.况.的当且仅当i̸ = 1 且 sai−1,1 = sai,2,即上一条消息存在且它的发出者与这条消息提到的网友一致。 • 若这条消息是.楼.上.型.消.息,则这条消息是.符.合.实.际.情.况.的当且仅当i̸ = M 且 sai+1,1 = sai,2,即下一条消息存在且它的发出者与这条消息提到的网友一致。 • 若这条消息是.学.术.消.息,则无论如何这条消息一定不是符合实际情况的,这是因 为小I 只想灌水不想学术。 在以上定义下,小I 希望找到一个重排方案,使得该重排方案中符合实际情况的消 息数量最多。你需要帮他找到这个方案以及这个方案中符合实际情况的消息数量。 .为.了.方.便.你.的.解.题,.小I .还.告.诉.了.你.帖.子.中.消.息.的.一.个.特.殊.限.制:.因.为.学.术.社.区.会 .禁.言.在.社.区.中.只.灌.水.不.学.术.的.人,.所.以.在.小I .给.出.的.帖.子.里,.每.一.个.在.帖.子.中.发.过.言.的 .人.都.一.定.会.在.帖.子.中.发.出.至.少.一.条.学.术.消.息。 【输入格式】 从文件community.in 中读入数据。 第10 页 共14 页

NOI2022 省选 DAY1 学术社区(community) .本.题.有.多.组.测.试.数.据。第一行一个整数T 表示测试数据组数,接下来分别输入T 组数据。 对于每组测试数据,第一行两个整数N, M 分别表示帖子中发过消息的网友数量以 及帖子的消息数量。 接下来N 行每行一个字符串n 表示在帖子中发过消息的一个网友的网名。保证每 个测试数据中输入的N 个网友的网名两两不同。 接下来M 行每行三个字符串s1, s2, s3 描述一条消息,相邻的字符串之间用一个空 格分隔,其中s1 一定与输入中某个网友的网名相等。 输入的所有字符串仅由大小写英文字母、下划线(_)、英文问号(?)、英文感叹号 (!)和英文句号(.)构成,且长度不超过12。 对于每组测试数据,保证输入的N 个网名都发出过至少一条消息,.且.至.少.发.出.过 .一.条.学.术.消.息。 同一组测试数据中可能存在多条消息内容完全一致,此时应将他们视为.多.条消息。 【输出格式】 输出到文件community.out 中。 对于每组测试数据输出两行。 第一行输出一个非负整数表示所有重排方案中最大的符合实际情况的消息数量。 第二行输出M 个整数a1, a2, · · · , aM,表示符合实际情况的消息最多的重排方案。 若有多种合法的重排方案,.输.出.任.意.一.个.即.可。 【样例1 输入】 1 2 2 4 15 3 builtin_clz 4 builtin_ctz 5 jinkela 6 OrzTourist 7 builtin_clz MengXin QiuZhu 8 builtin_ctz builtin_clz louxia 9 jinkela builtin_ctz louxia 10 builtin_ctz builtin_clz loushang 11 builtin_clz BieMoZheng YaoXueShu 12 OrzTourist builtin_clz louxia 13 OrzTourist OrzTourist louxia 14 builtin_clz Iam Angry! 第11 页 共14 页

NOI2022 省选 DAY1 学术社区(community) 15 builtin_clz builtin_clz loushang 16 builtin_clz builtin_clz louxia 17 builtin_clz builtin_clz loushang 18 builtin_clz builtin_clz louxia 19 builtin_ctz Xue Shu 20 jinkela Xue Shu 21 OrzTourist Xue Shu 22 1 9 23 builtin_clz 24 builtin_clz builtin_clz loushang 25 builtin_clz builtin_clz loushang 26 builtin_clz builtin_clz louxia 27 builtin_clz builtin_clz Loushang 28 builtin_clz builtin_clz LOUSHANG 29 builtin_clz Builtin_clz loushang 30 builtin_clz loushang louxia 31 builtin_clz builtin_clz builtin_clz 32 builtin_clz loushang builtin_clz 【样例1 输出】 1 9 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 3 4 8 1 2 7 9 3 6 4 5 【样例1 解释】 第一个测试数据与题目背景中给出的例子基本一致,而不同的点在于:为了满足每 个人至少发出一条学术消息的要求,在该组数据输入的最后有几条额外的学术消息。 第二个测试数据中,输入的前两条消息是楼上型消息,第三条消息是楼下型消息, 其他消息是学术消息。 【样例2】 见选手目录下的community/community2.in 与community/community2.ans。 第12 页 共14 页

NOI2022 省选 DAY1 学术社区(community) 【样例3】 见选手目录下的community/community3.in 与community/community3.ans。 该组样例满足数据范围中的特殊性质A、特殊性质B、特殊性质C。 【样例4】 见选手目录下的community/community4.in 与community/community4.ans。 该组样例满足数据范围中的特殊性质C。 【数据范围】 设∑M 为单个测试点中所有测试数据的M 的和。 对于所有测试点,1 ≤T ≤102, 1 ≤N ≤M ≤77, 777, 1 ≤∑M ≤2.5 × 105。 T ≤ M ≤ ∑M ≤ 测试点编号 特殊性质A 特殊性质B 特殊性质C 5 10 50 1 无 无 无 10 16 160 2 30 2, 222 15, 000 3,4 有 有 有 5,6 无 7,8,9 无 有 10,11 无 12,13 无 102 77, 777 2.5 × 105 14,15 有 有 有 16 无 17,18,19 无 有 20,21,22 无 23,24,25 无 .注.意:.为.了.阅.读.方.便,.测.试.点.编.号.在.表.格.中.的.第.四.列。 特殊性质A:没有楼上型消息。.注.意:.这.不.意.味.着s3 .不.等.于loushang。 特殊性质B:对于每组测试数据,存在一个重排方案,使得每一条楼上型消息和楼 下型消息都是符合实际情况的。 特殊性质C:对于每组测试数据,若存在一条消息是s1 s2 loushang,其中s1, s2 为任意字符串,则该组数据中一定不存在一条消息是s2 s1 louxia。 【评分方式】 若一个测试点内所有测试数据的符合实际情况的消息数量都正确,你将获得该测试 点50% 的分数;在此基础上,若一个测试点内所有测试数据的重排方案都正确,你将 第13 页 共14 页

NOI2022 省选 DAY1 学术社区(community) 获得该测试点的所有分数。需要注意的是,.如.果.你.只.希.望.获.得50% .的.分.数,.你.也.要.保 .证.在.每.组.测.试.数.据.的.第.二.行.输.出.一.个1 .到M .的.排.列,.否.则.实.际.分.数.与.期.望.分.数.可.能.出 .现.偏.差。 【提示】 因为这对你可能很重要,所以小I 再一次强调:.因.为.学.术.社.区.会.禁.言.在.社.区.中.只.灌 .水.不.学.术.的.人,.所.以.在.小I .给.出.的.帖.子.里,.每.一.个.在.帖.子.中.发.过.言.的.人.都.一.定.会.在.帖.子 .中.发.出.至.少.一.条.学.术.消.息。 本题输入规模较大,请使用较为快速的输入方式。 第14 页 共14 页