题目描述

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

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

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

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

题目链接

题目描述

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在 小凯无法准确支付的商品。

阅读全文