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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1063】【Noi2008】【道路设计】  

2014-03-21 14:07:21|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    鉴于bzoj1062实在太神了,想了一个小时发现自己的前提想错了233,然后看了题解觉得各种神奇,但是觉得做法还是比较模模糊糊的,所以待整理一下再动键盘,先看了这道题。

    很显然这是一棵树或者不连通...实际上这题就是将树划分成很多条链(多少条没有定下来,随便),然后要求到达根节点经过链数最多的那个节点经过的链数最小,求这个最小值以及方案个数。

    实际上咱们只关心 最大的经过的链,咱们可以试试用这个来做DP?显然状态数有点小多....O(n^2)的。得O(nlogn)才可以做...。然后突然发现自己233了,首先可以知道树链剖分可以得到答案上界为O(logn)的,所以Dp的话一个节点只需要(logn)的枚举,然后复杂度貌似的确是O(nlogn)的?那么来思考如何DP。

    然后发现有几个不和谐的地方,一个是实际上子树可以连两条链或者一条链,这个在dp里面没有表示出来,所以咱们再增加一维状态 f[i][j][2],其中0表示的是 以i为根的子树中,其中某个节点到达根所需要经过的链数最大为j,且根只接一棵子树的方案数,而1就是根接两棵子树的方案数。那么最后的答案就是f[i][j][0] 或者 f[i][j][1]中第一个方案数不为0的 j ,然后方案数照着输出即可。接下来考虑转移。

    假设咱们DFS出了某个儿子节点的f[][][],那么要用它更新父亲节点,首先更新父亲 的 f[][][1],这个首先枚举该儿子的j ,然后先用这个j来更新父亲j+1以上的方案(相乘),然后对于f[][j][1],所有小于等于j的f[][j][0]*儿子的f[][j][0]得到,对于以下的显然跟这个j无关,无视了。然后 f[][][0],实际上就是枚举j,然后对于j-1及其以下的所有方案,将那个子树断掉,然后将这棵子树接上去,所以就是所有的和乘f[i'][j][0]即可。复杂度O(nlog^2n),非常满意=w=。

    然后去看题解检查自己的想法,发现的确是树Dp,但是设f[i][j][2]是不对的,还有可能有不接儿子这个状态,应该是f[i][j][3],这个没思考到果然蒟蒻= =(不过貌似有人是咱这样的也可以?)。这个只要把上面的转移改一下就可以了。
    最后的方程可以戳这个 方程君

    最后自己整理一下自己的方程。
    首先DFS好某棵子树之后看如何更新,先来f[][][2],这个用f[][][1]和 子树的f[][][1]或者f[][][0]来更新,咱们枚举这棵子树的j,然后把这种情况的子树接上去,然后显然它只能更新j及j以上的,就这样更新即可,然后再来f[][][1],这个用子树的f[][][1]或者f[][][0]来更新,同0的,然后f[][][0],这个枚举j,用f[][][0]和子树的f[][][1]或f[][][0]或f[][][2],然后就没了233333。

     对了咩还有考虑边界情况,对于每一个,咱们都需要保留f[][j][0]=1。(0<=j<=11)

     另外这题有一个小坑的地方。如果乃是最后判断方案加起来是否为0来判断的话,会WA,因为直接取模可能f为0,然后会使这个被跳过,所以取模得特判一下,如果这个数模=0且这个数不为0,就取那个模数。
==================================

program bzoj1062;
const maxn=100100;
type edge=record
     v,pre:longint;
     end;

var e:array[0..maxn*2]of edge;
    last,fa:array[0..maxn]of longint;
    f:array[0..maxn,0..11,0..2]of int64;
    n,m,tot,modd:longint;

procedure addedge(u,v:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].pre:=last[u];
  last[u]:=tot;
  inc(tot);e[tot].v:=u;e[tot].pre:=last[v];
  last[v]:=tot;
end;

function get(p:int64):int64;
begin
  if p mod modd<>0 then exit(p mod modd);
  if p=0 then exit(0) else exit(modd);
end;

procedure dfs(p:longint);
var tmp,j:longint;
    f1,f2:int64;
begin
  tmp:=last[p];
  while tmp<>0 do
   begin
     if (fa[p]<>e[tmp].v)then
      begin
        fa[e[tmp].v]:=p;
        dfs(e[tmp].v);
        for j:=1 to 11 do
         begin
           f1:=f[e[tmp].v][j][0]+f[e[tmp].v][j][1]; 
           if j=1 then f2:=0 else
           f2:=f[e[tmp].v][j-1][0]+f[e[tmp].v][j-1][1]
           +f[e[tmp].v][j-1][2];
           f[p][j][2]:=get(f[p][j][2]*f2+f[p][j][1]*f1);
           f[p][j][1]:=get(f[p][j][1]*f2+f[p][j][0]*f1);
           f[p][j][0]:=get(f[p][j][0]*f2);
         end;
      end;
     tmp:=e[tmp].pre;
   end;
end;

procedure init;
var i,j,u,v:longint;
begin
  read(n,m,modd);
  if n<>m+1 then
   begin
     writeln(-1);
     write(-1);
     exit;
   end;
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to m do
   begin
     read(u,v);
     addedge(u,v);
   end;
  fillchar(f,sizeof(f),0);
  fillchar(fa,sizeof(fa),0);
  for i:=1 to n do
   for j:=1 to 11 do
    f[i][j][0]:=1;
  dfs(1);
  for i:=1 to 11 do
   if f[1][i][0]+f[1][i][1] +f[1][i][2]<>0 then
    begin
      writeln(i-1);
      write((f[1][i][0]+f[1][i][1]+f[1][i][2])mod modd);
      exit;
    end;
  writeln(-1);
  write(-1);
end;

begin
  init;
end.



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

历史上的今天

评论

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

页脚

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