为什么WA ...TAT

断点一定在序列开始结束或01的分界处,枚举断点,分别向两边求逆序对...不正确吗..?
ps:输出时":"后面有空格么 @doc
type hehe=record
a:array[0..100001]of integer;
end;
var n,i,j,len,k,min,c,d:longint;
tem:array[1..10]of hehe;
s:string;
t,tp:array[0..100001]of integer;
ans,anss:array[1..10]of longint;
procedure merge1(head,mid,tail,num:longint);
var tt,tl,tr,j:longint;
begin
tt:=head;
tl:=head;
tr:=mid+1;
while (tl<=mid)and(tr<=tail)do
begin
if tem[num].a[tl]>=tem[num].a[tr] then
begin
t[tt]:=tem[num].a[tl];
inc(tl);
end
else begin
t[tt]:=tem[num].a[tr];
inc(tr);
anss[num]:=anss[num]+mid+1-tl;
end;
inc(tt);

end;
while (tl<=mid) do begin t[tt]:=tem[num].a[tl];inc(tl);inc(tt); end;
while (tr<=tail) do begin t[tt]:=tem[num].a[tr];inc(tr);inc(tt); end;
for j:=head to tail do tem[num].a[j]:=t[j];
end;
procedure merge_sort1(head,tail,num:longint);
var mid:longint;
begin
if head<tail then
begin
mid:=(head+tail)div 2;
merge_sort1(head,mid,num);
merge_sort1(mid+1,tail,num);
merge1(head,mid,tail,num);
end;
end;
procedure merge(head,mid,tail,num:longint);
var tt,tl,tr,i:longint;
begin
tt:=head;
tl:=head;
tr:=mid+1;
while (tl<=mid)and(tr<=tail)do
begin
if tem[num].a[tl]<=tem[num].a[tr] then
begin
t[tt]:=tem[num].a[tl];
inc(tl);
end
else begin
t[tt]:=tem[num].a[tr];
inc(tr);
ans[num]:=ans[num]+mid+1-tl;
end;
inc(tt);
end;
while (tl<=mid) do begin t[tt]:=tem[num].a[tl];inc(tl);inc(tt); end;
while (tr<=tail) do begin t[tt]:=tem[num].a[tr];inc(tr);inc(tt); end;
for i:=head to tail do tem[num].a[i]:=t[i];
end;
procedure merge_sort(head,tail,num:longint);
var mid:longint;
begin
if head<>tail then
begin
mid:=(head+tail)div 2;
merge_sort(head,mid,num);
merge_sort(mid+1,tail,num);
merge(head,mid,tail,num);
end;
end;
begin
readln(n);
fillchar(tem,sizeof(tem),2);
fillchar(ans,sizeof(ans),0);
for i:=1 to n do tem[i].a[0]:=0;
for i:=1 to n do
begin
readln(s);
fillchar(t,sizeof(t),2);
tem[i].a[0]:=length(s);
for j:=1 to tem[i].a[0] do
if s[j]='B' then tem[i].a[j]:=0 else tem[i].a[j]:=1;
for j:=1 to tem[i].a[0] do tp[j]:=tem[i].a[j];
merge_sort(1,tem[i].a[0],i);
min:=ans[i];
for j:=1 to tem[i].a[0] do tem[i].a[j]:=tp[j];
for j:=2 to tem[i].a[0] do
if (tem[i].a[j]=0)and(tem[i].a[j-1]=1) then
begin
ans[i]:=0;anss[i]:=0;
merge_sort1(1,j-1,i);
merge_sort(j,tem[i].a[0],i);
if min>ans[i]+anss[i] then min:=ans[i]+anss[i];
for k:=1 to tem[i].a[0] do tem[i].a[k]:=tp[k];
end;
if tem[i].a[tem[i].a[0]]=1 then
begin
ans[i]:=0;
anss[i]:=0;
merge_sort1(1,tem[i].a[0],i);
if min>ans[i]+anss[i] then min:=ans[i]+anss[i];
writeln('Case #',i,':',min);
end;
end;
end.

