飒飒

SAM大法好
#1 Accepted 3ms 4.242 MiB
#2 Accepted 2ms 4.211 MiB
#3 Accepted 3ms 4.25 MiB
#4 Accepted 2ms 4.242 MiB
#5 Accepted 2ms 4.215 MiB
#6 Accepted 3ms 4.125 MiB
#7 Accepted 2ms 4.23 MiB
#8 Accepted 2ms 4.238 MiB
#9 Accepted 2ms 4.219 MiB
#10 Accepted 2ms 4.227 MiB
#11 Accepted 3ms 4.125 MiB
#12 Accepted 3ms 4.25 MiB
#13 Accepted 3ms 4.223 MiB
#14 Accepted 34ms 16.125 MiB
#15 Accepted 40ms 16.09 MiB
#16 Accepted 69ms 29.031 MiB
#17 Accepted 87ms 28.25 MiB
#18 Accepted 79ms 27.594 MiB
#19 Accepted 88ms 27.965 MiB
#20 Accepted 79ms 27.34 MiB

#include<bits/stdc++.h>
using namespace std;
struct data
{
char num[25],name[45],sex,score[45],address[45];
int age;
bool scan()
{
scanf("%s",num);
if(strcmp(num," end")==0)
return 0;
scanf("%s%s%s%c%d%a\n",num,&name,&sex,&age,&score,&address);
return false;
}
void print()
{
printf("%s%s%c%d%s%s\n",num,name,sex,age,score,address);
}
};
struct node
{
data d;
node*nxt,*pre;
}*head,*tail,*p;
int n,k;

int main()
{
head=new node;
head->pre=head->nxt=NULL;
tail=head;

while(1)
{
p=new node;
if(p->d.scan())
break;

p->pre=tail;
tail->nxt=NULL;
tail=p;
}
p=tail;
while(p!=head)
{
p->d.print();
p=p->pre;
}
return 0;
}

只想说这道题的读入为什么这么奇怪……

改了基数还是没0ms好不爽：
**
编译成功

foo.cpp: In function 'void Build()':
foo.cpp:41:17: warning: operation on 'j' may be undefined [-Wsequence-point]
foo.cpp: In function 'int main()':
foo.cpp:71:21: warning: unknown conversion type character 'l' in format [-Wformat]
foo.cpp:71:21: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 0 ms, mem = 6904 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 6900 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 6900 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 6904 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 6904 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 6904 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 6900 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 6900 KiB, score = 5
测试数据 #8: Accepted, time = 0 ms, mem = 6900 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 6904 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 6904 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 6896 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 6904 KiB, score = 5
测试数据 #13: Accepted, time = 15 ms, mem = 6900 KiB, score = 5
测试数据 #14: Accepted, time = 15 ms, mem = 6904 KiB, score = 5
测试数据 #15: Accepted, time = 78 ms, mem = 6896 KiB, score = 5
测试数据 #16: Accepted, time = 62 ms, mem = 6900 KiB, score = 5
测试数据 #17: Accepted, time = 78 ms, mem = 6896 KiB, score = 5
测试数据 #18: Accepted, time = 62 ms, mem = 6904 KiB, score = 5
测试数据 #19: Accepted, time = 46 ms, mem = 6904 KiB, score = 5
Accepted, time = 371 ms, mem = 6904 KiB, score = 100
**
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 200010

int Rank[MAXN],sa[MAXN],h[MAXN],p[27];
int n;
int x[MAXN],y[MAXN],t[MAXN],w[MAXN],r[MAXN];

char s[MAXN];

