Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:题目很经典呀!!!跟1147有个比呀,虽然水,但是有嚼头~~说说思路In Reply To:题目很经典呀!!!跟1147有个比呀,虽然水,但是有嚼头~~说说思路 Posted by:huguang123 at 2009-03-23 15:26:43 > 对于工作A,当然很容易了,从a~z搜索一下,输出相应位置的前一位就好了,时间复杂度26*10000,当然可以过了。 > 工作B么,当然,有个条件很重要,就是题中给的p,既首字母所在的位置,那么按照他给的排序规则,既,有相同字母,在原单词中早出现的排在前面,所以我们需要先构造一个在s'中出现的所有字符的升序序列ss,然后从头往后找,找到第一个与首字母相同的位置记为i,那么s‘中的i位置就为单词的最后一个字母了。单词长度为l,原单词记为ans,既ans[0]=s'[p];ans[l-1]=s’[i];,并把ss[i]标记为不可找,防止以后找重了。接下来就是循环操作了: > step1:在ss中从后往前找,找到与s‘[i]相同的字母的位置,记为j; > step2:把s’[j]放到ans中上一次操作的前一位; > step3:i=j; > step4:重复step1,知道找了l-2遍为止。 > 记住,要用数组进行优化呀! > > 此题为本人做出第300题,发个题解留个纪念,也当是做个小小的贡献。 hao Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator