NOIP2004:

1．Joseph

题目描述:

原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。

现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。

输入:

仅有的一个数字是k（0 < k <14）。

输出:

    使得最先出列的k个人都是坏人的m的最小值。

输入样例:

4

输出样例:

30

程序：

#include <>

long k, m, begin;

int check(long remain){

    long result = (  ①  ) % remain;

    if (  ②  ){

       begin = result; return 1;

    }

    else return 0;

}

int main(){

    long i, find = 0;

    scanf("%ld", &k);

    for (m = k;   ③  ; m++){

       find = 1; begin = 0;

       for (i = 0; i < k; i++)

           if (!check(  ④  )){

              find = 0; break;

           }

    }

    printf("%ld\n",   ⑤  );

    return 0;

}

2．逻辑游戏

题目描述:

一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。

对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。

输入:

输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。

输入的第一行是n（0

输出:

    当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。

输入样例:

3

1 1 2

1 2 2

1 1 2

输出样例:

    YES

程序：

#include <>

#include <>

int orig, n, ns, a[102][102], bun;

int d[]={1, 0, -1, 0, 0, 1,   ①  };

void plimba(int x, int y){

    int i, x1, y1;

    a[x][y] = -a[x][y];

    if (abs(a[x - 1][y]) != orig && (  ②   != a[x - 1][y]

|| abs(a[x][y - 1]) != orig)) ns++;

    if (abs(a[x + 1][y]) != orig && (a[x + 1][y - 1] != a[x + 1][y]

|| abs(a[x][y - 1]) != orig)) ns++;

    if (abs(a[x][y - 1]) != orig && (  ③   != a[x][y - 1]

|| abs(a[x - 1][y]) != orig)) ns++;

    if (abs(a[x][y + 1]) != orig && (a[x - 1][y + 1] != a[x][y + 1]

|| abs(a[x - 1][y]) != orig)) ns++;

    for (i = 0; i < 4; i++){

       x1 = x + d[2 * i]; y1 = y +   ④  ;

    if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= n &&   ⑤  )

plimba(x1, y1);

    }

}

int main(){

    int i, j;

    bun = 1;

    scanf("%d", &n);

    for (i = 0; i <= n+1; i++)

 for (j = 0; j <= n+1; j++) a[i][j] = 0;

    a[0][0] = -1; a[n + 1][0] = -1;

a[0][n + 1] = -1; a[n + 1][n + 1] = -1;

    for (i = 1; i <= n; i++)

for ( j = 1; j <= n; j++) scanf("%d", &(a[i][j]));

    for (i = 1; i <=n ; i++)

       for (j = 1; j <= n; j++){

           if (a[i][j] > -1){

              ns = 0;   ⑥  ;

              plimba(i, j);

              if (ns % 2 == 1)bun = 0;

           }

       }

    if (bun) printf("YES\n"); else printf("NO\n");

    return 0;

}

NOIP2005:

1．木材加工
题目描述:
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定了的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。
木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
输入:
第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
输出:
输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。
输入样例:
3 7
232
124
456
输出样例:
114
程序：
#include
int n, k, len[10000];
int isok(int t) {
int num = 0, i;
for (i = 0; i < n; i++) {
if (num >= k) break;
num = ① ;
}
if ( ② ) return 1;
else return 0;
}
int main() {
int i, left, right, mid;
scanf("%d%d", &n, &k);
right = 0;
for (i = 0; i < n; i++) {
scanf("%d", &(len[i]));
if (right < len[i]) right = len[i];
}
right++;
③ ;
while ( ④ < right) {
mid = (left + right) / 2;
if ( ⑤ ) right = mid;
else left = mid;
}
printf ("%d\n", left);
return 0;
}

NOIP2006

1．（选排列）下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数中取 k(1<=k<=n)个数的全部可能的排列（不一定按升序输出）。例如，当 n=3，k=2 时，应该输出（每行输出 5 个排列）：

12 13  21  23   32

31

程序：

#include <>

int n,k,a[10];

long count=0;

void perm2(int j)

{int i,p,t;

if(    ①   )

   {for(i=k;i<=n;i++)

  {count++;

   t=a[k]; a[k]=a[i]; a[i]=t;

   for(     ②  )

  printf("%1d",a[p]);  /* "%1d"中是数字 1，不是字母 l */

   printf("  ");

   t=a[k];a[k]=a[i];a[i]=t;

   if(count%5==0) printf("\n");

   }

return;

   }

for(i=j;i<=n;i++)

   {t=a[j];a[j]=a[i];a[i]=t;

③  ;

t=a[j];     ④   ;

   }

}

