当前位置:首页 >> 学科竞赛 >> NOIP 2006年普及组解题报告

NOIP 2006年普及组解题报告


NOIP 2006 年普及组解题报告
北京市八一中学 王祺磊 2006 年,普及组的题目出的略显简单,和提高组题目形成鲜明对比。但是,题目考察 面全面而有效,李老师的程序功底可见一斑。 题目上来说,主要考察了几个方面:模拟(主要是一一对应的哈希表使用) ,动态规划 (继续了 2005 年的背包问题) ,字符串操作(规则简单,难度不深) ,取值规律(简化了的 2 进制全模

拟取舍) 。其实说简单,主要因为 2005 年普及组的采药刚刚出了 01 背包,在本 年中又出了一道,让人突出的感觉到了 01 背包的重要,也为信息学的动态规划时代,拉开 了序幕。从 2006 年起,动态规划就成了信息学教学的重中之重。而最后一题的规律过于简 单,而且,去掉了,生成所有情况的较复杂部分,只保留了 2 进制转换后的部分。考察点显 得有些过于直白了。 下面,我们来分别看一看各个题目。 一、明明的随机数 在这道题中,再次考察了 2005 年中校门外的树的一一对应的哈希表的知识点,当然, 对待数的排序来说,更是简化了的“箱排序”思想。用至少有 1000 个数组元素的数组,用 位置和数值,一一对应。用位置代替数值。每得到一个数值就在数组的相应位置上做一个标 记或者做加。这样,从头到尾统计一下数值非零的位置就知道有多少个不相同的数字了。可 以然后再记录下来这些数字,从头到尾输出即可。当然,本题因为是要输出个数,并且个数 要求在前,所以需要从头儿到尾统计一下个数。 参考程序: #include <cstdlib> #include <iostream> using namespace std; int s[1001] , x[1001]; int main(int argc, char *argv[]) { int i, t, n; cin >> n; while (n--) { cin >> t; s[t]++; } for ( t = 0 , i = 0 ; i <= 1000 ; i++ ) if (s[i]) x[t++] = i; cout << t << endl; cout << x[0]; for ( i = 1 ; i < t ; i++ ) cout << " " << x[i];

cout << endl; //system("PAUSE"); return EXIT_SUCCESS; } 二、开心的金明 在 2005 年,大家熟悉了“采药”后,应该说这道题,是一道送分题目。分析也很简单, 用消耗的 N 元钱,来换价值和重要度的乘积。而结构上,属于明显的 01 背包问题。 参考程序如下: #include <cstdlib> #include <iostream> using namespace std; int s[30001]; int main(int argc, char *argv[]) { int i, j, n, m, v, w; cin >> n >> m; for ( i = 0 ; i < m ; i++ ) { cin >> v >> w; for ( j = n ; j >= v ; j-- ) if (s[j - v] + v * w > s[j] ) s[j] = s[j - v] + v * w; } cout << s[n] << endl; //system("PAUSE"); return EXIT_SUCCESS; } 三、Jam 的计数法 这道题在整套题中,属于最难的一题了。也是一道单纯的字符串题目。这道题,一般 会给人一种错觉,好似是回溯的题目去查找,但如果仔细分析,其实题目非常简单。就是要 从后面查找可以改变的位置。如果没有可以改变的了,就代表后面没有数字了。如果有可以 改变的, 则这个字母可以做加 1 的操作, 而这个可以改变的位置后面的所有字母均需要变的 跟改变的字母连续变化即可。只要把握好这两点,题目可以非常简单的解决。 参考程序如下: #include <cstdlib> #include <iostream> using namespace std; char z[28] = "0abcdefghijklmnopqrstuvwxyz"; int s, t, w; void pre(char *st) { char c;

