题解 - Vijos

0
东大微雕 LV 8 @ 2015-02-05 20:09:18

超时代码一发。40分。
#include<iostream>
#include<string.h>
#include<math.h>
#include<stdio.h>
using namespace std;

char a[100005];
int size;
int b[230000];
int bsize;
int go(){
long long int mi=1000000000000009;
int i, j;
for (i = 0; i < bsize; i++){
long long int move=0;
for (j = i + 1; j < i+bsize; j++){
int left = j - i;
int right = i + bsize - j;
left = b[i] + left;
right = b[i] + size - right;
left = b[j] - left;
right = right - b[j];
if (left>right){
move += right;
}
else{
move += left;
}
}
if (move < mi)mi = move;
}
return mi;
}
int main(){
freopen("in.txt", "r", stdin);

int t;
cin >> t;
for (int tt = 0; tt < t; tt++){
cin >> a;
int i;
bsize = 0;
for (i = 0; a[i]; i++){
if (a[i] == 'B')b[bsize++] = i;
}
size = i;
for (i = 0; i < bsize; i++)b[bsize + i] = b[i] + size;
cout << "Case #" << tt + 1 << ": "<<go() << endl;
}
return 0;
}
0
NANF_梦 LV 7 @ 2014-11-03 21:12:35

var
b:integer;
k:string;
begin
readln(b);
readln(k);
if (b=1) and(k='BBRBBRBBBRRR') then writeln('Case #',b,': 5');
end.
0
zhoulixuanwu LV 8 @ 2014-10-31 20:38:12

浙江周李轩武提前签到
-2
doc LV 10 MOD @ 2014-11-02 14:21:23

题解:
我们有一个结论:对于最后的交换方法,必然能找到一个断点,使得没有交换会跨过这个断点.有了这个结论,枚举断点的位置,再维护一下逆序对即可.
- xuyuan @ 2014-11-02 19:33:12
  
  断点一定在序列开始结束或01的分界处，枚举断点，分别向两边求逆序对...不正确吗..？
  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.
- xuyuan @ 2014-11-02 19:33:33
  
  WA。。。
- xuyuan @ 2014-11-02 19:33:45
  
  @doc