Author Archives: nike0good

POJ 2084 (Catalan数)

Posted on by

卡特兰数三大公式

C(n)=C(n-1)*(4*n-2)/(n+1)

C(n)=C(2n-1,n+1)-C(2n-1,n-1)

C(n)=C(2n,n)/(n+1)

Program p2084;
Const
   F=10000;
Type
   arr=record
       a:array[1..10000] of longint;
       len:longint;
       end;
var
   n,i,j:longint;
   c:array[1..101] of arr;
Procedure Mulpily(a:arr;b:longint;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
   begin
      inc(c.a[i],a.a[i]*b);
      inc(c.a[i+1],c.a[i] div F);
      c.a[i]:=c.a[i] mod F;
   end;
   c.len:=a.len;
   while c.a[c.len+1]>0 do
   begin
      inc(c.len);
      inc(c.a[c.len+1],c.a[c.len] div F);
      c.a[c.len]:=c.a[c.len] mod F;
   end;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);

end;
Procedure Divede(a:arr;b:longint;var c:arr);
var
   i,j,d:longint;
begin
   fillchar(c,sizeof(c),0);
   d:=0;
   for i:=a.len downto 1 do
   begin
      d:=d*F+a.a[i];
      c.a[i]:=d div b;
      d:=d mod b;
   end;
   c.len:=a.len;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);

end;
Procedure prin(a:arr);
var
   i,j:longint;
begin
   write(a.a[a.len]);
   for i:=a.len-1 downto 1 do
   begin
      if a.a[i]<1000 then write('0');
      if a.a[i]<100 then write('0');
      if a.a[i]<10 then write('0');
      write(a.a[i]);
   end;
   writeln;
end;
begin
   fillchar(c,sizeof(c),0);
   c[1].len:=1;
   c[1].a[1]:=1;
   c[2].len:=1;
   c[2].a[1]:=1;
   for i:=3 to 101 do
   begin
      Mulpily(c[i-1],4*i-2,c[i]);
      divede(c[i],i+1,c[i]);
   end;
   read(n);
   while (n<>-1) do
   begin
      prin(c[n+1]);
      read(n);
   end;

end.

POJ 1001 (坑爹的小数高精度乘法)

Posted on by

小数高精度乘法

program P1001;
Type
    arr=record
        a:array[1..10000] of longint;
        len:longint;
        xs:longint;
        end;
Var
    s:ansistring;
    n,i,j,k,len:longint;
    r:arr;
Procedure relax(var c:arr);
var
   i,j:longint;
begin
   while (c.a[c.len]=0) and (c.len>1) do dec(c.len);
   if (c.len=1) and (c.a[1]=0) then begin c.xs:=0; exit; end;
   i:=1;
   while (c.a[i]=0) do inc(i);
   dec(i);
   if (i>0) then
   begin
      if (c.xs>=i) then dec(c.xs,i)
      else
      begin
         i:=c.xs;
         c.xs:=0;
      end;
      for j:=i+1 to c.len do c.a[j-i]:=c.a[j];
      dec(c.len,i);
   end;
end;
procedure prin(c:arr);
var
   i:longint;
begin
   relax(c);
   if (c.xs=0) then
   begin
      for i:=c.len downto 1 do write(c.a[i]);
      writeln;
      exit;
   end;
   if (c.xs<=c.len) then
   begin
      for i:=c.len downto c.xs+1 do write(c.a[i]);
      write('.');
      for i:=c.xs downto 1 do write(c.a[i]);
      writeln;
      exit;
   end;
   write('.');
   for i:=1 to c.xs-c.len do write('0');
   for i:=c.len downto 1 do write(c.a[i]);
   writeln;
end;
Procedure cheng(a:arr;b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
      for j:=1 to b.len do
      begin
         inc(c.a[i+j-1],a.a[i]*b.a[j]);
         inc(c.a[i+j],c.a[i+j-1] div 10);
         c.a[i+j-1]:=c.a[i+j-1] mod 10;
      end;
   c.len:=a.len+b.len+1;
   c.xs:=a.xs+b.xs;

   relax(c);

end;
procedure jie(a:arr;b:longint;var c:arr);
begin
   if (b=1) then c:=a
   else if (b mod 2=0) then
   begin
      jie(a,b div 2,c);
      cheng(c,c,c);
   end
   else begin
      jie(a,b div 2,c);
      cheng(c,c,c);
      cheng(c,a,c);
   end;

end;
Begin
   while (not(eof)) do
   begin
      readln(s);
      len:=length(s);
      i:=pos(' ',s);
      j:=pos('.',s);
      if j=0 then
      begin
         r.xs:=0;
         r.len:=i-1;
         for k:=1 to r.len do r.a[r.len-k+1]:=ord(s[k])-48;
      end
      else begin
      r.xs:=i-j-1;
      r.len:=i-2;
      for k:=1 to j-1 do r.a[r.len-k+1]:=ord(s[k])-48;
      for k:=j+1 to i-1 do r.a[r.len-k+2]:=ord(s[k])-48;
      end;
      relax(r);
      i:=len;
      while (s[i]<>' ') do dec(i);
      n:=0;
      for k:=i+1 to len do n:=n*10+ord(s[k])-48;
      jie(r,n,r);
      prin(r);
  end;
end.

二叉查找树

Posted on by

二叉查找树是一种支持查找，删除，排序的数

在排序上可以说是动态 的， 即随时告诉我们排序（中序遍历）

在二元排序树b中查找x的过程为：

  1. 若b是空树，则搜索失败，否则：
  2. 若x等于b的根节点的数据域之值，则查找成功；否则：
  3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
  4. 查找右子树。

插入则是一直找

删除分情况：
A：无子树，直接删
B：有一个子树，直接将其子树代替删除点
C：有两个子树
1.先找左子树的最大值，向右递归直至无右子树的点最大

q=p;

    s=p->lchild;
while(s->rchild){
      q=s;
      s=s->rchild;
}

此时p为删点地址，q为最右子父，s为最右子

 p->data = s->data;

直接搬移本身的值，不必删地址，这样不需要维护关系

问题转化为删无右子树的s

 if(q!=p)
      q->rchild = s->lchild; //维护s，把s跳过     
else
      q->lchild = s->lchild; //还是维护被删代替p（该子树的根）的s   此处s为q的左子树根 故特判
delete s;
}

自此树便建立了

ELF hash

Posted on by

字符串Hash 模板代码

unsigned long
 elf_hash(const unsigned char *name)
  {
      unsigned long       h = 0, g;

      while (*name) {
          h = (h << 4) + *name++;
          if (g = h & 0xf0000000)
              h ^= g >> 24;
          h &= ~g;
      }
      return h;
  }

线段树-模板

Posted on by

PushUp（root） 维护

          sum[root]=sum[root/2]+sum[root/2+1] 

Build     建树 （当前区间，序号（当前区间的root））

         维护目前结点

l=r   return

    更新左右子树

Update   更新子节点 （当前区间，所求区间，Root）

l=r    更新   return

更新结点在左子树    更新左子树

否则更新右子树

PushUp 当前结点

Query 区间求和 （当前区间，所求区间，Root）

包含   直接返回当前值

否则考察左右结点是否包含   求和

       

C++ 注意事项

Posted on by

1：名字空间 --》STL无法使用

2.define 必须+10     极限点  时间小wa

3.for后面不能加；，否则会跳过

4。for的3个i一定要统一

5. ==和=

6.int64 --》long long 占位符：%lld

7.不能用相同的变量 -》别 局部与总 类型不同 

8.abs <cmath> 中间的类型为float