int i, j, x; bool f; f = true; for (i = w - 1; i >= 0 ; i-- ) if (st[i] != z[t - (w - 1) + i]) { f = false; break; } if ( f ) return; i= 0; while (st[w - i - 1] == z[t - i]) i++; st[w - i - 1]++; c = st[w - i - 1]; for (x = 1 , j = w - i ; j < w ; j++ , x++) st[j] = c + x; } int main(int argc, char *argv[]) { char st[28] , *str; char str1[28]; int i, j, k; cin >> s >> t >> w; cin >> st; str = st; for ( i = 0 ; i < 5 ; i++ ) { strcpy(str1 , str); pre(str); if ( strcmp(str1 , str) != 0) cout << str << endl; else break; } //system("PAUSE"); return EXIT_SUCCESS; } 四、数列 没有想到最后一道题会这么简单,看到题目以后,看到数列首先有些困惑,但是,括 号里的内容,却让思路豁然开朗。这个表达式,明显的表现出了,加法算式的部分选择,这 种情况很正常的想到了 2 进制的 01 转化后和加法算式部分的乘积后的结果。而且,仔细观 察在这道题目中,我们甚至不用生成 2 进制的 01 形式,只需要将 N 转化成为 2 进制就可以 了。可以说,真的是不能够再简单了。

参考程序如下: #include <cstdlib> #include <iostream> using namespace std; int s[33]; int kf(int k, int x) { int i, s; s = 1; for ( i = 0 ; i < x ; i++ ) s *= k; return s; } int main(int argc, char *argv[]) { int k, n, i, w; int t; cin >> k >> n; w = 0; while ( n != 0 ) { s[w] = n % 2; n /= 2; w++; } /* for ( i = 0 ; i < w ; i++ ) cout << s[i]; cout << endl; */ t = 0; for ( i = 0 ; i < w ; i++ ) { t = t + s[i] * kf(k , i); } cout << t << endl; //system("PAUSE"); return EXIT_SUCCESS; } 注 : 本 份 解 题 报 告 的 参 考 答 案 均 采 用 G++ 编 译 器 通 过 , 并 已 经 在 http://judge.ybdevelop.cn/JudgeOnline中测试通过,欢迎大家在在线测评中提交检测,如遇到

问题可到:北京市科协网站的在线交流(http://www.student.gov.cn/bjnoi/)或到作者的交流 论坛http://www.ybdevelop.cn的相应板块中提交。输入输出形式,采用的均为标准输入输出, 如果需要针对竞赛,请更改为相应的文件操作即可。


更多相关文档:

(一)第八届Noip2006普及组解题报告

noip2006 普及组noip2006 普及组隐藏>> 第八届 Noip2006 普及组解题报告 第一题: program c1; var K: Byte; n: Longint; Sn: Extended; begin Readln(K)...

NOIP2006普及组复赛试题(附题解)

NOIP2006普及组复赛试题(附题解)_其它考试_资格考试/认证_教育专区。NOIP2006普及组复赛试题(附题解)NOIP2006 普及组解题报告 NOIP2006普及组解题报告 NOIP2006普及...

2008年NOIP普及组解题报告

2008 年 NOIP 普及组解题报告 王祺磊 (本份解题报告以 C++为参考程序) 一、ISBN 号码 一道让人很长知识的题目,但是题目所蕴含的解题方法,却十分直接。你甚至可...

noip2005普及组解题报告

noip2005普及组解题报告_建筑/土木_工程科技_专业资料。noip2005普及组解题报告noip2005 普及组解题报告 陶陶摘苹果 【文件名】: apple.pas/c/cpp 【问题描述】 ...

NOIP2015普及组解题报告

NOIP2015普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2015解题报告,by贴吧id u007zzt 的某蒟蒻 NOIP2015 普及组解题报告 From 贴吧 id u007zzt 金币 国王将...

NOIP2006普及组初赛试题及答案

NOIP2006普及组初赛试题及答案_电力/水利_工程科技_专业资料。NOIP2006普及组第...NOIP1997普及组复赛试题 NOIP1997普及组解题报告 NOIP1997普及组初赛试题1...

NOIP2010普及组解题报告

NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书。NOIP2010 普及组解题报告时间:2011-09-14 10:39:27 来源:网络 作者:网络 首先前两题可以说非常水,第三...

NOIP普及组解题报告

NOIP普及组解题报告_学科竞赛_高中教育_教育专区。NOIP2006 复赛普及组解题报告 【第一题解题思想】 :这道题属于容易题,但是题目难度大于 NOIP2005 和 2004 普及组...

NOIP2011普及组解题报告

NOIP2011普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2011 普及组解题报告一、数字反转 没得满分只能说明一个问题,你的程序写的太少了。 program reverse; ...

NOIP2006提高组复赛命题与解题报告

NOIP2006提高组复赛命题与解题报告_经济学_高等教育_教育专区。NOIP2006提高组复赛...【算法说明】 此题是在 01 背包问题的基础上改编的,但比普及组类似的一道题...
更多相关标签:
noip2006普及组复赛 | noip2006普及组初赛 | noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | noip2016复赛解题报告 | noip2014解题报告 | noip2015复赛解题报告 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com