题目描述

渡渡鸟国的每位国民都有一个长度为 $n$ 的身份证号,身份证号的每一位为 $[1,k]$ 内的一个整数。渡渡鸟国现在要设立若干个服务站,每个服务站有一个长度为 $2$ 的编号,每一位也是 $[1,k]$ 内的一个整数。

对于一只渡渡鸟,设其身份证号为 $s$,其中 $s$ 是一个长度为 $n$ 的字符串。对于一个服务站,设其编号为 $t$,其中 $t$ 是一个长度为 $2$ 的字符串。当且仅当 $t$ 是 $s$ 的子序列时,这只渡渡鸟可以被这个服务站服务。比如 $s=123,t=13$ 时,渡渡鸟可以被服务;而$s=123,t=31$ 时,渡渡鸟不能被服务。

渡渡鸟国王希望建设一些服务站,使得任意一只渡渡鸟都可以被至少一个服务站服务。它想知道最少需要建造多少个服务站。

通过并查集 首先最后要分成(k-1)组 然后求步数即可

评论