noip所有算法详解（非常全面）

本人精心整理自互联网，解压后约150MB,倍增、博弈、递归、递推、贪心、图论、动归、数论、搜索、数据结构(各种树形)、位运算、随机化、分治、字符串、排序、几何 当然noi的部分高级算法并未涉及，但针对noip是相当全面的！！

#include 
#include 
#define infile “dquery.in“
#define outfile “dquery.out“
#define maxn 41000
#define maxlogn 20

struct anedge{
              long xydist;
             }e[maxn+1];

struct edge2{
             long nodedist;
            }*g[maxn+1];

struct qqnode{
              long numnow;
             }zhan[maxn+1];

long degree[maxn+1]distfromroot[maxn+1]level[maxn+1]r[maxn+1]
     width[maxn+1]done[maxn+1]xl[maxn*2+10]df[maxn*2+10][maxlogn+1]
     nowtopnmnodexnodey;

FILE *fin=fopen（infile“r“）
     *fout=fopen（outfile“w“）;

void calc_width（）
{
 long inodeheadtail;
 for （i=1; i<=n; i++）
  done[i]=0;
 head=0;
 tail=1;
 width[1]=1;
 done[1]=1;
 distfromroot[1]=0;
 level[1]=1;
 while （head  {
   head++;
   node=width[head];
   for （i=1; i<=degree[node]; i++）
    if （done[g[node][i].node]==0）
     {
      tail++;
      width[tail]=g[node][i].node;
      done[g[node][i].node]=1;
      distfromroot[width[tail]]=distfromroot[node]+g[node][i].dist;
      level[width[tail]]=level[node]+1;
     }
  }
}

void dfs（）
{
 long itop;
 top=1;
 zhan[top].num=1;
 zhan[top].now=1;
 done[1]=1;
 while （top>0）
  {
   nowtop++;
   xl[nowtop]=zhan[top].num;
   while （（zhan[top].now<=degree[zhan[top].num]）&&（done[g[zhan[top].num][zhan[top].now].node]==1））
    zhan[top].now++;
   if （zhan[top].now<=degree[zhan[top].num]）
    {
     done[g[zhan[top].num][zhan[top].now].node]=1;
     zhan[top+1].num=g[zhan[top].num][zhan[top].now].node;
     zhan[top+1].now=1;
     zhan[top].now++;
     top++;
    }
   while （（top>=1）&&（zhan[top].now>degree[zhan[top].num]））
    top--;
 }
}

long min（long along b）
{
 if （level[xl[a]]  return（a）;
  else return（b）;
}

void calc_df（）
{
 long iji2step;
 for （i=1; i<=nowtop; i++）
  df[i][0]=i;
 j=0;
 step=1;
 while （step<=n）
  {
   j++;
   step*=2;
   for （i=1; i<=nowtop; i++）
    {
     i2=i+step/2; //important!!!
     if （i2>nowtop）
      df[i][j]=df[i][j-1];
      else df[i][j]=min（df[i][j-1]df[i2][j-1]）;
    }
  }
}

void init（）
{
 long ixydist;
 char c;
 fscanf（fin“%ld%ld“&n&m）;
 for （i=1; i<=n; i++）
  degree[i]=0;
 for （i=1; i<=m; i++）
  {
   fscanf（fin“%ld%ld%ld“&e[i].x&e[i].y&e[i].dist）;
   while （1）
    {
     fscanf（fin“%c“&c）;
     if （c!=‘ ‘）
      break;
    }
   degree[e[i].x]++;
   degree[e[i].y]++;
  }
 for （i=1; i<=n; i++）
  {
   g[i]=new （struct edge2 [degree[i]+2]）;
   g[i][0].node=0;
  }

 for （i=1; i<=m; i++）
  {
   x=e[i].x;
   y=e[i].y;
   dist=e[i].dist;
   g[x][0].node++;
   g[x][g[x][0].node].node=y;
   g[x][g[x][0].node].dist=dist;
   g[y][0].node++;
   g[y][g[y][0].node].node=x;
   g[y][g[y][0].node].dist=dist;
  }

 calc_width（）;

 nowtop=0;
 for （i=1; i<=n; i++）
  done[i]=0;
 dfs（）;
 for （i=1; i<=n; i++）
  r[i]=0;
 for （i=1; i<=nowtop; i++）
  if （r[xl[i]]==0）
   r[xl[i]]=i;

 calc_

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2002-01-08 07:50  文档\
     文件      275314  2010-10-04 00:00  文档\NOIP实用算法.pdf
     目录           0  2002-01-08 07:50  文档\位运算\
     目录           0  2002-01-08 07:50  文档\位运算\位运算简介及实用技巧\
     文件       47104  2008-03-02 23:39  文档\位运算\位运算简介及实用技巧\基础篇.doc
     文件       77824  2008-01-27 18:47  文档\位运算\位运算简介及实用技巧\实战篇.doc
     文件       60416  2008-01-27 18:46  文档\位运算\位运算简介及实用技巧\进阶篇.doc
     目录           0  2002-01-08 07:50  文档\倍增法\
     目录           0  2002-01-08 07:50  文档\倍增法\倍增思想的研究\
     目录           0  2002-01-08 07:50  文档\倍增法\倍增思想的研究\problem\
     目录           0  2002-01-08 07:50  文档\倍增法\倍增思想的研究\problem\197.files\
     文件        7611  2004-01-14 18:02  文档\倍增法\倍增思想的研究\problem\197.files\p197-01.gif
     文件        2101  2004-01-14 18:02  文档\倍增法\倍增思想的研究\problem\197.files\style-800.css
     文件        4147  2004-02-14 11:33  文档\倍增法\倍增思想的研究\problem\197.htm
     文件       24576  2004-04-19 22:38  文档\倍增法\倍增思想的研究\problem\fmf.doc
     目录           0  2002-01-08 07:50  文档\倍增法\倍增思想的研究\problem\Green.files\
     文件        4314  2004-02-14 14:13  文档\倍增法\倍增思想的研究\problem\Green.files\bg4.jpg
     文件       36160  2004-02-14 14:13  文档\倍增法\倍增思想的研究\problem\Green.files\cow1.jpg
     文件        9417  2004-02-14 14:23  文档\倍增法\倍增思想的研究\problem\Green.htm
     文件         640  2004-04-30 09:39  文档\倍增法\倍增思想的研究\problem\各题说明.txt
     目录           0  2002-01-08 07:50  文档\倍增法\倍增思想的研究\program\
     文件        2516  2003-02-15 17:37  文档\倍增法\倍增思想的研究\program\197.CPP
     文件        3612  2004-03-20 21:55  文档\倍增法\倍增思想的研究\program\dquery.cpp
     文件        1251  2004-04-19 17:57  文档\倍增法\倍增思想的研究\program\fib.cpp
     文件        5911  2004-03-27 15:08  文档\倍增法\倍增思想的研究\program\fmf.cpp
     文件        1383  2004-04-19 17:41  文档\倍增法\倍增思想的研究\program\power.cpp
     文件        1154  2004-04-19 22:12  文档\倍增法\倍增思想的研究\program\rmq.cpp
     文件         248  2004-04-19 22:40  文档\倍增法\倍增思想的研究\program\各程序说明.txt
     文件      142336  2004-04-30 09:38  文档\倍增法\倍增思想的研究\倍增思想的研究.doc
     文件          91  2004-04-16 15:28  文档\倍增法\倍增思想的研究\说明.txt
     文件      168960  2002-09-04 21:28  文档\分支高精度.ppt
............此处省略1004个文件信息