思路:构造
考虑对于一个字符串s,我们需要操作多少次可以将其所有的字符都变为相同字符
例如s=abbaaaccc...,除了字符a以外还有8个字符,考虑一种情况就是这8个字符都是相邻字符,没法一次性删除
- 第一次删除:删除不相邻的4个字符,还剩下4个字符
- 第二次删除:删除不相邻的2个字符,还剩2个字符
- 第三次删除:删除不相邻的1个字符,还剩1个字符
P1420.第3题-小红的字符串
题目描述
小红是一个热爱字符串操作的天才。最近,他遇到了一个有趣的挑战。他希望构造一个长度为n的、仅由小写字母组成的字符串,使其权值(通过特定操作得到的最小操作次数)等于k。
在这个挑战中,小红需要选择字符串中的若干不相邻的字符进行删除操作,使得最终字符串中所有字符都相同,并且操作次数最小。
例如,对于字符串"arcaea",小红可以按照以下步骤操作:
- 删除第3个和第5个字符,得到字符串 "araa"。
- 删除第2个字符,得到字符串 "aaa"。
经过2次操作后,字符串变成了 "aaa",其中所有字符都相同。因此,"arcaea"的权值为2。
现在,给定两个正整数n和k,请你帮小红构造一个长度为n的、仅由小写字母组成的字符串,使其权值等于k。
输入描述
两个以空格分隔的正整数n和k。
1≤k≤n≤200000。
输出描述
一个以小写字母组成的合法的字符串。
特别的,本题开启 Special Judge,有多个答案输出任意一个即可,如果无解请输出 -1。
6 2
arcaea