NOIP2008提高组复赛题解

NOIP2008提高组复赛题解

NOIP2008提高组复赛题解河南省实验中学 彭勃

NOIP2008提高组复赛题解

第一题 笨小猴

* 题目描述：笨小猴的词汇量很小，所以每次做英语选择题的时 候都很头疼。但是他找到了一种方法，经试验证明，用 这种方法去选择选项的时候选对的几率非常大！ 这种方 法的具体描述如下：假设maxn是单词中出现次数最多的 字母的出现次数，minn是单词中出现次数最少的字母的 出现次数，如果maxn-minn是一个质数，那么笨小猴就认 为这是个Lucky Word,这样的单词很可能就是正确的答 案。

NOIP2008提高组复赛题解

输入格式：输入文件word.in只有一行，是一个单词，其中只可 能出现小写字母，并且长度小于100。 * 输出格式： 输出文件word.out共两行，第一行是一个字符串， 假设输入的的单词是Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”; 第二行是一个整数， 如果输入单词是Lucky Word,输出maxn-minn的值，否则 输出0。

NOIP2008提高组复赛题解

样例1 输入： error 输出： Lucky Word 2 解释： 单词error中出现最多的字母r出现了3次，出现 次数最少的字母出现了1次，3-1=2,2是质数。

NOIP2008提高组复赛题解

样例2 输入： olymipic 输出： No Answer 0 解释： 单词olympic中出现最多的字母i出现了2次，出现次 数最少的字母出现了1次，2-1=1,1不是质数。

NOIP2008提高组复赛题解

思路：统计单词中每个字母的出现次数，挑出最多的次数和 最少的次数(不包括0次),相减判断是否为质数即可。 判断质数时可以写函数判断，也可以把100以内的质数 列成常量数组直接判断，因为单词最多只有100个字母。 需要注意的是输出时的LWNA四个字母要大写。 * 总结： 这是一道送分题，没有什么难度，需要注意的细节也 不多，所以在比赛中是一定要拿满分的。

NOIP2008提高组复赛题解

参考样程#include <fstream> #include <string> #include <cmath> #define I_F "word.in" #define O_F "word.out" using namespace std; string s; short ans; void Input(); void Search(); bool Pd(); void Output(); int main() { Input(); Search(); Output(); return 0; } void Input() { ifstream fin(I_F); fin>>s; fin.close(); } void Search() //统计字母出现次数 { short i, max=0, min=200; short f[26]={0}; for (i=0; i<s.length(); f[s[i++]-'a']++); for (i=0; i<26; i++) if (f[i]>0) { if (f[i]>max) max=f[i]; if (f[i]<min) min=f[i]; } ans=max-min; } bool Pd() //判断质数 { if (ans==1) return false; else if (ans==2) return true; else if (ans%2==0) return false; else for (short i=3; i<=sqrt((dou ble)ans); i+=2) if (ans%i==0) return false; return true; }

void Output() { ofstream fout(O_F); if (Pd()) fout<<"Lucky Word\n"<<ans<<endl; else fout<<"No Answer\n0\n"; fout.close(); }

NOIP2008提高组复赛题解

第二题 火柴棒等式 问题描述： 给你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根火柴棍必须全部用上

NOIP2008提高组复赛题解

输入格式： 输入文件matches.in共一行，有一个整数n(n<=24)。 * 输出格式： 输出文件matches.out共一行，表示能拼成的不同等 式的数目。

NOIP2008提高组复赛题解

样例1 输入：14 输出： 2 解释： 2个等式为0+1=1和1+0=1。

NOIP2008提高组复赛题解

样例2 输入： 18 输出： 9 解释： 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

NOIP2008提高组复赛题解

思路： 枚举两加数，计算所需火柴棒是否等于n。枚举 范围0~1000。 总结： 这也是比较水的一道题，数据规模较小，算法 简单，比赛中这样的题也应该拿到满分。

NOIP2008提高组复赛题解

参考样程#include <fstream> #define I_F "matches.in" #define O_F "matches.out" #define MAX 1000 using namespace std; const short match[10]={6,2,5,5,4,5, 6,3,7,6}; //10个数字所需火柴棒 long ans; short n; void Input(); int Matches(int x); void Search(); void Output(); int main() { Input(); Search(); Output(); } void Input() { ifstream fin(I_F); fin>>n; fin.close(); } int Matches(int x) //计算摆出x所需的火柴棒 { int t=x,s=0; if (x==0) return 6; else while (t>0) { s+=match[t%10]; t/=10; } return s; } void Search() { int i,j; n-=4; for (i=0; i<MAX; i++) for (j=0; j<=i; j++) //这样对于A+B和B+A就只 会搜索到一次，可以节约一半时间 if (Matches(i)+Matches(j)+Matches(i+j)==n) { if (i!=j) ans+=2; else ans++; } } //Output函数略

NOIP2008提高组复赛题解

第三题 传纸条 问题描述： 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完 的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的 矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就 无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。 纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐 标(1,1),小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的 纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向 …… 此处隐藏：3775字，全部文档内容请下载后查看。喜欢就下载吧 ……