2009年08月31日 14:36 阅读(107) 评论(5) 分类：program 《program memorandum》

09.11.17

拓扑要判重边啊判重边。。。。

-------------------------------------------------------------------------

09.11.15

雅丽的神经病题目

var ans:int64;

     a,b:array[1..1000]of longint;

for i:=1 to n do ans:=ans+int64(a[i])*int64(b[i]);

-------------------------------------------------------------------------

bellman-ford

原来写法这么暴力

flag:=true;

while flag do

  begin

   flag:=false;

   for i:=1 to n do for j:=1 to m do

     begin

      if 可以更新then

        begin

         更新

         flag:=true;

        end;

     end;

  end;

-------------------------------------------------------------------------

09.11.2

wlf大牛说“最大值的最小值和最小值的最大值什么的一般都可以用二分搞”

OTZ第三次魔兽模拟赛400分的wlf神牛

-------------------------------------------------------------------------

09.10.22

最长不降子序列nlog(n)

wa了N次我太垃圾了

function k(x:longint):longint;
  var p,q,m:longint;
  begin
   p:=0;q:=n;
   while p
     begin
      m:=(p+q+1)shr 1;
      if b[ m ]­­<=x then p:=m
         else q:=m-1;
     end;
   b[p+1]:=x;
   exit(p);
  end;
 
procedure dp;
  var i:longint;
  begin
   b[0]:=0;
   fillchar(b,sizeof(b),$7f);
   f[1]:=1;b[1]:=a[1].y;
   for i:=2 to n do
     begin
      f[i]:=k(a[i].y)+1;
      if f[i]>ans then ans:=f[i];
     end;
  end;      

-------------------------------------------------------------------------

09.10.21

voj1617

队列dp优化

第一次写

jj的标程

贴着

   p:=1;q:=1;
   f[0]:=m;
   for i:=1 to n do
     begin
      while (p
      f[i]:=f[g[p]]+s[i]-s[g[p]]-i*100;
      while (pf[g[q]]-s[g[q]]) do dec(q);
      inc(q);
      g[q]:=i;  

    end;

-------------------------------------------------------------------------

09.10.21

voj1092

康拓不能理解中

先扔这里

逆康托
begin
 c[2]:=1;
 for i:=3 to n do c[i]:=c[i-1]*(i-1);
 for i:=1 to n do a[i]:=i;
 for i:=n downto 2 do
   begin
    k:=(m-1) div c[i]+1;
    m:=m-(k-1)*c[i];
    write(a[k],' ');
    for j:=k to i-1 do a[j]:=a[j+1];
   end;
 write(a[1]);
end.

康托

   hash:=0;
   for i:=1 to n-1 do
     begin
       t:=0;
       for j:=i+1 to n do if a[i]>a[j] then inc(t);
       hash:=hash*(n+1-i)+t;
     end;
   inc(hash);

-------------------------------------------------------------------------

09.10.10

糖果盒子

传说中的悬线O(nm)算法(说是nm其实常数不小- -)

抄的标程

l和r的转移哪里有点看不太明白

不知道为什么是用while而不用if

暂存在这里

求数据模拟

var i,j,max,n,m:longint;
    h,l,r:array[0..301]of longint;
    a,f:array[0..301,0..301]of longint;
   
begin
 fillchar(f,sizeof(f),0); readln(n,m); max:=0;
 for i:=1 to n do
   begin
    for j:=1 to m do read(a[i,j]);
    readln;
   end;
 for i:=1 to n do
  for j:=1 to m do f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1]+a[i,j];
 for i:=1 to n do
  begin
    for j:=1 to m do if a[i,j]=0 then h[j]:=0 else inc(h[j]);
    for j:=1 to m do l[j]:=j; for j:=1 to m do r[j]:=j;
    for j:=1 to m do
      if h[j]>0 then
        while (h[l[l[j]-1]]>=h[j])and(h[l[j]-1]>=h[j]) do
           l[j]:=l[l[j]-1];
    for j:=m downto 1 do
      if h[j]>0 then
        while (h[r[r[j]+1]]>=h[j])and(h[r[j]+1]>=h[j]) do
           r[j]:=r[r[j]+1];
    for j:=1 to m do
     if (f[i,r[j]]-f[i,l[j]-1]-f[i-h[j],r[j]]+f[i-h[j],l[j]-1])>max then
       max:=f[i,r[j]]-f[i,l[j]-1]-f[i-h[j],r[j]]+f[i-h[j],l[j]-1];
  end;
 writeln(max);
