NOIP2006普及组复赛试题

1.明明的随机数

（random.pas/c/cpp）

【问题描述】

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

【输入文件】

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

N

第二行有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件物品，编号依次为j1，j2，……，jk，则所求总和为：

　　v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。

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

【输入文件】

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

N m

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

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

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)
[问题描述l
Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的(使用相同个数的字母)，英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b，c，d，e，f，g，h／i／i)这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfii”之后的数字应该是“bdghi”。(如果我们用U、V依次表示Jam数字“bdfii”与“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
bdfii
[输出样例]
bdghi
bdghi
bdgij 1
bdhii
befgh
4．数列
(Seqlaence．pas／c／c~p)
[问题描述]
给定一个正整数k(3≤k≤土5)，把所有k的方幂及所有有限个互不相等的k的方幂之和构成 ——个递增的序列，例如，当k=3时，这个序列是：
l， 3， 4， 9， 10， 12， 13， …
(该序歹实际上就是：30，31，30＋31，32，30＋32，31＋32，30＋31＋32…
请你求出这个序列的第N项的值(用土0进制数表示)。
例如，对于k=3，N=100，正确答案应该是98l。
[输入文件]
输入文件sequence．in只有l行，为2个正整数，用一个空格隔开：
k N
(k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000)。
[输出文件]
输出文件sequence．out为计算结果，是一个正整数(在所有的测试数据中，结果均不超过
2.1*10)。(整数前不要有空格和其他符号)。
[输入样例]
3 100
[输出样例]
981

先说明一下,普及组是初中参与的,提高组是高中参加的.

再写一下我的算法:
1.就是简单的排序,即使是效率最第的冒泡排序都可以通过
2.动态规划
typedef struct
{
int v;
char p;
} data;
#include<stdio.h>
int main(void)
{
int i,k;
long countline[30000];
data datas[25];
int n,m;
FILE *input,*output;
input=fopen("happy.in","r");
fscanf(input,"%d%d",&n,&m);
for(i=0;i<m;i++) fscanf(input,"%d%d",&datas[i].v,&datas[i].p);
fclose(input);
for(i=0;i<m;i++)
for(k=n;k>0;k--)
if(k>=datas[i].v && (countline[k]<datas[i].v*datas[i].p+countline[k-datas[i].v]))
countline[k]=datas[i].v*datas[i].p+countline[k-datas[i].v];
output=fopen("happy.out","w");
fprintf(output,"%ld",countline[n]);
fclose(output);
return 0;
}
3.全排列(这是四个题中最难的)
4.实质是兔子数列

嘿嘿,有题做啦,谢啦

问下孔明,学数据结构看什么书好啊

请问弟3题用递归,怕不怕效率太慢的啊呀

#include <stdio.h>
int main()
{
int s,t,w,i,ok,g=5;
char a[26];
FILE *input,*output;
input=fopen("counting.in","r");
output=fopen("counting.out","w");
fscanf(input,"%d%d%d%s",&s,&t,&w,a);
fclose(input);
for(i=0;i<w;i++)
a[i]=a[i]-'a'+1;
while(a[0]<=t)
{
a[w-1]++;
if(a[w-1]>t)
{
for(i=w-1;i>0;i--)
{
if(a[i]>t)
{
a[i]=s;
a[i-1]++;
}
else
break;

}
if(a[0]>t)
break;
else
continue;
}
for(i=0;i<w-1;i++)
{
if(a[i]<a[i+1])
ok=1;
else
{
ok=0;
break;
}
}
if(ok==1)
{
for(i=0;i<w;i++)
fprintf(output,"%c",a[i]+'a'-1);
fprintf(output,"\n");
g--;
}
if(g==0)
break;
}
fclose(output);
getch();
}

第三题这样做可不可以啊,我才初二啊,不太会C,给点建议.

只要讲的透彻就行,我是看的noi教程

数据规模较小,且第归较易实现,因此用第归就可以(如果是提高组的就得用其它方法)

我也初二，差距阿!!!!!!!

Me too