Plan中的树状数组被偶搞定拉!掌声鼓励!

果然是一个好东西!加油!

GDKOI'2007正等着偶！偶一定要死死地拿上几十分咯！
====================================
把最近的计划发上来哦..请大家监督偶..
[数据结构]
*随机搜索树
*伸展树
*树状数组
*哈希表
[串]
*KMP
*扩展KMP
[图]
*割点&割边
*极大连通子图&极大连通分支
*最小点基&最小汇基
*最大独立集&最小支配集
[网络流]
*标号法
*预流推进
......

荣幸地得了400分..Share4道Ac程序..
==========
program NOIp_random;
 const
  inputfile='random.in';
  outputfile='random.out';
 var
  n,m:byte;
  f:array[1..1000]of boolean;
 procedure origin;
  var
   i:byte;
   x:word;
  begin
   assign(input,inputfile);
   reset(input);
   readln(n);
   fillchar(f,sizeof(f),0);
   for i:=1 to n do
    begin
     read(x);
     f[x]:=true
    end;
   close(input)
  end;
 procedure main;
  var
   i:word;
  begin
   m:=0;
   for i:=1 to 1000 do
    if f[i] then
     inc(m)
  end;
 procedure printout;
  var
   flag:boolean;
   i:word;
  begin
   assign(output,outputfile);
   rewrite(output);
   writeln(m);
   flag:=false;
   for i:=1 to 1000 do
    if f[i] then
     if flag then
      write(' ',i)
      else
       begin
        write(i);
        flag:=true
       end;
   writeln;
   close(output)
  end;
 begin
  origin;
  main;
  printout
 end.
==========
program NOIp_happy;
 const
  maxn=30000;
  maxm=25;
  inputfile='happy.in';
  outputfile='happy.out';
 var
  m:byte;
  n:word;
  p:array[1..maxm]of byte;
  v:array[1..maxm]of word;
  f:array[0..maxm,0..maxn]of longint;
 procedure origin;
  var
   i:byte;
  begin
   assign(input,inputfile);
   reset(input);
   readln(n,m);
   fillchar(v,sizeof(v),0);
   fillchar(p,sizeof(p),0);
   for i:=1 to m do
    readln(v[i],p[i]);
   close(input)
  end;
 procedure main;
  var
   i:byte;
   j:word;
   x:longint;
  begin
   fillchar(f,sizeof(f),0);
   for i:=1 to m do
    for j:=0 to n do
     begin
      f[i,j]:=f[i-1,j];
      if j>=v[i] then
       begin
        x:=f[i-1,j-v[i]]+v[i]*p[i];
        if x>f[i,j] then
         f[i,j]:=x
       end
     end;
  end;
 procedure printout;
  begin
   assign(output,outputfile);
   rewrite(output);
   writeln(f[m,n]);
   close(output)
  end;
 begin
  origin;
  main;
  printout
 end.
==========
program NOIp_count;
 const
  inputfile='count.in';
  outputfile='count.out';
 var
  temp:shortint;
  s,t,w,total:byte;
  str:string;
  place,path:array[0..26]of byte;
  first:array[0..26]of boolean;
  letter:array[0..26]of char;
 procedure origin;
  begin
   readln(s,t,w);
   readln(str);
  end;
 procedure init;
  begin
   total:=0;
   temp:=t-s-w+1;
   fillchar(place,sizeof(place),0);
   fillchar(path,sizeof(path),0);
   fillchar(first,sizeof(first),1);
   fillchar(letter,sizeof(letter),0)
  end;
 procedure build_letter;
  var
   i:byte;
  begin
   for i:=s to t do
    letter[i-s+1]:=chr(i+96);
  end;
 procedure build_place;
  var
   i:byte;
  begin
   for i:=1 to w do
    repeat
     inc(place[i])
    until str[i]=letter[place[i]]
  end;
 procedure print;
  var
   i:byte;
  begin
   for i:=1 to w do
    write(letter[path[i]]);
   writeln
  end;
 procedure qtry(dep:byte);
  var
   i:byte;
  begin
   if dep<=w then
    begin
     if first[dep] then
      begin
       i:=place[dep];
       first[dep]:=false
      end
      else
       i:=path[dep-1]+1;
     for i:=i to temp+dep do
      begin
       path[dep]:=i;
       qtry(dep+1)
      end
    end
    else
     begin
      if total>0 then
       if total>5 then
        begin
         close(output);
         halt
        end
        else
         print;
      inc(total)
     end
  end;
 procedure main;
  begin
   build_letter;
   build_place;
   qtry(1)
  end;
 begin
  assign(input,inputfile);
  reset(input);
  assign(output,outputfile);
  rewrite(output);
  origin;
  init;
  main;
  close(input);
  close(output)
 end.
