首页 > 其他 > 详细

NOIP 2001解题报告

时间:2014-08-15 08:14:07      阅读:211      评论:0      收藏:0      [点我收藏+]

第一题:  有形如:ax3+bx2+cx+d=0  这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d  均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。

解题过程:

直接枚举,把根的范围扩大到100来处理 (精确到小数点后2位 ),水题,15分钟写完AC。如果精确到小数点后6位什么的,就只能二分求解了。。我是把结果和0相差不到0.02的 就当成根,有风险,不过还是AC了。百度了一下有更好的处理方法:
以x作循环变量,从-10000取到10000(因为精确到小数点后两位),此时x1=(x-0.5)/100, x2=(x+0.5)/100(因为x精确到小数占后2位,所以x2,x1取差为0.1); 对于满足x1,x2满足f(x1)*f(x2)<0时,打印x即可;

 

 第二题:  将整数n分成k份,且每份不能为空,任意两种分法不能相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5;1,5,1;5,1,1;问有多少种不同的分法。 

 

  解题过程:

1.首先想到搜索,但对于极限数据n=200,k=6肯定是超时的。

2. 想到用递归求解,f[remain][ma][cnt]表示将数remain划分成不超过ma的cnt份的方案数;  f[remain][ma][cnt] =f[remain-ma][ma][cnt-1](ma单独一份)+f[remain][ma-1][cnt]  (没有ma); 递归边界: A:remain=cnt时 f=1 B:remain<cnt 或者cnt*ma<remain时 f=0 注意A要写在前面,因为remain=cnt=0时 f=1;  不知道会不会有重叠子问题,就加了个记忆化,反正空间不用白不用。极限数据也能秒杀; 递归边界的处理花了点时间,大概30多分钟写完AC;
百度后 发现有更好的方法: f[i][j]表示把i分成j份的方案数,只要二维; f[i][j]=f[i-1][j-1](1这个数单独一份)+f[i-j][j](划分方案中没有1,那就先每一份都分一个1) 拓扑关系明确,直接用递推就行;  

 

第三题:

给出一个长度不超过200的由小写英文字母组成的字母串(约定:该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)。 单词在给出的一个不超过6个单词的字典中。 要求输出最大的个数。    解题过程: 1. 没思路,烦,看到字符串的处理就头大,不想写。。 2. 看到后面那题更麻烦,还是滚回来写这题把。。先预处理了区间[i,j]里有多少个单词(直接暴搜),写了一大堆,然后类似昨天的乘积最大那题,动规方程几乎都一样只是把*改成+; 1个小时左右写完,提交后错了一个点。 错误:输入字符串的时候指针cnt从1开始每次+1,但最后cnt的值并不是字符串的长度,多了1.

 

第四题:

又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第I个城市中高速铁路了的单位里程价格为Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。 任务:

找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。  解题思路: 题目很简单,很裸的求最短路,但是写起来相当麻烦。。 1个多小时才写好,提交错了一个点,相差0.1.蛋疼的精度问题。。vijos上提交AC。 初次总得分:350左右
心得与反思: 1.为啥没考搜索。 2.多组数据的题目一定要注意初始化的问题,自己检验时可以把同一组数据复制几次看结果是否相同。 3.字符串的处理还是有些怕,要勤加练习。 

NOIP 2001解题报告,布布扣,bubuko.com

NOIP 2001解题报告

原文:http://www.cnblogs.com/vb4896/p/3913833.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!