12 条题解

  • 2
    @ 2014-07-20 09:48:27

    树状数组维护,加枚举顶点

    const maxn=1002;
    type point=^node;
    node=record
    x:longint;
    next:point;
    end;
    var i,j,nn,x,y,sum,k:longint;
    c:char;
    next:array[0..maxn] of point;
    s,n,w,e:array[0..maxn,0..maxn] of longint;
    t:array[1..maxn] of longint;
    m,ans:array[0..maxn,0..maxn,0..1] of boolean;
    p:point;
    procedure add(x,sum:longint);
    begin
    while (x<=nn) do
    begin
    t[x]:=t[x]+sum;
    x:=x+x and -x;
    end;
    end;
    function find(x:longint):longint;
    var s:longint;
    begin
    s:=0;
    while (x>0) do
    begin
    s:=s+t[x];
    x:=x-x and -x;
    end;
    exit(s);
    end;
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a) else exit(b);
    end;
    begin
    readln(nn);
    for i:=1 to nn+1 do
    begin
    for j:=1 to 2*nn+1 do
    begin
    read(c);
    case c of
    '_':m[i,j div 2,0]:=true;
    '|':m[i-1,(j+1) div 2,1]:=true;
    end;
    end;
    readln;
    end;
    for i:=1 to nn+1 do
    for j:=1 to nn+1 do
    begin
    if m[i,j-1,0] then e[i,j]:=e[i,j-1]+1;
    if m[i-1,j,1] then n[i,j]:=n[i-1,j]+1;
    end;
    for i:=nn+1 downto 1 do
    for j:=nn+1 downto 1 do
    begin
    if m[i,j,0] then w[i,j]:=w[i,j+1]+1;
    if m[i,j,1] then s[i,j]:=s[i+1,j]+1;
    end;
    inc(nn);
    for i:=1 to nn*2 do
    begin
    if i<=nn then
    begin
    x:=1; y:=i;
    end else
    begin
    x:=i-nn; y:=nn;
    end;
    fillchar(next,sizeof(next),0);
    fillchar(t,sizeof(t),0);
    while (x<=nn) and (y>=1) do
    begin
    p:=next[x];
    while (p<>nil) do
    begin
    add(p^.x,-1);
    p:=p^.next;
    end;
    if w[x,y]>n[x,y] then
    begin
    if (find(x-n[x,y]-1)-find(x-min(w[x,y],n[x,y]+1+n[x-n[x,y]-1,y])-1))>0 then
    ans[x-n[x,y]-1,y,1]:=true else
    end;
    if w[x,y]<n[x,y] then
    begin
    if (find(x-w[x,y]-1)-find(x-min(w[x,y]+1+w[x,y+w[x,y]+1],n[x,y])-1))>0 then
    ans[x,y+w[x,y],0]:=true;
    end;
    add(x,1);
    new(p);
    k:=x+min(s[x,y],e[x,y])+1;
    p^.x:=x; p^.next:=next[k];
    next[k]:=p;
    inc(x); dec(y);
    end;
    if i<=nn then
    begin
    x:=i; y:=1;
    end else
    begin
    x:=nn; y:=i-nn+1;
    end;
    fillchar(next,sizeof(next),0);
    fillchar(t,sizeof(t),0);
    while (x>=1) and (y<=nn) do
    begin
    p:=next[x];
    while (p<>nil) do
    begin
    add(p^.x,-1);
    p:=p^.next;
    end;
    if e[x,y]<s[x,y] then
    begin
    if find(x+min(s[x,y],e[x,y]+1+e[x,y-e[x,y]-1]))-find(x+e[x,y])>0 then
    ans[x,y-e[x,y]-1,0]:=true;
    end else if e[x,y]>s[x,y] then
    begin
    if find(x+min(s[x,y]+1+s[x+s[x,y]+1,y],e[x,y]))-find(x+s[x,y])>0 then
    ans[x+s[x,y],y,1]:=true;
    end;
    add(x,1);
    k:=x-min(n[x,y],w[x,y])-1;
    new(p);
    p^.x:=x; p^.next:=next[k];
    next[k]:=p;
    dec(x); inc(y);
    end;
    end;
    sum:=0;
    for i:=1 to nn do
    for j:=1 to nn do
    begin
    if ans[i,j][0] then inc(sum);
    if ans[i,j][1] then inc(sum);
    end;
    writeln(sum);
    end.

  • 0
    @ 2015-06-30 10:54:06

    const maxn=1002;
    type point=^node;
    node=record
    x:longint;
    next:point;
    end;
    var i,j,nn,x,y,sum,k:longint;
    c:char;
    next:array[0..maxn] of point;
    s,n,w,e:array[0..maxn,0..maxn] of longint;
    t:array[1..maxn] of longint;
    m,ans:array[0..maxn,0..maxn,0..1] of boolean;
    p:point;
    procedure add(x,sum:longint);
    begin
    while (x<=nn) do
    begin
    t[x]:=t[x]+sum;
    x:=x+x and -x;
    end;
    end;
    function find(x:longint):longint;
    var s:longint;
    begin
    s:=0;
    while (x>0) do
    begin
    s:=s+t[x];
    x:=x-x and -x;
    end;
    exit(s);
    end;
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a) else exit(b);
    end;
    begin
    readln(nn);
    for i:=1 to nn+1 do
    begin
    for j:=1 to 2*nn+1 do
    begin
    read(c);
    case c of
    '_':m[i,j div 2,0]:=true;
    '|':m[i-1,(j+1) div 2,1]:=true;
    end;
    end;
    readln;
    end;
    for i:=1 to nn+1 do
    for j:=1 to nn+1 do
    begin
    if m[i,j-1,0] then e[i,j]:=e[i,j-1]+1;
    if m[i-1,j,1] then n[i,j]:=n[i-1,j]+1;
    end;
    for i:=nn+1 downto 1 do
    for j:=nn+1 downto 1 do
    begin
    if m[i,j,0] then w[i,j]:=w[i,j+1]+1;
    if m[i,j,1] then s[i,j]:=s[i+1,j]+1;
    end;
    inc(nn);
    for i:=1 to nn*2 do
    begin
    if i<=nn then
    begin
    x:=1; y:=i;
    end else
    begin
    x:=i-nn; y:=nn;
    end;
    fillchar(next,sizeof(next),0);
    fillchar(t,sizeof(t),0);
    while (x<=nn) and (y>=1) do
    begin
    p:=next[x];
    while (p<>nil) do
    begin
    add(p^.x,-1);
    p:=p^.next;
    end;
    if w[x,y]>n[x,y] then
    begin
    if (find(x-n[x,y]-1)-find(x-min(w[x,y],n[x,y]+1+n[x-n[x,y]-1,y])-1))>0 then
    ans[x-n[x,y]-1,y,1]:=true else
    end;
    if w[x,y]<n[x,y] then
    begin
    if (find(x-w[x,y]-1)-find(x-min(w[x,y]+1+w[x,y+w[x,y]+1],n[x,y])-1))>0 then
    ans[x,y+w[x,y],0]:=true;
    end;
    add(x,1);
    new(p);
    k:=x+min(s[x,y],e[x,y])+1;
    p^.x:=x; p^.next:=next[k];
    next[k]:=p;
    inc(x); dec(y);
    end;
    if i<=nn then
    begin
    x:=i; y:=1;
    end else
    begin
    x:=nn; y:=i-nn+1;
    end;
    fillchar(next,sizeof(next),0);
    fillchar(t,sizeof(t),0);
    while (x>=1) and (y<=nn) do
    begin
    p:=next[x];
    while (p<>nil) do
    begin
    add(p^.x,-1);
    p:=p^.next;
    end;
    if e[x,y]<s[x,y] then
    begin
    if find(x+min(s[x,y],e[x,y]+1+e[x,y-e[x,y]-1]))-find(x+e[x,y])>0 then
    ans[x,y-e[x,y]-1,0]:=true;
    end else if e[x,y]>s[x,y] then
    begin
    if find(x+min(s[x,y]+1+s[x+s[x,y]+1,y],e[x,y]))-find(x+s[x,y])>0 then
    ans[x+s[x,y],y,1]:=true;
    end;
    add(x,1);
    k:=x-min(n[x,y],w[x,y])-1;
    new(p);
    p^.x:=x; p^.next:=next[k];
    next[k]:=p;
    dec(x); inc(y);
    end;
    end;
    sum:=0;
    for i:=1 to nn do
    for j:=1 to nn do
    begin
    if ans[i,j][0] then inc(sum);
    if ans[i,j][1] then inc(sum);
    end;
    writeln(sum);
    end.

  • 0
    @ 2014-07-20 09:48:39

    const maxn=1002;
    type point=^node;
    node=record
    x:longint;
    next:point;
    end;
    var i,j,nn,x,y,sum,k:longint;
    c:char;
    next:array[0..maxn] of point;
    s,n,w,e:array[0..maxn,0..maxn] of longint;
    t:array[1..maxn] of longint;
    m,ans:array[0..maxn,0..maxn,0..1] of boolean;
    p:point;
    procedure add(x,sum:longint);
    begin
    while (x<=nn) do
    begin
    t[x]:=t[x]+sum;
    x:=x+x and -x;
    end;
    end;
    function find(x:longint):longint;
    var s:longint;
    begin
    s:=0;
    while (x>0) do
    begin
    s:=s+t[x];
    x:=x-x and -x;
    end;
    exit(s);
    end;
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a) else exit(b);
    end;
    begin
    assign(input,'temp.in');reset(input);
    readln(nn);
    for i:=1 to nn+1 do
    begin
    for j:=1 to 2*nn+1 do
    begin
    read(c);
    case c of
    '_':m[i,j div 2,0]:=true;
    '|':m[i-1,(j+1) div 2,1]:=true;
    end;
    end;
    readln;
    end;
    for i:=1 to nn+1 do
    for j:=1 to nn+1 do
    begin
    if m[i,j-1,0] then e[i,j]:=e[i,j-1]+1;
    if m[i-1,j,1] then n[i,j]:=n[i-1,j]+1;
    end;
    for i:=nn+1 downto 1 do
    for j:=nn+1 downto 1 do
    begin
    if m[i,j,0] then w[i,j]:=w[i,j+1]+1;
    if m[i,j,1] then s[i,j]:=s[i+1,j]+1;
    end;
    inc(nn);
    for i:=1 to nn*2 do
    begin
    if i<=nn then
    begin
    x:=1; y:=i;
    end else
    begin
    x:=i-nn; y:=nn;
    end;
    fillchar(next,sizeof(next),0);
    fillchar(t,sizeof(t),0);
    while (x<=nn) and (y>=1) do
    begin
    p:=next[x];
    while (p<>nil) do
    begin
    add(p^.x,-1);
    p:=p^.next;
    end;
    if w[x,y]>n[x,y] then
    begin
    if (find(x-n[x,y]-1)-find(x-min(w[x,y],n[x,y]+1+n[x-n[x,y]-1,y])-1))>0 then
    ans[x-n[x,y]-1,y,1]:=true else
    end;
    if w[x,y]<n[x,y] then
    begin
    if (find(x-w[x,y]-1)-find(x-min(w[x,y]+1+w[x,y+w[x,y]+1],n[x,y])-1))>0 then
    ans[x,y+w[x,y],0]:=true;
    end;
    add(x,1);
    new(p);
    k:=x+min(s[x,y],e[x,y])+1;
    p^.x:=x; p^.next:=next[k];
    next[k]:=p;
    inc(x); dec(y);
    end;
    if i<=nn then
    begin
    x:=i; y:=1;
    end else
    begin
    x:=nn; y:=i-nn+1;
    end;
    fillchar(next,sizeof(next),0);
    fillchar(t,sizeof(t),0);
    while (x>=1) and (y<=nn) do
    begin
    p:=next[x];
    while (p<>nil) do
    begin
    add(p^.x,-1);
    p:=p^.next;
    end;
    if e[x,y]<s[x,y] then
    begin
    if find(x+min(s[x,y],e[x,y]+1+e[x,y-e[x,y]-1]))-find(x+e[x,y])>0 then
    ans[x,y-e[x,y]-1,0]:=true;
    end else if e[x,y]>s[x,y] then
    begin
    if find(x+min(s[x,y]+1+s[x+s[x,y]+1,y],e[x,y]))-find(x+s[x,y])>0 then
    ans[x+s[x,y],y,1]:=true;
    end;
    add(x,1);
    k:=x-min(n[x,y],w[x,y])-1;
    new(p);
    p^.x:=x; p^.next:=next[k];
    next[k]:=p;
    dec(x); inc(y);
    end;
    end;
    sum:=0;
    for i:=1 to nn do
    for j:=1 to nn do
    begin
    if ans[i,j][0] then inc(sum);
    if ans[i,j][1] then inc(sum);
    end;
    writeln(sum);
    close(input);
    end.

  • 0
    @ 2013-07-17 10:16:31

    个人认为要用至少二维的树状数组去做,把每一条边分配到不同的c[i,j],然后进行反复求和,哪一个正方形只缺一边就记录下来,然后开一个记录表,防止重复,嗯,这只是个人的一些想法,具体我还没能力去做,希望可以帮助一下...

  • 0
    @ 2009-09-03 20:30:52

    Orz hyc神牛

    PS::常数卡得好紧啊

  • 0
    @ 2009-08-17 15:41:16

    这题是不是用搜索啊??

  • 0
    @ 2009-09-04 15:49:11

    常数没卡啊……线段树都放过了……

  • 0
    @ 2009-08-17 10:52:53

    我有点怀疑数据有问题,因为我只能得60分。有几个点莫名其妙的WA

    囧,交了十多次都是60 - -|||

  • 0
    @ 2009-08-17 09:38:04

    谁过了?

    难度0?

  • 0
    @ 2009-08-17 08:23:46

    哇哇

  • 0
    @ 2009-08-16 09:50:34

    nnd,又地板

  • 0
    @ 2009-08-10 20:58:36

    Orz 教主 and tky神牛

  • 1

信息

ID
1618
难度
8
分类
搜索 | 枚举数据结构 | 树状数组 点击显示
标签
递交数
344
已通过
32
通过率
9%
被复制
1
上传者