==========
program NOIp_sequence;
 const
  inputfile='sequence.in';
  outputfile='sequence.out';
 var
  k,power:shortint;
  n:word;
  p:array[0..10]of longint;
  f:array[0..2000]of longint;
 procedure origin;
  begin
   assign(input,inputfile);
   reset(input);
   readln(k,n);
   close(input)
  end;
 procedure build_power;
  var
   power2,powerk,limit2,limitk:longint;
  begin
   power:=0;
   power2:=1;
   powerk:=1;
   limit2:=1000 div 2;
   limitk:=maxlongint div k;
   while (power2<=limit2)and(powerk<=limitk) do
    begin
     inc(power);
     power2:=power2*2;
     powerk:=powerk*k;
    end
  end;
 procedure build_p;
  var
   i:byte;
  begin
   fillchar(p,sizeof(p),0);
   p[0]:=1;
   for i:=1 to power do
    p[i]:=p[i-1]*k
  end;
 procedure qtry(start,dep:byte;sum:longint);
  var
   i:byte;
  begin
   if dep=0 then
    begin
     inc(f[0]);
     f[f[0]]:=sum;
     exit
    end;
   for i:=start to power-dep+1 do
    qtry(i+1,dep-1,sum+p[i])
  end;
 procedure build_f;
  var
   i:byte;
  begin
   fillchar(f,sizeof(f),0);
   for i:=1 to power do
    qtry(0,i,0);
  end;
 procedure sort_f;
  var
   i,j:word;
   temp:longint;
  begin
   for i:=1 to f[0]-1 do
    for j:=i+1 to f[0] do
     if f[j]<f[i] then
      begin
       temp:=f[i];
       f[i]:=f[j];
       f[j]:=temp
      end
  end;
 procedure main;
  begin
   build_power;
   build_p;
   build_f;
   sort_f;
  end;
 procedure printout;
  begin
   assign(output,outputfile);
   rewrite(output);
   writeln(f[n]);
   close(output)
  end;
 begin
  origin;
  main;
  printout
 end.
==========

 

1.明明的随机数

（random.pas/c/cpp）

【问题描述】

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

【输入文件】

输入文件random.in 有2行，第1行为1个正整数，表示所生成的随机数的个数：

N

第2行有N个用空格隔开的正整数，为所产生的随机数。

【输出文件】

输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】

   10

   20 40 32 67 40 20 89 300 400 15

【输出样例】

   8

   15 20 32 40 67 89 300 400

 

2.开心的金明

(happy.pas/c/cpp)

【问题描述】

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j₁，j₂，……，j_k，则所求的总和为：

v[j₁]*w[j₁]+v[j₂]*w[j₂]+ …+v[j_k]*w[j_k]。（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

【输入文件】

输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：

N  m

（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数

v  p

（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

【输出文件】

输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

【输入样例】

1000 5

800 2

400 5

300 5

400 3

200 2

【输出样例】

3900

 

                            3.Jam的计数法

 

                           （count.pas/c/cpp）

【问题描述】

Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U<V，且不存在Jam数字P，使U<P<V）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。

【输入文件】

输入文件counting.in 有2行，第1行为3个正整数，用一个空格隔开：

s t w

（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s<t≤26, 2≤w≤t-s ）

第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。

所给的数据都是正确的，不必验证。

【输出文件】

输出文件counting.out 最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。

【输入样例】

   2 10 5

   bdfij

【输出样例】

bdghi

bdghj

bdgij

bdhij

befgh

 

4.数列

                      （sequence.pas/c/cpp）

 

【问题描述】

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：

1，3，4，9，10，12，13，…

（该序列实际上就是：3⁰，3¹，3⁰+3¹，3²，3⁰+3²，3¹+3²，3⁰+3¹+3²，…）

请你求出这个序列的第N项的值（用10进制数表示）。

例如，对于k=3，N=100，正确答案应该是981。

【输入文件】

输入文件sequence.in 只有1行，为2个正整数，用一个空格隔开：

k N

（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。

【输出文件】

输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10⁹）。（整数前不要有空格和其他符号）。

【输入样例】

   3 100

【输出样例】

981