Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:题目很经典呀!!!跟1147有个比呀,虽然水,但是有嚼头~~说说思路

Posted by 20082970 at 2009-04-23 20:06:00 on Problem 1602
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator