讨论 / 有没有O(nlogn)的算法
libojie 2011-02-08 21:06:00
点我顶贴 收藏 删除
有没有O(nlogn)的算法,请大牛指教!
#1 wish@2009-03-22 12:39:00
回复 删除
可以用 Trie

线性复杂度

这两天有空写个看看

#2 OI帝国@2009-03-22 13:07:00
回复 删除
状态: Accepted

测评机: Xeost[5]

得分: 100分

提交日期: 2009-3-20 12:58:00

有效耗时: 2079毫秒

测试结果1: 通过本测试点|有效耗时156:ms

测试结果2: 通过本测试点|有效耗时172:ms

测试结果3: 通过本测试点|有效耗时157:ms

测试结果4: 通过本测试点|有效耗时172:ms

测试结果5: 通过本测试点|有效耗时156:ms

测试结果6: 通过本测试点|有效耗时250:ms

测试结果7: 通过本测试点|有效耗时266:ms

测试结果8: 通过本测试点|有效耗时250:ms

测试结果9: 通过本测试点|有效耗时250:ms

测试结果10: 通过本测试点|有效耗时250:ms

快排即可

#3 libojie@2009-03-22 13:28:00
回复 删除
快排?

开始时已经按字典序排序了,快排是什么时候?

请解释!

#4 libojie@2009-03-22 13:29:00
回复 删除
我想了想,确实可以用Trie。

似乎字母树就是干这个的。

就是写代码比较麻烦……

#5 OI帝国@2009-03-22 17:25:00
回复 删除
已有序?我没看到。
#6 wish@2009-03-24 19:05:00
回复 删除
Trie 的程序:

貌似写得有点丑,而且貌似真的不需要 Trie

汗。。。全当练习吧

program rq_429(input, output);

const

 maxNode = 1000000;

 

var

 N, NodeCount, ans, Current, i, j, c: Longint;

 S: string;

 T: array [0..maxNode, ’a’..’z’] of Integer;

 F: array [1..maxNode] of Boolean;

begin

 fillchar(F, sizeof(F), 0);

 fillchar(T, sizeof(T), 0);

 readln(N);

 ans := 0;

 NodeCount := 0;

 for i := 1 to N do

  begin

   readln(S);

   Current := 1;

   c := 0;

   for j := 1 to length(S) do

    if T[c, S[j]] = 0 then

     begin

      inc(NodeCount);

      T[c, S[j]] := NodeCount;

      c := NodeCount

     end

    else

     begin

      c := T[c, S[j]];

      if F[c] then

       inc(Current)

     end;

   F[c] := True;

   if Current > ans then

    ans := Current

  end;

 writeln(ans)

end.

#7 lychees@2009-03-24 19:49:00
回复 删除
- -大家都出来了..
#8 OI帝国@2009-03-28 12:51:00
回复 删除
trie都出来了,至于么?

我的:

for i:=1 to n do

begin

tt:=1;

for j:=i-1 downto 1 do

begin

l:=length(s[j]);

if copy(s[i],1,l)=s[j] then begin tt:=a[j]+1;break;end;

if s[j,1]<>s[i,1] then break;

end;

a[i]:=tt;

end;

for i:=1 to n do if a[i]>ans then ans:=a[i];

write(ans);

#9 jww521@2009-08-28 17:06:00
回复 删除
有的啊!

查看状态 Show Status

状态题目:词链

题目编号:429-词链 查看该题

状态: Accepted

测评机: Xeost[5]

得分: 100分

提交日期: 2009-8-28 17:02:00

有效耗时: 623毫秒

测试结果1: 通过本测试点|有效耗时47ms

测试结果2: 通过本测试点|有效耗时46ms

测试结果3: 通过本测试点|有效耗时47ms

测试结果4: 通过本测试点|有效耗时47ms

测试结果5: 通过本测试点|有效耗时47ms

测试结果6: 通过本测试点|有效耗时46ms

测试结果7: 通过本测试点|有效耗时63ms

测试结果8: 通过本测试点|有效耗时62ms

测试结果9: 通过本测试点|有效耗时125ms

测试结果10: 通过本测试点|有效耗时93ms

利用二分思想。

#10 lohocla4dam@2009-10-14 20:18:00
回复 删除
这个题没有O(nlgn)的算法,假设用二分找到了一个

s[mid-1]包含于toFind的mid,

那么对于s[mid]与toFind应如何取舍?

如果按长度大小来取舍,那如果toFind最后一个字母为z,可能导致最坏情况

查看更多回复
提交回复