main()

{int i;

  printf("\nEntry n,k (k<=n):\n");

  scanf("%d%d",&n,&k);

  for(i=1;i<=n;i++)  a[i]=i;

⑤   ;

}

2．N叉树
题目描述:
我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不是唯一的了。但是我们可以计算满足条件的不同二叉树的一共有多少个。这不是一个很困难的问题，稍微复杂一点，我们把这个问题推广到N叉树。
我们用小写英文字母来表示N叉树的结点，不同的结点用不同的字母表示。比如，对于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以得到6个不同的4叉树（如下图）。

输入:
输入数据包括3行。
第一行是一个正整数N(1 ≤ N ≤ 20)，表示我们要考虑N叉树。
第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。
输出:
输出不同的N叉树的数目。题目中给的数据保证得到的结果小于231。
输入样例:
4
abdefgc
defgbca
输出样例:
6
程序：
#include
#include
char str1[100], str2[100];
int N;
long com[100][100];
long getcom(int x, int y) {
if (y == 0 || x == y) ① ;
else if (com[x][y] != 0) return com[x][y];
else {
com[x][y] = getcom(x - 1, y)+ ② ;
return com[x][y];
}
}
long count(int a, int b, int c){
long sum = 1;
int k = 0;
int s = a + 1, t = c, p;
if (a == b) return 1;
while(s <= b){
p = t;
while(str1[s] != str2[t]) t++;
sum = sum * count(s, s + t - p, p);
s = ③ ;
④ ;
k++;
}
return ⑤ * getcom(N, k);
}
int main(){
int len;
scanf("%d", &N);
scanf("%s%s", str1, str2);
len = strlen(str1);
printf("%ld\n", count( ⑥ ));
return 0;
}

NOIP2006:

（选排列）下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数中取 k(1<=k<=n)个数的

全部可能的排列（不一定按升序输出）。例如，当 n=3，k=2 时，应该输出（每行输出 5 个排列）：

12 13  21  23 32

31

程序：

#include <> int n,k,a[10]; long count=0;

void perm2(int j)

{int i,p,t;

if(    ①   )

   {for(i=k;i<=n;i++)

  {count++;

   t=a[k]; a[k]=a[i]; a[i]=t;

   for(     ②  )

  printf("%1d",a[p]);  /* "%1d"中是数字 1，不是字母 l */

   printf("  ");

   t=a[k];a[k]=a[i];a[i]=t;

   if(count%5==0) printf("\n");

   }

return;

   }

for(i=j;i<=n;i++)

   {t=a[j];a[j]=a[i];a[i]=t;

③  ;

t=a[j];     ④   ;

   }

}

main()

{int i;

  printf("\nEntry n,k (k<=n):\n");

  scanf("%d%d",&n,&k);

  for(i=1;i<=n;i++)  a[i]=i;

⑤   ;

}

2．（TSP 问题的交叉算子）TSP 问题(Traveling Salesman Problem)描述如下：给定 n 个城

市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环 路，每个城市恰好经过一次，求使总代价达到最小的一条环路。

遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法 之一是 1 到 n 这 n 个数字的一个排列，每个数字为一个城市的编号。例如当 n=5 时，“3 4 2 15”表示该方案实施的路线为 3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两 个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：

 (1)选定中间一段作为互换段，该段的起止下标为 t1，t2，随机生成 t1，t2 后，互换两段。

 (2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：

 ) 将两个互换段中，共同的数字标记为 0，表示已处理完。

 ) 将两个互换段中其余数字标记为 1，按顺序将互换段外重复的数字进行替换。 例               如：n=12，两个个体分别是：

a1: 1 3 5 4  * 2  6 7  9  * 10 12 8 11

a2: 3 2 1 12 * 6 7 10 11 * 8  5  4  9

t1=5，t2=8。

上述每一行中，两个星号间的部分为互换段。假定数组的下标从 1 开始，互换后有：

a1: 1 3 5 4 * 6 7 10 11  * 10 12 8 11

a2: 3 2 1 12 * 2 6  7  9  *  8  5  4  9

然后，将数字 6,7 对应的项标记为 0，星号内数字 2,9,10,11 对应的项标记为 1，并且按顺序对 应关系为:10<->2，11<->9。于是，将 a1[9]=10 替换为 a1[9]=2，将 a2[2]=2 替换为 a2[2]=10，