void Build() {
x[0]=y[sa[0]=0]=-1;
int N,b=1,M=n,j;
for (int i=0;i++<n;) M=max(M,Rank[i]=s[i]);
do {
for (int i=0;i++<n;) x[i]=Rank[i],y[i]=i+b<=n?Rank[i+b]:0;
b<<=1;
for (int i=0;i<=M;i++) w[i]=0;
for (int i=0;i++<n;) w[y[i]]++;
for (int i=0;i++<M;) w[i]+=w[i-1];
for (int i=0;i++<n;) r[w[y[i]]--]=i;
for (int i=0;i<=M;i++) w[i]=0;
for (int i=0;i++<n;) w[x[r[i]]]++;
for (int i=0;i++<M;) w[i]+=w[i-1];
for (int i=n;i;i--) sa[w[x[r[i]]]--]=r[i];
N=0;
for (int i=0;i++<n;) {
if (x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]]) N++;
Rank[sa[i]]=N;
}
} while (N<n);
memset(h,0,sizeof(h));
j=1;
for (int i=0;i++<n;) {
if (i==sa[1]) h[i]=j=0
; else {
j=j-1<0?0:--j;
h[i]=j;
for (int k=1;i+j+k-1<=n&&sa[Rank[i]-1]+j+k-1<=n;k++) {
if (s[i+j+k-1]==s[sa[Rank[i]-1]+j+k-1]) h[i]++ ; else break;
}
j=h[i];
}
}
}

void getstring() {
int c;
for (int i=0;i++<n;) {
for (c=getchar();!(c>=int('a')&&c<=int('z'));c=getchar()) ;
s[i]=char(c);
}
}

int main() {
scanf("%d",&n);
getstring();
memset(p,0,sizeof(p));
for (int i=0;i++<n;) p[int(s[i])-int('a')+1]=1;
for (int i=0;i++<26;) p[i]+=p[i-1];
for (int i=0;i++<n;) Rank[i]=p[int(s[i])-int('a')+1];
Build();
long long ans=0;
for (int i=0;i++<n;) {
ans+=(i-h[i]);
}
printf("%lld\n",ans);
return 0;
}

话说呢，其实基数排序也可以算是O(n log n)的一种排序，不过对数的底数是10，而且常数比较大。反正直接O(n log^2 n)过掉了，就不追究啥了。

编译成功

foo.cpp: In function 'void Build()':
foo.cpp:54:17: warning: operation on 'j' may be undefined [-Wsequence-point]
foo.cpp: In function 'int main()':
foo.cpp:84:21: warning: unknown conversion type character 'l' in format [-Wformat]
foo.cpp:84:21: warning: too many arguments for format [-Wformat-extra-args]
测试数据 #0: Accepted, time = 0 ms, mem = 5432 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 5424 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 5424 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 5428 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 5428 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 5428 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 5424 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 5424 KiB, score = 5
测试数据 #8: Accepted, time = 15 ms, mem = 5424 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 5428 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 5424 KiB, score = 5
测试数据 #11: Accepted, time = 15 ms, mem = 5424 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 5428 KiB, score = 5
测试数据 #13: Accepted, time = 62 ms, mem = 5424 KiB, score = 5
测试数据 #14: Accepted, time = 62 ms, mem = 5424 KiB, score = 5
测试数据 #15: Accepted, time = 109 ms, mem = 5428 KiB, score = 5
测试数据 #16: Accepted, time = 109 ms, mem = 5424 KiB, score = 5
测试数据 #17: Accepted, time = 125 ms, mem = 5428 KiB, score = 5
测试数据 #18: Accepted, time = 109 ms, mem = 5428 KiB, score = 5
测试数据 #19: Accepted, time = 109 ms, mem = 5428 KiB, score = 5
Accepted, time = 715 ms, mem = 5432 KiB, score = 100

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>

using namespace std;

#define MAXN 200010

int Rank[MAXN],sa[MAXN],h[MAXN],p[27];
int n;
int x[MAXN],y[MAXN],t[MAXN];

char s[MAXN];

