Daily Archives: 23 9 月, 2012

CF 187A(从后取数的重排数列）

Posted on by

题目大意：一串数，每次把最后那个数挪到前面任意位置，就最少挪动次数

显然一个数最多挪一次（只能从后取的话，插2次的一定能变成1次）

因此找最后挪动的数即可，最后挪动的数即由于与下序列的连线与之前的交叉，其它数无论怎么挪都无法影响到它）

Program DD;
const
   maxn=200000;
var
   n,i,j,l,r:longint;
   a,b,hposa,hposb:array[1..maxn] of longint;
begin
   read(n);
   for i:=1 to n do
   begin
      read(a[i]);
      hposa[a[i]]:=i;
   end;
   for i:=1 to n do
   begin
      read(b[i]);
      hposb[b[i]]:=i;
   end;
   r:=0;
   for i:=1 to n do
   begin
       if r<hposb[a[i]] then r:=hposb[a[i]]
       else break;
   end;
   if (r=hposb[a[i]]) then writeln('0') else
   writeln(n-i+1);

end.

POJ 2588(解析几何+并查集）

Posted on by

题目就是早从左到右的路

注意输入的实数

这题图画好就行，别像我一开始把图弄反就成

从上开始找，若找到一个与下边界相邻的就无解，找到与左边相邻的记圆与左边界相交的下边的点（相当于左上角挖去一块），右边同理。

Program snake;
const
   maxn=1000;
var
   n,i,j:longint;
   x,y,r,lc,rc:array[1..maxn] of double;
   maxl,maxr:double;
   father:array[1..maxn] of longint;
   b,up,down,left,right:array[1..maxn] of boolean;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
Procedure union(x,y:longint);
begin
   father[father[x]]:=father[father[y]];
end;
function distance(i,j:longint):double;
begin
   exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));
end;
function dis(x1,y1,x2,y2:double):double;
begin
   exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;

begin
   fillchar(b,sizeof(b),false);
   fillchar(up,sizeof(up),false);
   fillchar(down,sizeof(down),false);
   fillchar(left,sizeof(left),false);
   fillchar(right,sizeof(right),false);
   fillchar(lc,sizeof(lc),0);
   fillchar(rc,sizeof(rc),0);
   maxl:=1000;maxr:=1000;

   read(n);
   for i:=1 to n do
   begin
      read(x[i],y[i],r[i]);
      father[i]:=i;
      for j:=1 to i-1 do
         if distance(i,j)<r[i]+r[j] then
            if getfather(i)<>getfather(j) then
               union(i,j);
      if (y[i]<r[i]) then down[i]:=true;
      if (y[i]+r[i]>1000) then up[i]:=true;
      if (x[i]<r[i]) then
      begin
         left[i]:=true;
         lc[i]:=y[i]-sqrt(sqr(r[i])-sqr(x[i]));
      end;
      if (x[i]+r[i]>1000) then
      begin
         right[i]:=true;
         rc[i]:=y[i]-sqrt(sqr(r[i])-sqr(1000-x[i]));
      end;

   end;
   for i:=1 to n do
      if (up[i]) and not(b[i]) then
      begin
         for j:=1 to n do
            if father[i]=father[j] then
            begin
               b[j]:=true;
               if (down[j]) then
               begin
                  writeln('Bill will be bitten.');
                  halt;
               end;
               if left[j] then
               begin
                  if lc[j]<maxl then maxl:=lc[j];

               end;
               if right[j] then
               begin
                  if rc[j]<maxr then maxr:=rc[j];
               end;


            end;
      end;
   writeln('Bill enters at (0.00, ',maxl:2:2,') and leaves at (1000.00, ',maxr:2:2,').');




end.

POJ 3122(二分答案）

Posted on by

二分答案……

Program pie;
const
   lef=0.00001;
var
   t,n,f,i,j:longint;
   r:array[1..10000] of longint;
   s:array[1..10000] of double;
   maxs:double;
procedure sort(l,r:double);
var
   m:real;
   i,j,tot:longint;
begin
   m:=(l+r)/2;
   tot:=0;
   for i:=1 to n do inc(tot,trunc(s[i]/m));

   if tot>=f then
   begin
      if r-l<lef then writeln(r:4:4)
      else sort(m,r);


   end
   else sort(l,m);










end;
begin
   read(t);
   while (t>0) do
   begin
      read(n,f);
      inc(f);
      for i:=1 to n do
      begin
         read(r[i]);
         s[i]:=sqr(r[i])*pi;
      end;
      maxs:=s[1];
      for i:=2 to n do
         if maxs<s[i] then maxs:=s[i];
      sort(0,maxs);

      dec(t);
   end;
end.

POJ 3844(同余）

Posted on by

果断同余……

D[j]-D[i]  mod  k =0

D[j]=D[i]

求有多少相等数对，用队列O(n)

Program P3844;
const
   maxn=50000;
   maxd=1000000;
var
   ans,t,f,n,i,j:longint;
   d:array[0..maxn] of longint;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;j:=r;
   m:=d[(l+r) shr 1];
   repeat
      while d[i]<m do inc(i);
      while d[j]>m do dec(j);
      if i<=j then
      begin
         p:=d[i];
         d[i]:=d[j];
         d[j]:=p;
         inc(i);dec(j);
      end;

   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);

end;
begin
   read(t);
   d[0]:=0;
   while (t>0) do
   begin
      read(f,n);
      for i:=1 to n do
      begin
         read(d[i]);
         d[i]:=(d[i]+d[i-1]) mod f;
      end;
      qsort(1,n);

      ans:=0;
      i:=0;j:=0;
      while (i<=n) do
      begin
         while (d[i]=d[j]) and (j<n) do inc(j);
         if d[i]<>d[j] then dec(j);
         inc(ans,((j-i+1)*(j-i)) shr 1);
         i:=j+1;
         inc(j);
      end;


      writeln(ans);

      dec(t);
   end;
end.