看了下今年小学生计算机试题，发现自己还不如小学生了，

kangkls

看了下今年小学生计算机试题，发现自己还不如小学生了， [复制链接]

 

【问题描述】
小明有一个字符串，由小写英文字母组成。
小明准备对他的字符串进行改造，改造的方法是删除字符串中间的一部分字
符。小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右
边的字符（a < b < … < z）。
例如，对于字符串 happy，小明可以删除第一个字母，变成 appy，满足要
求。或者小明删除第二字母，变成 hppy，也满足要求。小明还有其他方法使得
结果满足要求。
再如，对于字符串 autumn，可以删除3 个字母变成 tmn，或者删除4 个
字母变成 at。其他满足要求的方案还有很多。
小明想知道，对于一个字符串，至少要删除多少个字母能满足要求。
【输入格式】
从文件trans.in 中输入数据。
输入一行包含一个字符串。
【输出格式】
输出到文件trans.out 中。
输出一行，包含一个整数，表示最少要删除的字母个数。
【样例输入】
happy
【样例输出】
1
【样例输入】
autumn
【样例输出】
3

对于所有评测用例，字符串的长度不超过100000。

 

 

限制半个小时做出来，考试时间总共120分钟，5道题，这是其中一道。

看了感觉自己还不如小学生，

 

 

此帖出自嵌入式系统论坛

lcofjp

智商这东西，年龄不是主要决定因素

kangkls

lcofjp 发表于 2020-9-28 12:11 智商这东西，年龄不是主要决定因素

可以挑战下这个题  啊！

kangkls

我这里有测试数据和答案，谁做了我可以测试

okhxyyo

现在小孩子很多都是四五岁就开始编程启蒙了。我前些天刚给我闺女买了编程启蒙课。我闺女三岁半，但是在买课的里面年龄都算挺大的了。全是看着最近活动囤货的。五六岁的人家都早开始学了

lcofjp

okhxyyo 发表于 2020-9-28 12:33 现在小孩子很多都是四五岁就开始编程启蒙了。我前些天刚给我闺女买了编程启蒙课。我闺女三岁半，但是在买课 ...

给你闺女注册个论坛账号，哈哈

lcofjp

kangkls 发表于 2020-9-28 12:16 可以挑战下这个题  啊！

不想浪费那个脑细胞了，过了那个年轻好胜的年龄了，有空闲时间还是让脑子多休息一下比较好。

sint27

应该不是义务教育的吧，不然不敢相信

maychang

“再如，对于字符串 autumn，可以删除3 个字母变成 tmn”

错了吧？ tmn 不符合要求。删除字符串 utu ，autumn 变成amn，才符合要求。

kangkls

maychang 发表于 2020-9-28 16:15 “再如，对于字符串 autumn，可以删除3 个字母变成 tmn” 错了吧？ tmn 不符合要求。删除字符 ...

是的，我是复制过来的，没做任何改动

kangkls

我感觉这道题对我来说，还是挺困难的，特别是最少删除多少个字符。

kangkls

发一组测试数据，答案是722

测试数据如下

adcbbdeecdeabbdabdabedabebeddcaaeecaaceeaadeceecccededadcdcceaaceddcdbdabdedddbbdaabeedabacccdebedacbcbabcbaddbecbaabdeebeacecdbaabdbedecdeddcccdeebbcecaddebaddcebedaeaeddbdcbccdcddbbebcceeccadbccadaeaabdbcdddccbbabeadccdbcabcbdccddaaebbaeceacedbbaccacaacabedcccdbaddbaeabaaaceddeaeaeccdadebcbedeabcbcdaeeaeddaacbcaacbecacacdddddbeabeacdacebcedbaecabaccaeaedbaddaabdbcdeadbbedcbdaaccdcbcdcbceecabccabeccbbbbdcbbbdadbbdbaaaceaaeddebdeeebaacbdecebcccbddbeeebcdcbacbcdacbbadcceeaecbbdaaadcceececacbcbdebaaaeabbaacceadadccbdadcbaaceabbddeecaeeddbcdcdabbcdbbacebbbebaeadccdabccdcbeceacaceaadeccceddbccebabcbaeaebddddbecdcbceadeaeabecbcbcacabeaecaaecddaecbacecaaaeddbebadbccbaaabdecbecbdcaacdaddbbecadeaabeaeecbadaecbeabcadaaedbcecaccadbadadbcabcbedabbcecedeebaccdcbaacecaacedebcdddcbaccadbcaeaccdebbadbcbacccdbdbcbbdcaddacababacddaeeaeccebcdbcaaabbcabcbbadcedcacdcbecdebddaaeeaedacacdcebcbbcedcaecbcbdabebbddaccbceedecdcebbeeaacabecaecdadbbdcbdcaebcbcdcbc

freebsder

做不出来做不出来

qwqwqw2088

kangkls 发表于 2020-9-28 17:02 发一组测试数据，答案是722 测试数据如下 adcbbdeecdeabbdabdabedabebeddcaaeecaaceeaadeceecccededa ...

怎么个计算过程

29447945

不会做不会做

kangkls

qwqwqw2088 发表于 2020-9-28 23:36 怎么个计算过程

删除最少的字符之后，使这个字符串的字母从小到大排列

btty038

这个任务看来只有交给下一代了

powerlove

太复杂了，这个任务看来只有交给下一代了

guojun0718

10X*10X 口算有口诀，小孩子学了口算口诀，比学数学的博士还要算的快，这样子，有意义吗？实际的数字处理中有多少这样子的特例？

而且，一种特例，就一套口诀。需要背多少口诀？

回到这个题目，从普遍性来讲，提供一点思路。

最后一个设为最大，然后依次往前找，比大的就删除，小的就留下，并设为最大，继续找，直到第一个。

或者反过来，从第一个，找最小。

但是，这个算法执行次数，似乎是阶乘，如果字符串过长，程序执行时间需要多久？

这个是我的第一感觉。也不想多想。

这些孩子如果是出于强烈的兴趣，保不齐能出天才，甚至于黑（白）客。

但是出于竞赛的目的的话。。。如果再考虑到升学。。。

我个人是不太赞成这类题目的。

kangkls

1%的孩子是满分，当然，这里也许有水分，不一定完全是孩子自己做的。