void Qsort(int l,int r) {
int i=l,j=r,m=(rand()*21)%(r-l+1)+l;
int X=x[m],Y=y[m];
do {
while (x[i]<X||(x[i]==X&&y[i]<Y)) i++;
while (x[j]>X||(x[j]==X&&y[j]>Y)) j--;
if (i<=j) {
swap(x[i],x[j]);
swap(y[i],y[j]);
swap(t[i],t[j]);
i++,j--;
}
} while (i<=j);
if (i<r) Qsort(i,r);
if (j>l) Qsort(l,j);
}

void Build() {
srand(time(NULL));
x[0]=y[0]=-1;
int j=1,R;
do {
for (int i=0;i++<n;) x[i]=Rank[i],y[i]=Rank[i+j],t[i]=i;
Qsort(1,n);
R=0;
for (int i=0;i++<n;) {
if (x[i]!=x[i-1]||y[i]!=y[i-1]) R++;
Rank[t[i]]=R;
}
j<<=1;
} while (j<=n&&R<n);
for (int i=0;i++<n;) sa[Rank[i]]=i;
memset(h,0,sizeof(h));
j=1;
for (int i=0;i++<n;) {
if (i==sa[1]) h[i]=j=0
; else {
j=j-1<0?0:--j;
h[i]=j;
for (int k=1;i+j+k-1<=n&&sa[Rank[i]-1]+j+k-1<=n;k++) {
if (s[i+j+k-1]==s[sa[Rank[i]-1]+j+k-1]) h[i]++ ; else break;
}
j=h[i];
}
}
}

void getstring() {
int c;
for (int i=0;i++<n;) {
for (c=getchar();!(c>=int('a')&&c<=int('z'));c=getchar()) ;
s[i]=char(c);
}
}

int main() {
scanf("%d",&n);
getstring();
memset(p,0,sizeof(p));
for (int i=0;i++<n;) p[int(s[i])-int('a')+1]=1;
for (int i=0;i++<26;) p[i]+=p[i-1];
for (int i=0;i++<n;) Rank[i]=p[int(s[i])-int('a')+1];
Build();
long long ans=0;
for (int i=0;i++<n;) {
ans+=(i-h[i]);
}
printf("%lld\n",ans);
return 0;
}

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 6212 KiB, score = 5

测试数据 #1: Accepted, time = 0 ms, mem = 6216 KiB, score = 5

测试数据 #2: Accepted, time = 0 ms, mem = 6220 KiB, score = 5

测试数据 #3: Accepted, time = 0 ms, mem = 6212 KiB, score = 5

测试数据 #4: Accepted, time = 0 ms, mem = 6212 KiB, score = 5

测试数据 #5: Accepted, time = 0 ms, mem = 6212 KiB, score = 5

测试数据 #6: Accepted, time = 0 ms, mem = 6212 KiB, score = 5

测试数据 #7: Accepted, time = 0 ms, mem = 6220 KiB, score = 5

测试数据 #8: Accepted, time = 0 ms, mem = 6220 KiB, score = 5

测试数据 #9: Accepted, time = 0 ms, mem = 6216 KiB, score = 5

测试数据 #10: Accepted, time = 15 ms, mem = 6216 KiB, score = 5

测试数据 #11: Accepted, time = 15 ms, mem = 6220 KiB, score = 5

测试数据 #12: Accepted, time = 15 ms, mem = 6220 KiB, score = 5

测试数据 #13: Accepted, time = 31 ms, mem = 6216 KiB, score = 5

测试数据 #14: Accepted, time = 31 ms, mem = 6220 KiB, score = 5

测试数据 #15: Accepted, time = 78 ms, mem = 6216 KiB, score = 5

测试数据 #16: Accepted, time = 62 ms, mem = 6216 KiB, score = 5

测试数据 #17: Accepted, time = 78 ms, mem = 6212 KiB, score = 5

测试数据 #18: Accepted, time = 78 ms, mem = 6212 KiB, score = 5

测试数据 #19: Accepted, time = 62 ms, mem = 6216 KiB, score = 5

Accepted, time = 465 ms, mem = 6220 KiB, score = 100

