分享到新浪微博 分享到QQ空间 打印

[灌水] NOIP2008提高组复赛试题

NOIP2008提高组复赛试题

http://www.xystudio.cn/jsfd/UploadFiles_8843/200811/2008111618260636.doc

1. 笨小猴 
(wird.pas/c/cpp) 

【问题描述】 

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大! 

这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果maxn-minn是一个质数,那么笨小猴就认为这是个Lucky Word,这样的单词很可能就是正确的答案。 

【输入】 

输入文件word.in只有一行,是一个单词,其中只可能出现小写字母,并且长度小于100。 

【输出】 

输出文件word.out共两行,第一行是一个字符串,假设输入的的单词是Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”; 

第二行是一个整数,如果输入单词是Lucky Word,输出maxn-minn的值,否则输出0。 

【输入输出样例1】 

word.in 
word.out 

error 
Lucky Word 



【输入输出样例1解释】 

单词error中出现最多的字母r出现了3次,出现次数最少的字母出现了1次,3-1=2,2是质数。 

【输入输出样例2】 

word.in 
word.out 

Olymipic 
No Answer 



【输入输出样例2解释】 

单词olympic中出现最多的字母i出现了2次,出现次数最少的字母出现了1次,2-1=1,1不是质数。 

2. 火柴棒等式 
(matches.pas/c/cpp) 

【问题描述】 

给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示: 


注意: 

1. 加号与等号各自需要两根火柴棍 

2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C>=0) 

3. n根火柴棍必须全部用上 

【输入】 

输入文件matches.in共一行,又一个整数n(n<=24)。 

【输出】 

输出文件matches.out共一行,表示能拼成的不同等式的数目。 

【输入输出样例1】 

matches.in 
matches.out 

14 



【输入输出样例1解释】 

2个等式为0+1=1和1+0=1。 

【输入输出样例2】 

matches.in 
matches.out 

18 



【输入输出样例2解释】 

9个等式为: 

0+4=4 

0+11=11 

1+10=11 

2+2=4 

2+7=9 

4+0=4 

7+2=9 

10+1=11 

11+0=11 

3. 传纸条 
(wassage.pas/c/cpp) 

【问题描述】 

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。 

在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 

还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用0表示),可以用一个0-100的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。 

【输入】 

输入文件message.in的第一行有2个用空格隔开的整数m和n,表示班里有m行n列(1<=m,n<=50)。 

接下来的m行是一个m*n的矩阵,矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。 

【输出】 

输出文件message.out共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。 

【输入输出样例】 

message.in 
message.out 

3 3 
0 3 9 
2 8 5 
5 7 0 
34 


【限制】 

30%的数据满足:1<=m,n<=10 

100%的数据满足:1<=m,n<=50 

4. 双栈排序 
(twostack.pas/c/cpp) 

【问题描述】 

Tom最近在研究一个有趣的排序问题。如图所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将输入序列升序排序。 

操作a 

如果输入序列不为空,将第一个元素压入栈S1 

操作b 

如果栈S1不为空,将S1栈顶元素弹出至输出序列 

操作c 

如果输入序列不为空,将第一个元素压入栈S2 

操作d 

如果栈S2不为空,将S2栈顶元素弹出至输出序列 

如果一个1~n的排列P可以通过一系列操作使得输出序列为1,2,…,(n-1),n,Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b> 



当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。 

【输入】 

输入文件twostack.in的第一行是一个整数n。 

第二行有n个用空格隔开的正整数,构成一个1~n的排列。 

【输出】 

输出文件twostack.out共一行,如果输入的排列不是“可双栈排序排列”,输出数字0;否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。 

【输入输出样例1】 

twostack.in 
twostack.out 


1 3 2 4 
a b a a b b a b 


【输入输出样例2】 

twostack.in 
twostack.out 


2 3 4 1 



【输入输出样例3】 

twostack.in 
twostack.out 


2 3 1 
a c a b b d 


【限制】 

30%的数据满足: n<=10 

50%的数据满足: n<=50 

100%的数据满足: n<=1000
附件: 您所在的用户组无法下载或查看附件
谁不怀念苏联,谁就没有良心;谁想回到苏联,谁就没有头脑.

Woodu.ME--从零开始的博客生活

TOP

CPP的数组真烦……只能数字做下标……
先给出第一个
复制内容到剪贴板
代码:

