AdditionalFile6999.zip

#6999. 「THUPC 2026 初赛」生命线

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

对于一个长为 $n$ 的、仅由 $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ 构成的字符串 $s$ ，考虑一张含 $n$ 个点的无向带权图，每两个点 $i, j$ $\left(i \neq j\right)$ 间有权值为 $\operatorname{LCP}\left(suf_{i}, suf_{j}\right)^{\dagger}$ 的边，其中 $suf_{i}=s[i: n]$ 。 Ecrade__ 定义字符串 $s$ 的价值为该图最大生成树的边权之和。

Ecrade__ 想要请你找出所有长为 $n$ 的、仅由 $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ 构成的字符串中，价值第 $k$小的任意一个。

${ }^{\dagger} \operatorname{LCP}\left(s_{1}, s_{2}\right)$ 定义为字符串 $s_{1}$ 与 $s_{2}$ 的最长公共前缀的长度。

输入格式

从标准输入读入数据。

第一行一个整数 $T$ $\left(1 \leq T \leq 2 \times 10^{5}\right)$，表示测试数据组数。

对于每组测试数据，一行两个整数 $n, k$ $\left(1 \leq n, \sum n \leq 4 \times 10^{5}, 1 \leq k \leq \min\left(26^{n}, 10^{15}\right)\right)$。

输出格式

输出到标准输出。

对于每组测试数据，第一行输出第 $k$ 小的价值，第二行输出一行一个长为 $n$ 的、价值第 $k$ 小的字符串。若有多个字符串满足条件，输出其中任意一个即可。

样例 1

输入

3
2 1
2 676
3 16000

输出

0
hi
1
gg
1
qwq

• 对于第一组测试数据，长为 $2$ 的字符串中，第 $1$ 小（即最小）的价值为 $0$，一个满足条件的字符串为 $\texttt{hi}$ 。当然，$\texttt{ab}$、$\texttt{yz}$ 等字符串也满足条件。
• 对于第二组测试数据，长为 $2$ 的字符串中，第 $676$ 小（即最大）的价值为 $1$，一个满足条件的字符串为 $\texttt{gg}$。当然， $\texttt{aa}$、$\texttt{zz}$ 等字符串也满足条件。
• 对于第三组测试数据，长为 $3$ 的字符串中，第 $16000$ 小的价值为 $1$，一个满足条件的字符串为 $\texttt{qwq}$。当然，$\texttt{cpp}$、$\texttt{lol}$ 等字符串也满足条件。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。