3 条评论

  • @ 2015-08-03 10:55:02

    111111112222222223333333333334444444444444444455555666666666777888899999990000qqwwwwwwwweeeeeeeeeeerrrrrrrrtttttttttyyyyyyyyyuuuuuuuiiiiiioooooooopppppaassssssddddddddfffffffhhhhhhgjkllzzzzxxxxxxxccccccvvvvvvvbbbbbbbbnnnnnnnnnnnmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

  • @ 2014-11-03 08:08:38

    为什么复制过来总是没有格式……

  • @ 2014-11-03 08:08:16

    a:array[0..100001]of integer;
    end;
    var n,i,j,len,k,min,c,d:longint;
    tem:array[1..10]of hehe;
    s:string;
    t,tp:array[0..100001]of integer;
    ans,anss:array[1..10]of longint;
    procedure merge1(head,mid,tail,num:longint);
    var tt,tl,tr,j:longint;
    begin
    tt:=head;
    tl:=head;
    tr:=mid+1;
    while (tl<=mid)and(tr<=tail)do
    begin
    if tem[num].a[tl]>=tem[num].a[tr] then
    begin
    t[tt]:=tem[num].a[tl];
    inc(tl);
    end
    else begin
    t[tt]:=tem[num].a[tr];
    inc(tr);
    anss[num]:=anss[num]+mid+1-tl;
    end;
    inc(tt);

    end;
    while (tl<=mid) do begin t[tt]:=tem[num].a[tl];inc(tl);inc(tt); end;
    while (tr<=tail) do begin t[tt]:=tem[num].a[tr];inc(tr);inc(tt); end;
    for j:=head to tail do tem[num].a[j]:=t[j];
    end;
    procedure merge_sort1(head,tail,num:longint);
    var mid:longint;
    begin
    if head<tail then
    begin
    mid:=(head+tail)div 2;
    merge_sort1(head,mid,num);
    merge_sort1(mid+1,tail,num);
    merge1(head,mid,tail,num);
    end;
    end;
    procedure merge(head,mid,tail,num:longint);
    var tt,tl,tr,i:longint;
    begin
    tt:=head;
    tl:=head;
    tr:=mid+1;
    while (tl<=mid)and(tr<=tail)do
    begin
    if tem[num].a[tl]<=tem[num].a[tr] then
    begin
    t[tt]:=tem[num].a[tl];
    inc(tl);
    end
    else begin
    t[tt]:=tem[num].a[tr];
    inc(tr);
    ans[num]:=ans[num]+mid+1-tl;
    end;
    inc(tt);
    end;
    while (tl<=mid) do begin t[tt]:=tem[num].a[tl];inc(tl);inc(tt); end;
    while (tr<=tail) do begin t[tt]:=tem[num].a[tr];inc(tr);inc(tt); end;
    for i:=head to tail do tem[num].a[i]:=t[i];
    end;
    procedure merge_sort(head,tail,num:longint);
    var mid:longint;
    begin
    if head<>tail then
    begin
    mid:=(head+tail)div 2;
    merge_sort(head,mid,num);
    merge_sort(mid+1,tail,num);
    merge(head,mid,tail,num);
    end;
    end;
    begin
    readln(n);
    fillchar(tem,sizeof(tem),2);
    fillchar(ans,sizeof(ans),0);
    for i:=1 to n do tem[i].a[0]:=0;
    for i:=1 to n do
    begin
    readln(s);
    fillchar(t,sizeof(t),2);
    tem[i].a[0]:=length(s);
    for j:=1 to tem[i].a[0] do
    if s[j]='B' then tem[i].a[j]:=0 else tem[i].a[j]:=1;
    // for j:=1 to tem[i].a[0] do write(tem[i].a[j],' ');
    // writeln;
    for j:=1 to tem[i].a[0] do tp[j]:=tem[i].a[j];
    merge_sort(1,tem[i].a[0],i);
    min:=ans[i];
    // writeln(min);
    for j:=1 to tem[i].a[0] do tem[i].a[j]:=tp[j];
    // for j:=1 to tem[i].a[0] do write(tem[i].a[j],' ');
    // writeln;
    for j:=2 to tem[i].a[0] do
    if (tem[i].a[j]=0)and(tem[i].a[j-1]=1) then
    begin
    ans[i]:=0;anss[i]:=0;
    merge_sort1(1,j-1,i);
    merge_sort(j,tem[i].a[0],i);
    // writeln(j,' ',anss[i],' ',ans[i],' ',anss[i]+ans[i]);
    if min>ans[i]+anss[i] then min:=ans[i]+anss[i];
    for k:=1 to tem[i].a[0] do tem[i].a[k]:=tp[k];
    end;
    if tem[i].a[tem[i].a[0]]=1 then
    begin
    ans[i]:=0;
    anss[i]:=0;
    merge_sort1(1,tem[i].a[0],i);
    if min>ans[i]+anss[i] then min:=ans[i]+anss[i];
    writeln('Case #',i,':',min);
    end;
    end;
    end.

  • 1

信息

ID
1900
难度
9
分类
(无)
标签
(无)
递交数
331
已通过
14
通过率
4%
被复制
3
上传者