| 题目名称 | 1906. [SRM 467] 均匀字符串 |
|---|---|
| 输入输出 | homogeneous.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-01-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 cstdio |
100 | 0.046 s | 58.69 MiB | C++ |
| 关于 均匀字符串 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
坑了我一个星期，写错若干次……→_→
题解：http://blog.sina.com.cn/s/blog_c5566b0f0102vbmh.html | ||||
|
回复 @清羽 :
可管理员们似乎删不了题……  Asm.Def
2015-01-18 23:12
3楼
| ||||
|
@catdio 请把这个题目删掉吧。在题库里面发现有这个题了，谢谢！
 清羽
2015-01-18 21:25
2楼
| ||||
|
我还以为抄袭题目直接就连数据一并down下来了呢……唉，too young too naive
清羽
2015-01-18 20:41
1楼
| ||||
【题目描述】
我们称一个字符串是“均匀的”，如果它每个长度为n的连续子串都包含不超过d个不同的字符。对于一个字符串seed和一个长整型整数k，定义k大均匀字符串为：所有和seed长度相同且字典序大于等于seed的均匀字符串中，按字典序从小到大，从0开始数的第k个。这里所说的字符串只包含小写字母。给出n,d,seed,k，你需要计算并输出k大均匀字符串。如果合法的字符串少于k+1个，输出空字符串。
【输入格式】
一行，分别为d,n,seed,k。
【输出格式】
一行一个字符串，即k大均匀字符串。
【样例输入0】
1 2 aaa 3
【样例输出0】
d
【提示】
n=2,d=1的条件意味着两个相邻字符必须相等。因此合法的均匀字符串只有"aaa", "bbb", "ccc", ..., "zzz"。"ddd"是第四个（从0开始数的3号）。
【样例输入1】
2 3 abc 0
【样例输出1】
aca
【样例输入2】
2 4 ttrrzz
【样例输出2】
ttsssc
【样例输入3】
6 8 txyaaxaassaaaarghjsdohasdghususdidisisdodo 10000000000000000
【样例输出3】
txyaaxaassaaaarghjsgaaaaaaaaadntffiniqrddy
【样例输入4】
2 5 zzzzzaa 100
【样例输出4】
（注：样例输出4是一个空字符串）
【提示】
在这种情况下，有25个形如"zzzzzXX"的均匀字符串，其中X是除了z之外的任何小写字母。有25个形如“zzzzzXz”的均匀字符串，还有26个以“zzzzzz”开头的均匀字符串。因此总共有25+25+26=76个字典序大于等于"zzzzzaa"的均匀字符串。
【数据规模和约定】
1<=n<=9
1<=d<=n
0<=k<=10^18
seed的长度在1~50之间。
seed至少包含n个字符。
seed只包含小写字母。
【来源】
Topcoder SRM 467 Div 1, 1000