首页 » OI » 正文

noi.openjudge.cn题解

此处只写好多人挂了的题……

查找最接近的元素
http://noi.openjudge.cn/ch0111/01/
Code:

program ch011101;
var
    n,l,r,x,m,i,t,ans,k:longint;
    b:boolean;
    a:array[0..5000000] of longint;
begin
    readln(n);
    for i:=1 to n do read(a[i]);
    readln(m);
    for k:=1 to m do begin
      readln(t);
      l:=1;
      r:=n;
      b:=true;
      while l<r do begin
        x:=(l+r) div 2;
        if a[x]=t then begin b:=false; writeln(t); break; end;
        if t>a[x] then l:=x+1;
        if t<a[x] then r:=x;
      end;
      if b then begin
        ans:=maxlongint;
        for i:=-1 to 1 do if (r+i>0) and (r+i<=n) then if abs(a[r+i]-t)<abs(ans-t) then ans:=a[r+i];
        writeln(ans);
      end;
    end;
end.

切分矩形组
http://noi.openjudge.cn/ch0111/03/
Code: //个人觉得此题数据有误,见代码注释。

program ch011103;
var
    n,i,l,r,max,t,w,hh,x:longint;ans,ans2:int64;
    a,b,h:array[0..50000] of longint;
procedure asd(x:longint);
    var i:longint;
    begin
        ans:=0;ans2:=0;
        for i:=1 to n do begin
          if x>=b[i] then ans:=ans+(b[i]-a[i])*h[i];
          if x<=a[i] then ans2:=ans2+(b[i]-a[i])*h[i];
          if (x>a[i]) and (x<b[i]) then begin
            ans:=ans+(x-a[i]+1)*h[i]; //此处不应有+1,23333333333 But,数据就是这样!
            ans2:=ans2+(b[i]-x)*h[i];
          end;
        end;
    end;
begin
    readln(n);
    for i:=1 to n do begin
      readln(l,t,w,hh);
      a[i]:=l;b[i]:=l+w;h[i]:=hh;
      if b[i]>max then max:=b[i];
    end;
    l:=0;
    r:=max;
    while l<r do begin
      x:=(l+r) div 2;
      asd(x);
      if ans<ans2 then l:=x+1;
      if ans>=ans2 then r:=x;
    end;
    writeln(r);
end.

网线主管
http://noi.openjudge.cn/ch0111/04/
Code:

program ch011104;
var
    n,k,max,i,l,r,x:longint;t:real;
    a:array[0..50000] of longint;
function can:boolean;
    var i,t:longint;
    begin
        t:=0;
        for i:=1 to n do t:=t+a[i] div x;
        if t>=k then exit(true) else exit(false);
    end;
begin
    readln(n,k);
    max:=0;
    for i:=1 to n do begin readln(t); a[i]:=round(t*100); if a[i]>max then max:=a[i]; end;
    l:=1;
    r:=max+1;
    while l<r do begin
      x:=(l+r) div 2;
      if can then l:=x+1
      else r:=x;
    end;
    writeln((r-1)/100:0:2);
end.

带通配符的字符串匹配
http://noi.openjudge.cn/ch0206/6252/
Code:

program ch02066252;
var
    s1,s2:string;
    i,j,k:longint;
    f:array[0..50,-1..50] of boolean;
begin
    readln(s1);
    readln(s2);
    f[0,0]:=true;
    for i:=1 to length(s1) do
    for j:=0 to length(s2) do
      if s1[i]='*' then begin if f[i-1,j] or f[i,j-1] then f[i,j]:=true; end
      else if s1[i]='?' then begin if f[i-1,j-1] then f[i,j]:=true; end
      else if f[i-1,j-1] and (s1[i]=s2[j]) then f[i,j]:=true;
    if f[length(s1),length(s2)] then writeln('matched') else writeln('not matched');
end.

An Easy Problem
http://noi.openjudge.cn/ch0406/1455/
Code:

program ch04061455;
var
    n,l,i,c:longint;
begin
    while true do begin
      l:=0;c:=0;
      readln(n);
      if n=0 then break;
      while n and 1=0 do begin inc(l); n:=n>>1; end;
      while n and 1=1 do begin inc(c); inc(l); n:=n>>1; end;
      n:=n or 1;
      for i:=1 to l-c+1 do n:=n<<1;
      for i:=1 to c-1 do begin n:=n<<1; n:=n or 1; end;
      writeln(n);
    end;
end.

发表评论