Category Archives: DefaultCategory

POJ 2479(2段连续子序列和）

Posted on by

题目要求两段子序列和

分段就行 O(n)

话说这回数组又开小了，居然提示Runtime Error

Program P2479;
var
   t,n,i,j,m,m2,p:longint;
   a,b,c:array[0..50000] of longint;
begin
   read(t);
   a[0]:=-100001;
   while (t>0) do
   begin
      read(n);
      j:=0;
      m:=0;
      for i:=1 to n do
      begin
         read(a[i]);
         if a[i]<0 then inc(j);
         if a[i]>a[m] then m:=i;
      end;


      if j>n-2 then
      begin
         p:=a[m];
         m2:=0;
         for i:=1 to n do if (i<>m) and (a[m2]<a[i]) then m2:=i;
         inc(p,a[m2]);
         writeln(p);
      end
      else
      begin
         p:=0;
         m:=-100001;
         for i:=1 to n do
         begin
            inc(p,a[i]);
            if (p<0) then p:=0;
            if m<p then m:=p;
            b[i]:=m;
         end;
         p:=0;
         m:=-100001;
         for i:=n downto 1 do
         begin
            inc(p,a[i]);
            if (p<0) then p:=0;
            if m<p then m:=p;
            c[i]:=m;
         end;
         m:=0;
         for i:=1 to n-1 do
            if m<b[i]+c[i+1] then m:=b[i]+c[i+1];
         writeln(m);
      end;
      dec(t);
   end;
end.

POJ 2152(树形DP)

Posted on by

这题告诉我一个道理：数组开得太小会出现Time Limit Exceeded

言归正传：这题的DP方程是f[x,i]:=w[i]+∑(best[y],f[y,i]-w[i])   //f[x,i]指 x 的供应站为 i 时，x子树全取的最小代价

best[y]表示min(best[y,i]) 预处理

y为x的儿子

如果x的子树有重叠的供应站，那么这个供应站只能是x的供应站i

多叉树可以用边表存的（难道树形DP=DFS？）

《一张一弛,解题之道——“约制、放宽”方法在解题中的应用》

http://www.doc88.com/p-670874250550.html

Program p2152;
var
   t,n,i,j,u,v,w2,tot,root,father:longint;
   d,w,best,dis:array[1..2000] of longint;
   head,tail,edge,we:array[1..2000] of longint;
   f:array[1..1000,1..1000] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure addedge(u,v,w:longint);
var
   i,j:longint;
begin
   inc(tot);
   we[tot]:=w;
   edge[tot]:=v;
   tail[tot]:=head[u];
   head[u]:=tot;
end;
procedure calcdis(x:longint);
var
   i,p:longint;
begin
   p:=head[x];
   while (p<>0) do
   begin
      if (dis[edge[p]]=-1) then
      begin
         dis[edge[p]]:=dis[x]+we[p];
         calcdis(edge[p]);
      end;
      p:=tail[p];
   end;
end;
procedure dfs(x,fa:longint);
var
   i,j,p:longint;
begin
   best[x]:=maxlongint;
   p:=head[x];
   while (p<>0) do
   begin
      if (edge[p]<>fa) then dfs(edge[p],x);
      p:=tail[p];
   end;
   for i:=1 to n do dis[i]:=-1;
   dis[x]:=0;

   calcdis(x);


   for i:=1 to n do
   begin
      if (dis[i]>d[x]) then f[x,i]:=maxlongint
      else
      begin
         f[x,i]:=w[i];
         p:=head[x];
         while (p<>0) do
         begin
            if (edge[p]<>fa) then inc(f[x,i],min(best[edge[p]],f[edge[p],i]-w[i]));
            p:=tail[p];
         end;
         best[x]:=min(best[x],f[x,i]);




      end;


   end;
end;
begin
   read(t);
   while t>0 do
   begin
      tot:=0;
      fillchar(head,sizeof(head),0);
      fillchar(tail,sizeof(tail),0);

      read(n);
      for i:=1 to n do read(w[i]);
      for i:=1 to n do read(d[i]);
      for i:=1 to n-1 do begin read(u,v,w2); addedge(u,v,w2); addedge(v,u,w2); end;

      root:=1;
      dfs(1,-1);
      writeln(best[root]);

      dec(t);
   end;
end.

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