YZOJ P4259 [FJWC 2019] 不同的缩写

YZOJ P4259 [FJWC 2019] 不同的缩写

时间限制:1000MS      内存限制:262144KB

出题人:E.Space      难度:\(6.1\)

  • 题目描述

在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。

你打算用角色名字的一个非空子序列来作为它的简称。

当然,不同的角色要用不同的字符串作为简称,否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。

  • 输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行,每行一个由小写字母组成的字符串,代表一个角色的名字。

不同的角色可能会有相同的名字。

  • 输出格式

如果不存在一种分配简称的方案满足条件,输出 \(-1\)。

否则第一行输出一个正整数,表示最长的简称的最小长度。

接下来 \(n\) 行每行一个字符串,按顺序表示每个角色的简称。

若有多种方案满足条件,那么你可以输出任意一种。

  • 样例输入

  • 样例输出

  • 数据规模与约定

保证 \(n \leq 300\) ,每个名字的长度不超过 \(300\)。

 

 

 


 

 

 

我校校队成员(gamerboy

首先要求的是长度最小,可以想到二分答案,因为长度比答案大的一定可以,比答案小的一定不行。

因为每个人都与缩写一 一对应,所以其实发现这是一个二分图匹配,用序列自动机爆搜出所有的子序列,使用Trie树判重,然后连边匹配。

这样点/边数很多,所以考虑 Hall 定理,那么大于 \(n\) 个对应字符串的子序列就没有继续搜索的必要了。

这样就有一个点数 \(O(n^2)\) 边数 \(O(n^2)\) 的图,跑 Dinic 的复杂度是 \(O(n^3)\),总复杂度 \(O(n^3logn)\) 。

都知道 Dinic 跑不满,所以这题可以过。

 

 

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注