快排+倍增AC
测试数据 #0: Accepted, time = 0 ms, mem = 8496 KiB, score = 5

测试数据 #1: Accepted, time = 0 ms, mem = 8496 KiB, score = 5

测试数据 #2: Accepted, time = 10 ms, mem = 8460 KiB, score = 5

测试数据 #3: Accepted, time = 0 ms, mem = 8460 KiB, score = 5

测试数据 #4: Accepted, time = 15 ms, mem = 8460 KiB, score = 5

测试数据 #5: Accepted, time = 0 ms, mem = 8532 KiB, score = 5

测试数据 #6: Accepted, time = 0 ms, mem = 8568 KiB, score = 5

测试数据 #7: Accepted, time = 15 ms, mem = 8828 KiB, score = 5

测试数据 #8: Accepted, time = 15 ms, mem = 8828 KiB, score = 5

测试数据 #9: Accepted, time = 0 ms, mem = 8828 KiB, score = 5

测试数据 #10: Accepted, time = 14 ms, mem = 8828 KiB, score = 5

测试数据 #11: Accepted, time = 0 ms, mem = 8828 KiB, score = 5

测试数据 #12: Accepted, time = 14 ms, mem = 8828 KiB, score = 5

测试数据 #13: Accepted, time = 140 ms, mem = 8828 KiB, score = 5

测试数据 #14: Accepted, time = 128 ms, mem = 8828 KiB, score = 5

测试数据 #15: Accepted, time = 261 ms, mem = 8828 KiB, score = 5

测试数据 #16: Accepted, time = 220 ms, mem = 8828 KiB, score = 5

测试数据 #17: Accepted, time = 205 ms, mem = 8828 KiB, score = 5

测试数据 #18: Accepted, time = 261 ms, mem = 8828 KiB, score = 5

测试数据 #19: Accepted, time = 205 ms, mem = 8828 KiB, score = 5

Accepted, time = 1503 ms, mem = 8828 KiB, score = 100

测试数据 #0: Accepted, time = 15 ms, mem = 49988 KiB, score = 5

测试数据 #1: Accepted, time = 0 ms, mem = 49988 KiB, score = 5

测试数据 #2: Accepted, time = 15 ms, mem = 49988 KiB, score = 5

测试数据 #3: Accepted, time = 0 ms, mem = 49988 KiB, score = 5

测试数据 #4: Accepted, time = 0 ms, mem = 49988 KiB, score = 5

测试数据 #5: Accepted, time = 15 ms, mem = 49988 KiB, score = 5

测试数据 #6: Accepted, time = 0 ms, mem = 49988 KiB, score = 5

测试数据 #7: Accepted, time = 0 ms, mem = 50248 KiB, score = 5

测试数据 #8: Accepted, time = 15 ms, mem = 50248 KiB, score = 5

测试数据 #9: Accepted, time = 15 ms, mem = 50248 KiB, score = 5

测试数据 #10: Accepted, time = 15 ms, mem = 50248 KiB, score = 5

测试数据 #11: Accepted, time = 0 ms, mem = 50248 KiB, score = 5

测试数据 #12: Accepted, time = 15 ms, mem = 50248 KiB, score = 5

测试数据 #13: Accepted, time = 31 ms, mem = 50248 KiB, score = 5

测试数据 #14: Accepted, time = 138 ms, mem = 50248 KiB, score = 5

测试数据 #15: Accepted, time = 166 ms, mem = 50248 KiB, score = 5

测试数据 #16: Accepted, time = 167 ms, mem = 50248 KiB, score = 5

测试数据 #17: Accepted, time = 153 ms, mem = 50248 KiB, score = 5

测试数据 #18: Accepted, time = 167 ms, mem = 50248 KiB, score = 5

测试数据 #19: Accepted, time = 167 ms, mem = 50248 KiB, score = 5

后缀自动机裸题啊，效率O(n)

后缀数组例题啊！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 14：答案正确... 103ms

├ 测试数据 15：答案正确... 103ms

