注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2727】【Hnoi2012】【双十字】  

2014-04-18 20:06:17|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:给出一个01矩阵,然后求出双十字的个数。

   咱们首先来看看双十字是怎么确定的...首先双十字需要一个轴,然后咱们需要两个水平直线的中点,然后就是它们的长度。
   咱们尝试来枚举其中一些元素,然后推出其他的元素的个数。咱们可以枚举双十字的下水平直线的中心点,那么咱们就可以确定中心轴,以及上水平直线的中心点。然后咱们会发现咱们需要多记录一些信息才行...,设l[],r[],up[]表示某个点向上向下向左向右能够沿着1延伸的最长距离,那么min(L[],R[])就是它的下水平直线的距离的上限,咱们的问题就是统计上面的[y-up[]+2,y-2]区间内部的min(L[],R[]),然后能够迅速得出答案。这个可以用Hash表做,然后咱们就可以计算每一种长度X所提供的贡献,设当前枚举下水平直线的长度min(L[],R[])=Y,则 每一个的贡献为∑(Y-i )(1<=i<=min(X,Y)),然后这个的复杂度就是O(RCmin(R,C))的,还不够饿...

  突然发现自己又脑洞了...实际上咱们可以把一个点能最多能扩展的长度设为L,咱们每新处理完一个点,实际上就相当于多了L-1条线段,长度为1~L-1,然后咱们开个长度数组统计每一种长度出现的次数,这个就是区间赋值...然后咱们每查询一个点实际上就是查询L以下的十字架的个数,也就是区间求和....这样子就可以用一个线段树把复杂度降到O(RC Rlog(min(R,C)))。突然发现不是降而是升了额....

  但是感觉还是不够好...咱们看看每一个长度的贡献能否直接算出来....
  假设当前点i上面有一个点j,当前点能延伸的最长长度为L[i],上面点j的最长长度为L[j],那么就有:
  1)当L[j]>=L[i]的时候,方案是(L[i]-1)+(L[i]-2)...+1= L[i]*(L[i]-1)/2
  2)当L[j]<L[i]的时候,咱们枚举实际的L[i],可以分成两半,一个是当前实际的L[i]<=L[j]的时候,贡献是(L[j]-1)+(L[j]-2)...+1=L[j]*(L[j]-1)/2
       L[i]>L[j]的时候,对于L[i],L[j]不取0就都可以,所以是 L[j]*(L[i]-L[j])
       总的答案就是 L[j]*(L[j]-1)/2+L[j]*(L[i]-L[j])
  咱们可以分开计算额...首先一个树状数组存某个长度出现的次数,这个就可以统计L[j]>=L[i]的了。(推荐倒着存)
 然后就是第二个,分两部分存,一部分 -L[j]*L[j]-L[j]/2,一部分存L[j],然后分别统计即可。
 上面就可以用三个树状数组完成统计,复杂度是O(RClognMin(R,C)),貌似只能这个复杂度了额...

      想到这里然后去看ydc君的题解...然后发现这样一句话:

     【千万别忘了乘以Down[i]啊啊啊否则会爆零啊】

      奉劝各位oier,晚上一定要睡好,不然脑袋容易抽....然后就是好不容易想出一个解法千万不要像咱这样的,B的忘记还要枚举下面的长度啊啊啊啊啊啊啊....(其实上面的长度也忘记枚举了,上面的推导式子这两个全忘了...= =)

      额..所以不推荐直接用上面的推导...不过思路就是这样的了吧...= =
      不过,其实就是在上面的式子推导再乘以这两个遗漏的即可。

      PS:这一题咱也不知道为什么写T了,然后改着改着不知道为什么A了.....
============================== 

program bzoj2727;
const modd=1000000009;
var c:array[0..2,0..2000001]of int64;
l,r,up,down:array[0..2000101]of int64;
x:array[0..2000100]of boolean;
n,m,t:longint;
ans:int64;
que:array[0..200001]of longint;
s:array[0..1,0..200001]of int64;

function cal(i,j:longint):longint;
begin
if (i<1)or(i>n) then exit(0);
if (j<1)or(j>m) then exit(0);
exit((i-1)*m+j);
end;

procedure insert(kth,x:longint;cc:int64);
begin
if x=0 then exit;
if cc=0 then exit;
while x<=m do
begin
c[kth][x]:=c[kth][x]+cc;
if c[kth][x]>modd then c[kth][x]:=c[kth][x]-modd;
x:=x+(x and (-x));
end;
end;

procedure setup(kth,x:longint);
begin
if x=0 then exit;
while x<=m do
begin
c[kth][x]:=0;
x:=x+(x and (-x));
end;
end;

function sum(kth,x:longint):int64;
var s:int64;
begin
s:=0;
while x>0 do
begin
s:=s+c[kth][x];
if s>modd then s:=s-modd;
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;

procedure init;
var i,j,k,u,v,w,ll,rr:longint;
tmp,tmp2,tmp3:int64;
begin
read(n,m);
read(t);
fillchar(x,sizeof(x),true);
for i:=1 to t do
begin
read(u,v);
x[cal(u,v)]:=false;
end;
fillchar(l,sizeof(l),0);
fillchar(r,sizeof(r),0);
fillchar(up,sizeof(up),0);
fillchar(down,sizeof(down),0);
for i:=1 to n do
for j:=1 to m do
begin
w:=cal(i,j);
if x[w] then l[w]:=l[cal(i,j-1)]+1
else l[w]:=0;
if x[w] then up[w]:=up[cal(i-1,j)]+1
else up[w]:=0;
end;
for i:=n downto 1 do
for j:=m downto 1 do
begin
w:=cal(i,j);
if x[w] then r[w]:=r[cal(i,j+1)]+1
else r[w]:=0;
if x[w] then down[w]:=down[cal(i+1,j)]+1
else down[w]:=0;
end;
for i:=1 to n do
for j:=1 to m do
begin
w:=cal(i,j);
l[w]:=min(l[w],r[w]);
dec(down[w]);
dec(up[w]);
dec(l[w]);
end;
ans:=0;
x[0]:=false;
fillchar(c,sizeof(c),0);
fillchar(s,sizeof(s),0);
for i:=1 to m do
begin
tmp:=i;
s[0][i]:=(tmp*(tmp-1))shr 1 mod modd;
s[1][i]:=(tmp*(tmp+1))shr 1 mod modd;
end;
for i:=2 to m-1 do
begin
ll:=0;rr:=0;
w:=cal(1,i);
for k:=2 to n do
begin
inc(w,m);
if (x[w])and(k<n) then
begin
if (l[w]>1)and(down[w]>0) then
begin
tmp:=s[0][l[w]]*(sum(0,m)-sum(0,l[w]));
tmp2:=sum(1,l[w]);
tmp3:=sum(2,l[w])*l[w];
ans:=ans+(tmp+tmp3-tmp2)*down[w];
if ans>modd then ans:=ans mod modd;
end;
u:=cal(k-1,i);
if up[u]<=0 then continue;
if l[u]<=0 then continue;
insert(0,l[u],up[u]);
tmp:=s[1][l[u]]*up[u] mod modd;
insert(1,l[u],tmp);
insert(2,l[u],up[u]*l[u]);
que[rr]:=l[u];
inc(rr);
end
else
begin
while ll<rr do
begin
setup(0,que[ll]);
setup(1,que[ll]);
setup(2,que[ll]);
inc(ll);
end;
end;
end;
end;
ans:=ans mod modd;
ans:=(ans+modd)mod modd;
write(ans);
end;

begin
init;
end.


  评论这张
 
阅读(34)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017