Accepted 有效得分：100 有效耗时：156ms

puppy ,感谢你!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

#include "stdio.h"

#include "string.h"

char s1[2000000],s2[1000000];

long l;

long work()

{

long t=0;

for(long i=1;is1[i])

t=i;

else

{

if(s1[t]==s1[i])

for(long j=1;js1)

{ t=i;break;}

else

if(s1[t+j]

编译通过...

├ 测试数据 07：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：138ms

为什么O(n)却有点超时?谁能告诉我puppy何时出现啊?>

无语...

for i:=p to l+p-1 do write(s1[i]);

writeln;

没有'writeln' 交半天.... 无语....

中间语句顺序 打反了一行....... 无语........

让我调了一个小时......

同一个程序交n遍才AC，该死的评测机...

第400次提交，我AC了。。第一次编最小表示法

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

贴下神牛的论文：

求字符串的循环最小表示：

上面说的两个字符串同构的，并没有直接先求出Min(s)，而是通过指针移动，当某次匹配串长时，那个位置就是Min(s)。而这里的问题就是：不是给定两个串，而是给出一个串，求它的Min(s)，eg：Min(“babba”) = 4。那么由于这里并非要求两个串的同构，而是直接求它的最小表示，由于源串和目标串相同，所以处理起来既容易又需要有一些变化：我们仍然设置两个指针，p1, p2，其中p1指向s[0]，p2指向s[1]，仍然采用上面的滑动方式：

(1) 利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。

(2) k = 0开始，检验s[p1+k] 与 s[p2+k] 对应的字符是否相等，如果相等则k++，一直下去，直到找到第一个不同，(若k试了一个字符串的长度也没找到不同，则那个位置就是最小表示位置，算法终止并返回)。则该过程中，s[p1+k] 与 s[p2+k]的大小关系，有三种情况：

(A). s[p1+k] > s[p2+k]，则p1滑动到p1+k+1处 ---| 即s1[p1->p1+k]不会

是该循环字符串的“最小表示”的前缀。

(B). s[p1+k] = len 则返回p2

如果 p2 >= len 则返回p1

(4) 进一步的优化，例如：p1要移到p1+k+1时，如果p1+k+1

算法高效,在哪个机器上评测都一样,比如说我和楼下的这位.先用最小表示法判断是否同构,再用最小表示法寻找字典序最小的.然后输出.

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

能做到这种程度应该不容易吧，看最小表示法和循环同构断断续续得看了3个星期，终于全0MS通过，我不是在PUPPY上过的 ^_^

有点像1437做两次。

庆祝一下，第35个通过者。

另。如果要用1437的程序的话，请用Puppy测。

我一次Temper 90分T了。

后来一样的程序交Puppy AC。呵呵。

9ms AC

做两遍，第一遍判两串同构，第二遍让某串和自己求最小表示

第一遍判同构后的指针并不一定是最小表示（反例：两串相同）

看起来简单，，

但，，

其实，，

难得很，，

还是最小表示法好啊...

Vag 6K超了4个点 换Vivid Puppy就AC了

Puppy果然很强大

先扩两倍，然后第一问KMP没话说。

第二问：设f(i,j)表示：

令k=min(i,j),q=max(i,j)

则f(i,j)=min(s(k),s(q),s(q+1)..s(len));

且1~k-1,k+1~j-1均不可能成为最小表示。

如何求f(i,j)?令c表示最小的点使得s=s[j~j+c-1]且ss[j+c]。

三种情况：

1.若在len范围内不存在，则最小表示=s(i)，因为对于q

同冯牛....

PUPPY+最小表示法..同样的程序交了N遍,在遇到PUPPY的时候..终于AC了!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：65ms

貌似要O(n)+puppy才能过....

传说中的最小表示法，写起来很easy

可以参加Zhou Yuan论文

囧,圙……

没有人通过……

KMP??

拖鞋