bzoj2165: 大楼（矩阵快速幂）

//==========================

蒟蒻Macaulish：http://www.cnblogs.com/Macaulish/ 转载要声明！

//==========================

事情是这样的。太久没切矩阵找了两道题爽一爽。然后泰林大神就满脸堆笑地说大神来坐坐这道题吧！

然后我就来看这题。然后觉得这题没多难啊，直接用类似最短路的方法，然后只要把图存成矩阵就可以矩阵搞一搞啊。

然后愉快的码好，交上去，wa

傻了。对着代码看了很久还是不行。决定写对拍。然后泰林大神说黄学长有写，这样好啊，就直接拿黄学长的来对拍。

小数据似乎没有问题。大数据似乎也没有问题啊。然后拍了很久才发现自己数据造的不行，答案都小于maxlongint（教训1）

然后就造了答案会超maxlongint的数据，结果果然错了！

然后就发现没有可能错啊，该int64的地方都有啊。

找了很久才发现，问题在于1<<i上，然后我就愉快的1<<in64（i），这下没错了吧，显然还是错&……大神们围过来说，应该写成这样int64（1）<<i（教训2）。擦我当时有脑子么？

然后一交tle……

然后就走上了调常数的不归路。

然后不会调常数发现也是徒劳。期间试着改了几次都没有用。

然后勾搭到了初三神牛dwjshift ！！！！！

大神和我说了很久，提出了各种改进方法，并且在所有方法还是t了之后还友情提供了代码

然后还是t了。然后就跑去睡觉了。

晚上看着到了12点，是时候调常数了（我是不是很好人，晚上没人提交这样卡测评也不会掉rp）

然后打开程序，然后发现下午脑袋吃屎了……倍增找到第一个>=m后我竟然只是跳出了找的那个for（教训3）！然后程序继续跑倍增……

然后就用了大神说的几个方法

改变矩乘的for循环

运算符重载传数组可能慢在程序里面写三个for

然后可以等到这个数组都处理完再去处理那些≥m的值变为m

矩阵初始是最后一个倍增矩阵中没有超过m的，记录一下。

然后提交

然后速度好快啊（虽然还是被c++碾压一脸）

然后终于过了这道常数题（p也是可以调常数的（雾））！）

恩，血泪史

type

  arr=array[..,..]of int64;

var

  map:array[..]of arr;

  f:array[..]of arr;

  pow:array[..]of int64;

  t,n,i:longint;

  m:int64;

procedure into;

var

  i,j,k,trsum,now,tot,ii,jj,kk:longint;

  big,ans:int64;

  flag:boolean;

begin

  readln(n,m);

  for i:= to n do

    for j:= to n do

      read(map[,i,j]);

  trsum:=trunc(ln(m)/ln())+;

  tot:=trsum;

  for i:= to trsum do begin

    for ii:= to n do begin

      for jj:= to n do map[i,ii,jj]:=;

      for kk:= to n do

        if map[i-,ii,kk]<> then

          for jj:= to n do

            if (map[i-,kk,jj]<>) and (map[i,ii,jj]<map[i-,ii,kk]+map[i-,kk,jj]) then

              map[i,ii,jj]:=map[i-,ii,kk]+map[i-,kk,jj];

    end;

    //map[i]:=map[i-]*map[i-];

    flag:=true;

    for j:= to n do

      if map[i,,j]>=m then begin

        tot:=i;

        flag:=false;

        break;

      end;

    if not flag then break;

    for ii:= to n do

      for jj:= to n do

        if map[i,jj,kk]>m then map[i,jj,kk]:=m;

  end;

  now:=;

  f[now]:=map[tot-];

  ans:=pow[tot-];

  for i:=tot- downto  do begin

    for ii:= to n do begin

      for jj:= to n do f[-now,ii,jj]:=;

      for kk:= to n do

        if f[now,ii,kk]<> then

          for jj:= to n do

            if (map[i,kk,jj]<>) and (f[-now,ii,jj]<f[now,ii,kk]+map[i,kk,jj]) then

              f[-now,ii,jj]:=f[now,ii,kk]+map[i,kk,jj];

    end;

    big:=;

    for j:= to n do

      if big<f[-now,,j] then big:=f[-now,,j];

    if big<m then begin

      ans:=ans+pow[i];

      now:=-now;

      for ii:= to n do

        for jj:= to n do

          if f[now,ii,jj]>m then f[now,ii,jj]:=m;

    end;

  end;

  writeln(ans+);

end;

begin

  readln(t);

  pow[]:=;

  for i:= to  do

    pow[i]:=pow[i-]<<;

  while t> do begin

    into;

    dec(t);

  end;

end.

巴特西

bzoj2165: 大楼（矩阵快速幂）

最新文章

热门文章

巴特西

bzoj2165: 大楼 （矩阵快速幂）

最新文章

热门文章

bzoj2165: 大楼（矩阵快速幂）