类似再做第 2 组替换。这样处理后，就得到了两个新个体：

a1: 1 3  5  4  6 7 10 11 2 12 8  9

a2: 3 10 1 12 2 6 7   9 8  5  4  11

（3）输出两个新个体的编码。

程序：

#include <>

#include <>

#define N 20

int a1[N],a2[N],kz1[N],kz2[N]，n;

int rand1(int k)

{int t=0;

while(t<2|| t>k)

  t=(int)((double)rand()/RAND_MAX*k);

return t;

}

void read1(int a[],int m)

{读入数组元素 a[1]至 a[m]，a[0]=0，略。}

void wrt1(int a[],int m)

{输出数组元素 a[1]至 a[m]，略。}

void cross(int a1[], int a2[],int t1, int t2, int n)

{int i,j,k,t,kj;

for(i=t1; i<=t2; i++)

  {t=a1[i];      ①    ；

}

for(i=1;i<=n;i++)

  if(it2)

   kz1[i]=kz2[i]=-1;

   else

②   ；

for(i=t1;i<=t2;i++)

   for(j=t1;j<=t2;j++)

   if(a1[i]==a2[j])

  {    ③   ;  break;

  }

for(i=t1;i<=t2;i++)

  if(kz1[i]==1)

  {for(j=t1;j<=t2;j++)

   if(kz2[j]==1)

     {kj=j; break;

      }

   for(j=1;j<=n;j++)

      if(    ④   )

{a1[j]=a2[kj];break;

  }

   for(j=1;j<=n;j++)

      if(    ⑤   )

{a2[j]=a1[i]; break;

  }

 }

   kz1[i]=kz2[kj]=0;

  }

main()

{int k,t1,t2;

printf("input (n>5):\n");  scanf("%d",&n);

printf("input array 1 (%d'numbers):\n",n);             read1(a1,n);

printf("input array 2 (%d'numbers):\n",n);             read1(a2,n);

t1=rand1(n-1);

do

{t2=rand1(n-1);

}while(t1==t2);

if(t1>t2)

  {k=t1; t1=t2; t2=k;

  }

⑥

wrt1(a1,n);  wrt1(a2,n);

}

NOIP2007:

1． （格雷码，Gray Code）

格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个

二进制位不同，以4位二进制数为例，编码如下：

如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数 -模转换等领域。下面程序的任务是：由键盘输入二进制数的位数 n (n<16)，再输入一个十进制数 m(0≤m<2ⁿ)，然后输出对应于 m的格雷码（共 n位，用数组 gr[]存放）。为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数起，由0变为1，或由1变为0。

 #include <>

main()

{int bound=1,m,n,i,j,b,p,gr[15];

 printf("input n,m\n");

 scanf("%d%d",&n,&m);

for(i=1;i<=n;i++) bound=   ①  ;

 if(m<0||m>=bound)

   {printf("Data error!\n");

       ②   ;

   }

 b=1;

 for(i=1;i<=n;i++)

  {p=0; b=b*2; 

 for(   ③  ;j<=m;j++)

     if(   ④   )

      p=1-p;

   gr[i]=p;

  }

 for(i=n;    ⑤   )

  printf("%1d",gr[i]);  /* 在 "%1d" 中出现的是数字1，不是字母l */

 printf("\n");

}

2．（连续邮资问题）某国发行了n种不同面值的邮票，并规定每封信最多允许贴m张邮票，在这

些约束下，为了能贴出{1，2，3,…，maxvalue}连续整数集合的所有邮资，并使maxvalue的值最

大，应该如何设计各邮票的面值？例如，当n=5、m=4时，面值设计为{1，3，11，15，32}，可使

maxvalue达到最大值70（或者说，用这些面值的1至4张邮票可以表示不超过70的所有邮资，但无

法表示邮资71。而用其他面值的1至4张邮票如果可以表示不超过k的所有邮资，必有k≤70）。

下面是用递归回溯求解连续邮资问题的程序。数组x[1:n]表示n种不同的邮票面值，并约定各元

素按下标是严格递增的。数组 bestx [1:n]存放使maxvalue达到最大值的邮票面值（最优解），

数组y[maxl]用于记录当前已选定的邮票面值x[1:i]能贴出的各种邮资所需的最少邮票张数。 请将程

序补充完整。

#include <>

#define NN 20

#define maxint 30000

#define maxl 500  /*邮资的最大值*/

int n,m,bestx[NN],x[NN],y[maxl],maxvalue=0;

void result()

