Noip2006普及组解题报告
By jlhsyxc
这次联赛题目总体比较简单，但有一些细节还是应该注意的。下面我们分别以每道题来谈谈。
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
*解答部分
此题是一道基础题，主要考了排序算法以及文件的简单操作。
我们先看此题的数据量N≤100，很容易想到此题可以用冒泡/直接插入/选择排序等时间复杂度为O(n*n)的算法。而且这样做不会超时。
实际上，由于0<ai<1001，且ai为整数，所以，我们不妨可以用桶排序做，这样代码可以短一些，时间也大大减少。
我们用Hash=0表示没有i这个数，hash=1 表示有i这个数。
那么，每次读一个I，只要做这种操作，最后统计一下即可。
注意点一：打印时，最后切勿多打空格，否则0分。
具体代码如下：
program noip2006_1_random;
const maxn=1050;
var a:array[1..maxn]of boolean;
i,n,x,max:longint;
procedure first;
begin
assign(input,'random.in');
assign(output,'random.out');
reset(input);rewrite(output);
end;
Begin
first;
readln(n);max:=0;
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
read(x);
a[x]:=true;
if max<x then max:=x;
end;
n:=0;
for i:=1 to max do if a then inc(n);
writeln(n);
for i:=1 to max-1 do
if a then write(i,' ');
if max<>0 then writeln(max);
close(input);close(output);
end.
2.开心的金明(happy.pas/c/cpp)
*题目部分
【问题描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入文件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
*解答部分
初看这道题，发现这题是个枚举。
用a表示第i个物品是否被取，即a=1表示取了，a=0表示没取。
等进位的枚举算法如下：
Fillchar(a,sizeof(a),0);
While a[0]=0 do
Begin
J:=m;
While a[j]=1 do dec(j);
A[j]:=1;
For i:=j+1 to m do a:=0;
End;
这样枚举次数为2^m,而此题中m（<25）。计算一下得33554432，有可能超时，所以我们继续思考。
发现此题是个经典的0/1背包问题，则立即可写出状态转移方程如下：
A[I,j]=max{a[i-1,j],a[i-1,j-w]+c}
其中w为重量，c为价值，在此题中w=v,c=w*p
其实数组还可以降维，只不过要把循环顺序改一下即可，即迭代的方法，具体代码如下：
program noip2006_2_happy;
const maxn=30100;maxm=30;
var a:array[0..maxn]of longint;
v,p,w,c:array[0..maxm]of longint;
n,m,i,j:longint;
procedure first;
begin
assign(input,'happy.in');
assign(output,'happy.out');
reset(input);rewrite(output);
readln(n,m);
for i:=1 to m do
begin
read(v);readln(p);
c:=p*v;
w:=v;
end;
end;
Begin
first;
for i:=1 to m do
for j:=n downto w do
if a[j]<a[j-w]+c then a[j]:=a[j-w]+c;
writeln(a[n]);
close(input);close(output);
end.
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
*解答部分
看了题目，会发现此题和noip2004普及组的《火星人》很像，但是又有一些差别。
其实《火星人》考的是生成排列，而此题考的是生成组合。
生成组合大致算法流程如下：
1. 从后向前找第一个未达到最大值的数a
2. a:=a+1
3. 后面的数都等于前面数加一
4. 判断a[0]，若a[0]=1则结束，否则转1
再结合题目，读入时只要转字符位数即可，即A:=ord(ch)-96
具体代码如下：
program noip2006_3_count;
var a:array[1..26]of longint;
s,t,w,i,p,q:longint;
str:string;
procedure first;
begin
assign(input,'count.in');
assign(output,'count.out');
reset(input);rewrite(output);
readln(s,t,w);
readln(str);
end;
Begin
first;
for i:=1 to w do
a:=ord(str)-96;
if t-s>w then
begin
p:=1;
while (p<=5)and(a[1]<t-w+1) do
begin
q:=w;
while (q>=1)and(a[q]=t-w+q) do dec(q);
if q<>0 then
begin
inc(a[q]);
for i:=q+1 to w do a:=a[i-1]+1;
for i:=1 to w do write(chr(a+96));
writeln;
inc(p);
end;
end;
end;
close(input);close(output);
end.
4.数列（sequence.pas/c/cpp）
*题目部分
【问题描述】
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第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*109）。（整数前不要有空格和其它符号）。
【输入样例】
3 100
【输出样例】
981
*解答部分
题目比较好懂，就不再解释了。
实际上，这道题是考枚举（BFS），数据量很小，但是又更优的算法。
我们先列一张表看一下：（此时k=3）
n 3^7 3^6 3^5 3^4 3^3 3^2 3^1 3^0 s
1 0 0 0 0 0 0 0 1 1
2 0 0 0 0 0 0 1 0 3
3 0 0 0 0 0 0 1 1 4
4 0 0 0 0 0 1 0 0 9
5 0 0 0 0 0 1 0 1 10
6 0 0 0 0 0 1 1 0 12
7 0 0 0 0 0 1 1 1 13
8 0 0 0 0 1 0 0 0 27
9 0 0 0 0 1 0 0 1 28
很明显，这道题的解s一定可以分成s=3^0*a[0]+3^1*a[1]+……+3^m*a[m]，而且我们发现表中a[1]至a[m]之间实际上是一个二进制序列。
这下算法就明朗了，只要将n转成二进制数，再按k的幂展开求和即可。
注意点，由于s均小于2.1*109，即这里暗示你用longint,就不能用integer,最好别用int64,Qword或extended（题目中的提示就应该是标程的类型）。
具体代码如下：
program noip2006_4_sequencet;
var k,n,ans,x,r:longint;
procedure first;
begin
assign(input,'sequence.in');
assign(output,'sequence.out');
reset(input);rewrite(output);
end;
Begin
first;
readln(k,n);
ans:=0;x:=1;
while n>0 do
begin
r:=n mod 2;
n:=n div 2;
ans:=ans+r*x;
x:=x*k;
end;
if ans=0 then writeln(1) else writeln(ans);
close(input);close(output);
end.
*本次联赛的小结
先说说我对今年联赛试题的小结吧。
我觉得，今年4道题目是解题多样性很好的体现，每道题都有不只一种算法可以AC，但是陷阱也是有的。比如说，有些同学第一题不注意输出格式，在末尾多打了一个空格；再比如说，有些同学看题不是很仔细，将第三题中“打印5个数”想当然的理解成“打印w个数”，导致此题得分很低。我想，这也就是为什么许多高手拿不到满分，而平时比较细心的人能拿高分的原因吧。
所以，我觉得，平时研究难题固然很重要，但是考试时的细心，策略往往显得更为重要。
