- 学姐吃寿司
- 2014-11-02 19:31:48 @
断点一定在序列开始结束或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 条评论
-
minecraft1.8.2 LV 8 @ 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
- 上传者