{输出结果：最大值：maxvalue  及 最优解： bestx[1:n]（略）

}

void backtrace(int i,int r)

{ int j,k,z[maxl];

 for(j=0;j<=   ①   ;j++)

   if(y[j]

     for(k=1;k<=m-y[j];k++)

      if(y[j]+k<=y[   ②   ])

        y[  ③   ]=y[j]+k;

     while(y[r]

  if(i>n)

  {if(r-1>maxvalue)

   {maxvalue=   ④   ;    

    for(j=1;j<=n;j++)

     bestx[j]=x[j];

   }

   return;

  }

for(k=0;k

   z[k]=y[k];

 for(j=   ⑤   ;j<=r;j++)

 {x[i]=j;

     ⑥  ;

  for(k=0;k

  y[k]=z[k];

 }

}

void main()

{int j;

printf("input n,m:\n");

 scanf(“%d%d”,&n,&m);

 for(j=1;j

   y[j]=maxint;

 y[0]=0;  x[0]=0; x[1]=1;

 backtrace(2,1);

 result();

}

NOIP2008:

1．(找第k大的数) 给定一个长度为1,000,000的无序正整数序列，以及另一个数n(1<=n<=1000000)，接下来以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。

#include <>

#include <>

int a[1000001],n,ans = -1;

void swap(int *a,int *b)

{

int c;

c = *a; *a = *b; *b = c;

}

int FindKth(int left, int right, int n)

{

int tmp,value,i,j;

if (left == right) return left;

tmp = rand()% (right - left) + left;

swap( &a[tmp], &a[left] );

value =          ①        

i = left;

j = right;

while (i < j)

{

     while (i < j &&            ②        ) j --;

     if (i < j) {a[i] = a[j]; i ++;} else break;

     while (i < j &&            ③        ) i ++;

     if (i < j) {a[j] = a[i]; j - -;} else break;

}

        ④        

if (i < n) return  FindKth(               ⑤            );

if (i > n) return                   ⑥                    

return i;

}

int main()

{

int i;

int m = 1000000;

for (i = 1;i <= m;i ++)

     scanf("%d", &a[i]);

scanf("%d", &n);

ans = FindKth(1,m,n);

printf("%d\n", a[ans]);

 return 0;

}

2．（矩阵中的数字）有一个n*n(1<=n<=5000)的矩阵a， 对于1<=i < n,1<=j<=n,  a[i,j] < a[i + 1,j]  a[j,i] < a[j,i+1]。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵a中的一个数字k，找出k所在的行列（注意：输入数据保证矩阵中的数各不相同）。

#include <>

int n,k,answerx,answery;

int a[5001][5001];

void FindKPosition()

{

int i = n,j = n;

while (j > 0)

{

     if (a[n][j] < k) break;              

     j --;

}

              ①            

while (a[i][j] != k)

{

     while (              ②              && i > 1) i --;

     while (              ③              && j <= n) j ++;

}

              ④            

              ⑤            

}

int main()

{

int i,j;

scanf( "%d", &n );

for (i = 1;i <= n;i ++)

     for (j = 1;j <= n;j ++)

        scanf( "%d", &a[i][j]);

scanf( "%d", &k );

FindKPosition();

printf("%d %d\n", answerx, answery);

return 0;

}

NOIP2009:

1．（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。

#include <>

int a[101];

int n,i,ans,len,tmp,beg,end;

int main(){

  scanf("%d",&n);

  for (i=1;i<=n;i++)

     scanf("%d",&a[i]);

  tmp=0;

  ans=0;

  len=0;

  beg=     ①     ;

  for (i=1;i<=n;i++){

     if (tmp+a[i]>ans){

         ans=tmp+a[i];

         len=i-beg;

     }

     else if (        ②         &&i-beg>len)

         len=i-beg;

     if (tmp+a[i]    ③     ){

         beg=     ④     ;

         tmp=0;

     }

     else

            ⑤        ;

  }

  printf("%d %d\n",ans,len);

  return 0;

}

2. (寻找等差数列)  有一些长度相等的等差数列（数列中每个数都为0~59的整数），设长度均为L，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先，L最大可能为多大？先读入一个数n（1<=n<=60），再读入n个数，代表打乱后的数。输出等差数列最大可能长度L。

#include <>

int hash[60];

int n, x, ans, maxnum;

int work(int now) {

    int first, second, delta, i;

    int ok;

    while (      ①       && !hash[now])

       ++now;

    if (now > maxnum)

       return 1;

    first = now;

    for (second = first; second <= maxnum; second++)

       if (hash[second]) {

           delta =       ②       ; 

           if (first + delta *    ③      > maxnum)

              break;

           if (delta == 0)

              ok = (      ④      );

           else{

              ok = 1;

              for (i = 0; i < ans; i++)

                  ok =     ⑤     && (hash[first+delta*i]);

           }

           if (ok){

              for (i = 0; i < ans; i++)

                  hash[first+delta*i]--;

              if (work(first))

                  return 1;

              for (i = 0; i < ans; i++)

                  hash[first+delta*i]++;

           }

       }

    return 0;

}

int main(){

    int i;

    memset(hash, 0, sizeof(hash));

    scanf("%d", &n);

    maxnum = 0;

    for (i = 0; i < n; i++){

       scanf("%d", &x);

       hash[x]++;

       if (x > maxnum)

           maxnum = x;

    }

    for (ans = n; ans >= 1; ans--)

       if ( n%ans==0 &&     ⑥     ) {

           printf("%d\n", ans);

           break;

       }

    return 0;

}

NOIP2010:

1.（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸，在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n()和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

    例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体的方法是：甲、乙一起过桥到河的左岸，家单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+4=7.

#include<>

#define SIZE 100

#define INFINITY 10000

#define LEFT 1

#define RIGHT 0

#define LEFT_TO_RIGHT 1

#define RIGHT_TO_LEFT 0

int n,time[SIZE],pos[SIZE];

int max(int a,int b)

{

    if(a>b)

       return a;

    else

       return b;

}

int go(int stage)

{

    int i,j,num,tmp,ans;

    if(stage== RIGHT_TO_LEFT)

    {

       num =0;

       ans =0;

       for (i=1;i<=n ;i++ )

       {

           if (pos[i]==RIGHT)

           {

              num++;

              if (time[i]>ans)

              {

                  ans =time[i];

              }

           }

       }

       if (__①___)

       {

           return ans;

       }

       ans = INFINITY;

       for (i=1;i<=n-1 ;i++ )

       {

           if(pos[i]==RIGHT)

           {

              for (j =i+1;j<=n ;j++ )

              {

                  if (pos[j] ==RIGHT)

                  {

                     pos[i] = LEFT;

                     pos[j] = LEFT;

                     tmp = max(time[i],time[j]) + ___②___;

                     if (tmp

                     pos[i] = RIGHT;

                     pos[j] = RIGHT;

                  }

              }

           }

       }

       return ans;

    }

    if(stage == LEFT_TO_RIGHT)

    {

       ans = INFINITY;

       for (i=1;i<=n;i++ )

       {

           if (___③____)

           {

              pos[i]= RIGHT;

              tmp = ____④____;

              if (tmp

                  ans =tmp;

              ____⑤_____

           }

       }

       return ans;

    }

    return 0;

}

int main()

{

    int i;

    scanf("%d",&n);

    for (i=1;i<=n ;i++ )

    {

       scanf("%d",&time[i]);

       pos[i] = RIGHT;

    }

    printf("%d\n",go(RIGHT_TO_LEFT);

    return 0;

}

2.（烽火传递）烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传递，在连续m个烽火台中至少有一个发出信号。现输入n、m和每个烽火台发出信号的代价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。

    例如，有5个烽火台，他们发出信号的代价一次为1、2、5、6、2，且m为3，则总共最少花费的代价为4，即由第2个和第5个烽火台发出信号。

#include<>

#define SIZE 100

int n,m,r,value[SIZE],heap[SIZE},pos[SIZE],home[SIZE],opt[SIZE];

//heap[i] 表示用顺序数组存储的堆heap中第i个元素的值

//pos[i]  表示opt[i]在堆heap中的位置，即heap[pos[i]]=opt[i]

//home[i] 表示heap[i]在序列opt中的位置，即opt[home[i]]=heap[i]

void swap(int i, int j)//交换堆中的第i和第j个元素

{

    int tmp;

    pos[home[i]] =j;

    pos[home[j]] =i;

    tmp = heap[i];

    heap[i] = heap[j];

    heap[j] = tmp;

    tmp = home[i];

    home[i] = home[j];

    home[j] = tmp;

}

void add(int k)//在堆中插入opt[k]

{

    int i;

    r++;

    heap[r] = __①__;

    pos[k] = r;

    ____②____;

    i=r;

    while ((i>1)&&(heap[i]

    {

       swap(i,i/2);

       i /= 2;

    }

}

void remove(int k)//在堆中删除opt[k]

{

    int i,j;

    i = pos[k];

    swap(i,r);

    r--;

    if (i==r+1)

       return;

    while ((i>1)&&(heap[i]

    {

       swap(i,i/2);

       i /= 2;

    }

    while (i+1<=r)

    {

       if ((i+i+1<=r)&&(heap[i+i+1]

           j = i+i+1;

       else

           ____③___;

       if (heap[i]>heap[j])

       {

           ____④____;

           i = j;

       }

       else

           break;

    }

}

int main()

{

    int i;

    scanf("%d %d",&n,&m);

    for (i=1;i<=m;i++)

    {

       opt[i] = value[i];

       add(i);

    }

    for (i=m+1;i<=n ;i++ )

    {

       opt[i] = ___⑤____;

       remove(__⑥___);

       add(i);

    }

    printf("%d\n",heap[1]);

    return 0;

}

NOIP2004:

1.

（1）      start+m-1                         　         

（2）      result>=k  (或者k<=result)

（3）   　 find==0               　　           

（4）      2*k-i                          

（5）      m-1                                                  

2.

 (1)     0,-1

（2）    a[x-1,y-1]

（3）    a[x-1,y-1]

（4）    d[2*i+1]

（5）    a[x1,y1]=orig

（6）    orig=a[i,j]

NOIP2005:

1.

（1）     num + len[i] / t                         　         

（2）     num >= k           　　　　           　  

（3）     left = 0                　　           

（4）     left + 1                          

（5）     !isok(mid) （或者 isok(mid) == 0）                                               

2.

（1）     return 1 （或者 return1L，或者 return1l）

（2）     getcom(x - 1, y - 1)

（3）     s + t - p + 1

（4）     t++  （或者 ++t，或者 t = t + 1，或者 t += 1）

（5）     sum

（6）     0, len - 1, 0

NOIP2006:

1．①  j==k （或 k==j）由收集

②  p=1;p<=k;p++

③  perm2(j+1)

④  a[j]=a[i];a[i]=t

⑤  perm2(1)

2．①  a1[i]=a2[i];a2[i]=t

②  kz1[i]=kz2[i]=1

③  kz1[i]=kz2[j]=0

④  a1[j]==a1[i]  &&  kz1[j]==-1

⑤  a2[j]==a2[kj]  &&  kz2[j]==-1

⑥  cross(a1,a2,t1,t2,n)

NOIP2007:

1  ① bound*2   ② return 或 exit(0)   ③ j=0  
 ④(j%b-(b/2))==0 
 ⑤ i>=1;i—- 或 i>0;i--
2  ① x[i-2]*(m-1)    ② j+x[i-1]*k  
③ j+x[i-1]*k （同2）  
   ④  r-1     
   ⑤  x[i-1]+1   
  ⑥ backtrace(i+1,r)

NOIP2008:

1.  ① a[left];

② a[j] < value (或a[j] <= value)

③ a[i] > value （或a[i] >= value）

④ a[i] = value;

⑤ i + 1,right,n

⑥ FindKth(left, i – 1, n);

2.  ① j++; （或者 j += 1; 或者 j=j+1;）

② a[i][j] > k

③ a[i][j] < k

④ answerx = i;

⑤ answery = j;

NOIP2009:

3. 

① 0

 ② tmp+a[i]==ans 或者 a[i]+tmp==ans 或者ans==a[i]+tmp等

 ③ <0

④ i

 ⑤ tmp+=a[i] 或者 tmp=tmp+a[i]

4. 

① now<=maxnum 或者 !(now>maxnum)

 ② second-first

③ (ans-1)

④ hash[first]>=ans 或者 hash[second]>=ans 或者 hash[first+delta]>=ans

 ⑤ ok

⑥ work(0) 或者 work(0)==1 或者 work(0)>0等

NOIP2010:

（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）

1．① num <= 2（或num < 3 或num = 2）

② go(LEFT_TO_RIGHT)

③ pos[i] == LEFT（或LEFT == pos[i]）

④ time[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) + time[i]）

⑤ pos[i] = LEFT

本小题中，LEFT可用1代替，LEFT_TO_RIGHT可用1代替，RIGHT_TO_LEFT可用0代替。

2．① opt[k]

② home[r] := k

③ j = i + i（或j = 2 * i 或j = i * 2）

④ swap(i, j)（或swap(j, i)）

⑤ value[i] + heap[1]（或heap[1] + value[i]）

⑥ i - m