end.

wlf大牛给了我另外一个版本的悬线dp

悬线的求法不一样

贴在下面

    ml:=1;
    for j:=1 to m do
      if h[j]=0 then begin ml:=j+1; l[j]:=1; end
        else if l[j]    mr:=m;
    for j:=m downto 1 do
      if h[j]=0 then begin mr:=j-1; r[j]:=m; end
        else if r[j]>mr then r[j]:=mr;     

ml表示第i行离(i,j)最近的左边的障碍点+1

mr表示第i行离(i,j)最近的右边的障碍点-1

初始化：for i:=1 to m do begin l[i]:=1; r[i]:=m;end;

后者效率更高

因为在更新l和r的时候用到了dp

而第一种则是朴素的悬线求法，冗余操作更多，不过更容易理解

经测试符合推测

上图

[一张图片，用时1.03秒]

此为wlf大牛的写法

[一张图片，用时1.18秒]
此为第一种写法

-------------------------------------------------------------------------

一些常见的二进制位的变换操作。
    功能              |           示例            |    位运算
----------------------+---------------------------+--------------------
去掉最后一位          | (101101->10110)           | x shr 1
在最后加一个0         | (101101->1011010)         | x shl 1
在最后加一个1         | (101101->1011011)         | x shl 1+1
把最后一位变成1       | (101100->101101)          | x or 1
把最后一位变成0       | (101101->101100)          | x or 1-1
最后一位取反          | (101101->101100)          | x xor 1
把右数第k位变成1      | (101001->101101,k=3)      | x or (1 shl (k-1))
把右数第k位变成0      | (101101->101001,k=3)      | x and not (1 shl (k-1))
右数第k位取反         | (101001->101101,k=3)      | x xor (1 shl (k-1))
取末三位              | (1101101->101)            | x and 7
取末k位               | (1101101->1101,k=5)       | x and (1 shl k-1)
取右数第k位           | (1101101->1,k=4)          | x shr (k-1) and 1
把末k位变成1          | (101001->101111,k=4)      | x or (1 shl k-1)
末k位取反             | (101001->100110,k=4)      | x xor (1 shl k-1)
把右边连续的1变成0    | (100101111->100100000)    | x and (x+1)
把右起第一个0变成1    | (100101111->100111111)    | x or (x+1)
把右边连续的0变成1    | (11011000->11011111)      | x or (x-1)
取右边连续的1         | (100101111->1111)         | (x xor (x+1)) shr 1
去掉右起第一个1的左边 | (100101000->1000)         | x and (x xor (x-1))

看着非常晕啊慢慢理解= =。

-------------------------------------------------------------------------

Matrix67大牛blog摘

    记得有一年我搞了一次NOIp普及组的模拟赛，里面有一道题是这样的：给你一个带实数边权的无向图，所有权值都大于1，然后叫你求一条从A到B的权值乘积最小的路径。只要了解Dijkstra算法原理的人都能想明白，该算法同样适用于权值乘积最小问题。但不出我所料，还是有很多人问我，为什么Dijkstra算法在这里仍然可以用？我的回答很简单。你根本不需要明白Dijkstra算法的原理你也能想到，这道题目依然可以用Dijkstra算法。只需要把所有权值全部取对数，权值乘积的问题立即转变为了权值和的问题；求出了最短路之后，再把所得结果当作指数还原回去即可。

真ws取对数= =。

-------------------------------------------------------------------------

我终于弄懂kmp（看毛片）算法啦

继续膜拜matrix67大牛

