首页 / 题库

P70010 - 去重(remove)

动态规划
通过次数1 提交次数10 内存限制 512MB 时间限制1秒

描述

给定一个字符串s,请你去除字符串中重复的字母,使得每种字母至少出现l次,至多出现r次。需保证返回结果的字典序最小,并且不能打乱字符的相对位置。如果原本字符串某种字符只出现了$l^' (l^'<l)$次,那么这种字符全都需要保留。
对于字典序,如果一个字符串a是字符串b的前缀串,那么a的字典序要小于b的字典序;如果不是,那么就比较他们之间第一个不同的字符的ACSII码值,值小的字典序更小。

输入

从文件remove.in中读入数据。
输入的第一行为两个数字l、r。
输入的第二行为字符串s。所有字符均为小写的英文字母。

输出

输出到文件remove.out中。
输出一行,为去掉部分的字符的剩余字符串。

样例

  • 复制
  • 复制
  • 复制
  • 复制

提示

【样例1解释】
各种字符至少保留1个,至多保留2个。满足条件的剩余字符串有‘cab’、‘bcabc’、‘bcac’、‘babc’、‘cabc’、‘abc’是不同字符最多两次至少一次出现并且保证原字符顺序不变的所有可能,但是‘abc’的字典序最小。

【样例2解释】
各种字符需要保留2~3个。但是字母b只有一个,那么必须保留。‘aaabcc’、 ‘aabccc’、 ‘aaabccc’、 ‘aabccc’都满足条件,其中‘aaabcc’的字典序最小。

【数据范围】

对于所有测试数据保证:$1≤length(s)≤10^6,s_i∈[a-z],1≤ l≤r≤length(s)$

特殊性质A : l=1。
特殊性质B : l=r。
特殊性质C : l=r-1。
特殊性质D : 字符串是由若干个同一字符组成、长度大于等于r的子串组成。 

 

附件

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36