#include <iostream>
#include <math.h>
using namespace std;
void sunum(int n){
int k;
for(k=2;k<n;k++){
  if(n%k==0){
    break;
  }
}
  if(k>=n&&(n!=0&&n!=1)){
    cout<<"Lucky Word"<<endl;
    cout<<n<<endl;
  }else{
    cout<<"No Answer"<<endl;
    cout<<0<<endl;
  }
}
int main (int argc, char *argv[])
{
  char word[100];
  int num,i,n;
  static int stat[25];
  cout<<"word.in"<<endl;
  cin.getline(word,100);
  char *wordin=word;
  i=0;
  n=strlen(wordin);
  while(i<n){
    switch(word[i]){
      case 'a':stat[0]+=1;break;
      case 'b':stat[1]+=1;break;
      case 'c':stat[2]++;break;
      case 'd':stat[3]++;break;
      case 'e':stat[4]++;break;
      case 'f':stat[5]++;break;
      case 'g':stat[6]++;break;
      case 'h':stat[7]++;break;
      case 'i':stat[8]++;break;
      case 'j':stat[9]++;break;
      case 'k':stat[10]++;break;
      case 'l':stat[11]++;break;
      case 'm':stat[12]++;break;
      case 'n':stat[13]++;break;
      case 'o':stat[14]++;break;
      case 'p':stat[15]++;break;
      case 'q':stat[16]++;break;
      case 'r':stat[17]++;break;
      case 's':stat[18]++;break;
      case 't':stat[19]++;break;
      case 'u':stat[20]++;break;
      case 'v':stat[21]++;break;
      case 'w':stat[22]++;break;
      case 'x':stat[23]++;break;
      case 'y':stat[24]++;break;
      case 'z':stat[25]++;break;
    }
    i++;
  }
  i=0;
  int max=0,min=100;
  while(i<26){
    if(stat[i]!=0&&stat[i]>max) max=stat[i];
    if(stat[i]!=0&&stat[i]<min) min=stat[i];
    i++;
  }
  system("cls");
  cout<<"word.out"<<endl;
  sunum(max-min);
  
  system("pause");
  return 0;
}

TOP

个人解题报告 第一题主要目的:送分 第二题测试穷举优化能力 第三题双向动态规划 第四题考察指针栈排序
谁不怀念苏联,谁就没有良心;谁想回到苏联,谁就没有头脑.

Woodu.ME--从零开始的博客生活

TOP

个人解题报告 第一题主要目的:送分 第二题测试穷举优化能力 第三题双向动态规划 第四题考察指针栈排序
谁不怀念苏联,谁就没有良心;谁想回到苏联,谁就没有头脑.

Woodu.ME--从零开始的博客生活

TOP

果然第二题只能穷举……我已经想了一个
先穷举1000之内的所偶排列,然后从排列中按需筛选……下周有空就写上
应该不难
第三题略略看了眼……找了点可用规律,总觉得这问题眼熟……W一说是动态规划就更眼熟了
下周一并试试……

TOP

第二题很容易证明最高四位数
两层for解决
谁不怀念苏联,谁就没有良心;谁想回到苏联,谁就没有头脑.

Woodu.ME--从零开始的博客生活

TOP

第二题我是将各个数字要的火柴数做成一个数组,然后证明穷举到711够了(数据输入保证n<=24)

TOP

我考了NOIP,得了200
第一题:90 第二题:100 第三题:0 第四题:10
竟然得了一个一等奖。。。
PS:2楼的方法有点繁琐,直接word-'a'就求出应该在哪个里加了

[ 本帖最后由 lzn3303768 于 2008-11-24 20:25 编辑 ]

TOP

初学,很多函数不详

TOP

第一题youd代码比我校最长的还要长100B左右

今年山东一等奖只有满分的
只要不是400的全部都是二等
谁不怀念苏联,谁就没有良心;谁想回到苏联,谁就没有头脑.

Woodu.ME--从零开始的博客生活

TOP

悲啊。资料太少,练习太少,学习时间也少……慢慢来得了

TOP

做这题好不实用……

TOP

完全不懂……好深奥
中考完毕,暑假开始。

TOP

第三,C/cpp编译标准用的C99,好多新的库函数都不让用
一个字贱
谁不怀念苏联,谁就没有良心;谁想回到苏联,谁就没有头脑.

Woodu.ME--从零开始的博客生活

TOP