├ 测试数据 16：答案正确... 368ms

├ 测试数据 17：答案正确... 352ms

├ 测试数据 18：答案正确... 352ms

├ 测试数据 19：答案正确... 352ms

├ 测试数据 20：答案正确... 368ms

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

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

终于会写计数排的后缀数组了。。

0MS 秒闪

膜拜集训队论文

// EXTRABAGENZA

const maxn = 400000;

var xx,k,max,i,j,n,m,p : longint;

ans : qword;

h,x,r,sa,z,w,y : array[0..maxn] of longint;

procedure d_init;

var i : longint;

ch : char;

begin

readln(n);

max := 0; i := 0;

while ( not eof () ) and ( i n ) do

begin

inc(i); read(ch); r[i] := ord(ch) - 32; if r[i] > max then max := r[i];

if i mod 80 = 0 then readln;

end;

n := i;

inc(n); r[n] := 32;

end;

procedure check( a,b,j : longint );

begin

if ( y[a] = y ) and ( y[a+j] = y ) then dec(p);

end;

procedure main;

begin

for i := 1 to n do x[i] := r[i];

for i := 0 to max do w[i] := 0;

for i := 1 to n do inc(w[x[i]]);

for i := 1 to max do inc(w[i],w);

for i := n downto 1 do

begin

sa[w[x[i]]] := i;

dec(w[x[i]]);

end;

j := 1; p := 0;

while p n do

begin

p := 0; for i := n - j + 1 to n do begin inc(p); y[p] := i; end;

for i := 1 to n do if sa[i] > j then begin inc(p); y[p] := sa[i] - j; end;

for i := 1 to n do z[i] := x[y[i]];

for i := 0 to max do w[i] := 0;

for i := 1 to n do inc(w[z[i]]);

for i := 1 to max do inc(w[i],w);

for i := n downto 1 do begin sa[w[z[i]]] := y[i]; dec(w[z[i]]); end;

for i := 1 to n do y[i] := x[i];

p := 1; x[sa[1]] := p;

for i := 2 to n do begin inc(p); check( sa[i],sa,j ); x[sa[i]] := p; end;

max := p;

j := j shl 1;

end;

for i := 1 to n do y[sa[i]] := i;

k := 0;

for i := 1 to n do

begin

h[i] := k;

if k > 0 then dec(k);

j := sa[y[i]-1];

while ( r = r[j+k] ) do inc(k);

end;

ans := 0;

for i := 1 to n do

begin

xx := sa[i];

inc( ans,n-xx-h[xx] );

end;

writeln(ans);

end;

begin

d_init;

main;

end.

后缀数组，先搁着吧

对我来说的确是道难题

我太菜了,一个后缀数组的倍增算法看了一星期,今天才彻底领悟

回楼下：前面13组n

晕死 ， 我 用 快排+倍增 的预处理 也就是 O （n*log^2（n）） 才6000万+

其他 的 O（n） ……

然后 前13 组 0ms， 后面 全 超时 了 ……

why？？ puppy 不是 很 NX 的 吗 ……

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

把快排 改成 基数 排序 后：

├ 测试数据 16：答案正确... 181ms

├ 测试数据 17：答案正确... 166ms

├ 测试数据 18：答案正确... 181ms

├ 测试数据 19：答案正确... 134ms

├ 测试数据 20：答案正确... 150ms

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

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

谢 crash 提醒 ……

看来 log(n) 的 因子 不可忽略……

不可过分依赖 快排 ……

不可过分依赖 puppy ……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 14：答案正确... 25ms

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

├ 测试数据 16：答案正确... 494ms

├ 测试数据 17：答案正确... 541ms

├ 测试数据 18：答案正确... 478ms

├ 测试数据 19：答案正确... 822ms

├ 测试数据 20：答案正确... 478ms

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

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

怎么那么慢啊？

怎样0msAC?

orz神牛们！！！

Orz 罗穗骞