今天在大牛blog看了好久被巨大的震慑到了

原来一个geek可以又牛逼又骚到这种境界

太吊啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦

如果我是个MM肯定嫁给matrix67牛   >______________________<

(我依然是一个很纯种的lolicon没有一点gay倾向)

原文地址：http://www.matrix67.com/blog/archives/115

procedure creatp;
  var i,j:longint;
  begin
   p[1]:=0;
   j:=0;
   for i:=2 to m do
     begin
      while (j>0)and(b[j+1]<>b[i]) do j:=p[j];
      if b[j+1]=b[i] then inc(j);
      p[i]:=j;
     end;
  end;
 
procedure kmp;
  var i,j:longint;
  begin
   j:=0;
   for i:=1 to n do
     begin
      while (j>0)and(b[j+1]<>a[i]) do j:=p[j];
      if b[j+1]=a[i] then inc(j);
      if j=m then
        begin
         writeln('We find a match point:',i-m+1);
         j:=p[j];
        end;
     end;
  end;   

-------------------------------------------------------------------------

快排

把自己原来背的改良了下= =。

效率果然提高不少

procedure kp(p,q:longint);
  var i,j,x,z:longint;
  begin
   i:=p;j:=q;
   x:=a[(i+j) div 2];
   while i<=j do
     begin
      while (a[i]
      while (x
      if i<=j then
        begin
         z:=a[i];a[i]:=a[j];a[j]:=z;
         inc(i);dec(j);
        end;
     end;
   if p
   if i
  end;

  

-------------------------------------------------------------------------

以下摘自matrix67大牛blog

经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31    根据前面的一些思路，现在我们需要构造一个2 x 2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多迭代一次。那么，我们把这个2 x 2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：
    

经典题目7 VOJ1067
    我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
    
    利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况

自己拍的代码

function mul(f,g:matrix;a,b,c:integer):matrix;  //矩阵乘法
  var i,j,k:integer;
  begin
   fillchar(mul,sizeof(mul),0);
   for i:=1 to a do
     for k:=1 to c do
       for j:=1 to b do
         begin
          inc(mul[i,k],f[i,j]*g[j,k]);
         end;
  end;

function work(i:longint):matrix;
  var temp:maxtrix;
  begin
   if i=1 then exit(A);    //A是单位矩阵
   temp:=work(i div 2);
   work:=mul(temp,temp,m,m,m);
   if i mod 2=1 then work:=mul(work,A,m,m,m);     

end;

procedure creatA;  //创建系数矩阵
  var i:integer;
  begin
    for i:=1 to m-1 do a[i,i+1]:=1;
    for i:=1 to m do a[m,i]:=coe[i];   //coe为系数
  end;

干太虚了递归快速幂会202 堆栈溢出

补个非递归的。。。

个人感觉写法很诡异= =。。

function g(x:longint):arr;
  var temp:arr;
  begin
   if x and 1=1 then temp:=a
                else temp:=f; // f是单位矩阵（就是斜对角线一排1的）
   repeat
    x:=x shr 1;
    a:=mul(a,a);
    if x and 1=1 then temp:=mul(temp,a);
   until x<=1;
   g:=temp;
  end; 

09.10.08

今天rp爆发想通了

模拟一个例子
求2的11次方
x   a    temp
11  2     2
5   4     8
2   16    8
1  256   2048

是不是感觉很诡异
把a和temp改成2的次幕

x   a   temp
11  1     1
5   2     3
2   4     3
1   8    11

temp确实被还原成11了
好像还是有一点诡异

下面把以上的数字全部改为二进制

  x     a     temp
1011    1       1
101    10      11
10    100      11
1    1000    1011

可以看出a就代表当前所操作的位

对照一下程序
每次x and 1（即x mod 2）就是取出当前x二进制的最后一位的值（即当前正在操作的位上的值）

temp:=a*temp就代表把这位上的值加上去（因为是二进制所以就是当前的a）

其实那句判断可以写成这样 temp:=temp*a*(x and 1);
第一个if也可以改写掉

其实以上过程有点像进制转换= =。

考虑下面这段程序

begin
 x:=3195;a:=1;temp:=x mod 10；
 repeat
  x:=x div 10;
  a:=a*10;
  temp:=temp+a*(x mod 10);
 until x<=1;
end;

以下是模拟过程
  x     a     temp
3095    1       5
309    10      95
30    100      95
3    1000    3095

对比一下上面的二进制模拟后道理应该就很显然了

我是大弱 

-------------------------------------------------------------------------

二分

init(p,q);

// if p

// if q>max then q:=max;

while p

  begin

    m:=(p+q) div 2;                   //m:=(p+q+1) div 2;

    if pd(m) then p:=m+1         //p:=m;

              else q:=m;                 //q:=m-1;

  end;

 -------------------------------------------------------------------------

实数我[哔~~~]

一个实数比如1.78的数读进去后可能会变成1.7799999999999999999999999

如果你read(z); 然后a:=trunc(z*100)会变成1.77

非常恶劣啊。。。。。。。。

害我某题费解半天

记住wlf大牛的话“实数都给它加一个0.000001”

 但是有时候这样也会错= = 我日

-------------------------------------------------------------------------

  

搭建双塔

f[i,j] 表示用前i个搭成高度差为j的双塔中高塔的高度

-------------------------------------------------------------------------

Kruskal

a[i]已按a[i].c排序

procedure kruskal;
  var i,fa,fb,sum:longint;
  begin
   sum:=0;ans:=0;
   for i:=1 to m do
     begin
      fa:=father(a[i].x); //并查集
      fb:=father(a[i].y);
      if fa<>fb then
        begin
         f[fb]:=fa;
         inc(sum);
         inc(ans,a[i].c);
        end;
      if sum=n-1 then break;
     end;
  end;     

-------------------------------------------------------------------------

并查集

function father(i:integer):integer;
  begin
   if f[i]=i then exit(i);
   f[i]:=father(f[i]);
   exit(f[i]);
  end;

f[fa]:=fb;

-------------------------------------------------------------------------

字符串hash

BKDRhash

function BKDRHash(s1:string):qword;
   var i:integer;
       seed,hash:qword;
   

begin
 seed:=131; // 31 131 1313 13131 131313 etc..
 hash:=0;
 for i:=1 to length(s1) do
    hash:=(hash*seed+ord(s1[i])) and $FFFFFFFF;
 BKDRHash:=hash and $7FFFFFFF;
end;

ELFhash

function ELFhash(s:string):longint;
  var i,g:longint;
  begin
   ELFhash:=0;
   for i:=1 to length(s) do
     begin
      ELFhash:=(ELFhash shl 4)+ord(s[i]);
      g:=ELFhash and($f0000000);
      if g>0 then ELFhash:=ELFhash xor (g shr 24);
      ELFhash:=ELFhash and (not g);
     end;

  end;

-------------------------------------------------------------------------

 f[1]:=1;
 for i:=2 to n do f[i]:=(4*i-2)*f[i-1]div (i+1);  

catalan数递推式

通项公式 f[n]=C(2n,n)/(n+1)

推杨辉3角显然没有递推式子快

但是递推可能算术上溢出

-------------------------------------------------------------------------

function equal:(p,q:real):boolean
begin
 if abs(p-q)<精度 then exit(true)
                             else exit(false);
end.

-------------------------------------------------------------------------

小堆
procedure heap(i,n:integer);
  var z,j:integer;
  begin
   z:=a[i];
   while i*2<=n do
    begin
     j:=i*2;
     if (ja[j+1]) then inc(j);
     if z>a[j] then
         begin
          a[i]:=a[j];
          i:=j;
         end
     else break;
    end;
   a[i]:=z;
  end;

向堆中插入元素（插入大堆）
procedure inst(i:integer);
  var z:integer;
  begin
   z:=a[i];
   while (i>1)and(a[i shr 1]
     begin
      a[i]:=a[i shr 1];
      i:=i shr 1;
     end;
   a[i]:=z;
  end;