2015.12.19初二、三提高组模拟赛 总结

最近埋在题海里,没怎么写blog,来写一篇吧。
这次比赛共3题,3小时40分钟。时间还是蛮够的,可是还是没有利用好。

比赛回顾

8:00 这次的题好像有点水诶。

题目描述

P1 团队背包

DaA 和他的朋友组成一个团队去旅行了。他们每个人都准备了一个背包,用来装旅行用的物品。他们的背包有两个特点:
1. 每个人的背包能装无限多的物品,每种物品有一个价值,但只能装一件;
2. 每个人都很有个性,所以每个人的背包不会完全相同。
DaA 的团队中有M 个人,那么对于整个团队,背包价值和最大是多少呢?

P2 弹性小球

DaA 有一个弹性小球,小球有一个能量值E。
DaA 走进一个M*N 房间,房间有M 行N 列。
一开始在左上角,以向右下角45°的方向弹射小球。小球有两个性质:
1. 小球在运动过程中不会损失能量,只有在碰壁或碰角的时候才会损失能量,能量<=0 了小球就停止运动了;
2. 小球弹射遵循反射定律,小球碰角会原路返回(请参照下边图画)。
请聪明的你告诉DaA 弹性小球在这个房间中的运动轨迹。
2015.12.19初二、三提高组模拟赛 总结_第1张图片

P3 神奇的项链

从前有一条神奇的项链,为什么说它神奇呢?因为它有两个性质:
1. 神奇的项链可以拉成一条线,线上依次是N 个珠子,每个珠子有一个能量值Ei;
2. 除了第一个和最后一个珠子,其他珠子都满足Ei=(Ei-1+Ei+1)/2+Di。
由于这条项链很长,我们只能知道其两端珠子的能量值(即E1&En)。并且我们知道每个珠子的Di是多少。请聪明的你求出这N 个珠子的能量值分别是多少。

思考过程

第一题,呵呵,水背包?第二题,呵呵,纯模拟?第三题,呵呵,推公式?
66666666666666666666666~
咦,第一题有坑!(吓)
先着手研究第三题。
首先有个显然的性质:求出E2,就能将整个序列求出。
这时E[i]=2*(E[i-1]-D[i-1])-E[i-2]
循环i,通过观察这个式子,我们发现可以不停地将已求出的E[i-1]和E[i-2]代入式子,最后得出一个用E[1]、E[2]表示E[n]的式子。由于E[1]、E[n]是已知的,所以该式就是关于E[2]的一元一次方程,直接求解,再推出E[3],E[4]…….E[n-1]即可。(注意开longlong)
第二题没啥好说的,直接模拟(pass)
几个小优化:当球碰到角的时候直接退出;当球弹的轨道重合时直接退出。
一个小细节:若要将’\’赋值给字符,应打成ch=’\\’;而不是ch=’\’;
最后第一题忘记了读题时的想法了(我是DOBY),然后没想出来(QAQ)。

程序实现

第三题很顺利地打了出来,调过样例后开long long,make了一个极限数据,好像没什么问题。对拍不好打,而且我认为这个程序的正确性无需验证。
第二题,实现还是很恶心的。写了近半个钟。调过样例,又make了一个极限数据,秒过,时间上是不成问题的。打开宏大壮丽的输出文件,猛然发现球弹到右边框时轨迹向上偏了一格。好险。
第一题没打完暴力,很可惜少了30分。
最后估分0+100+100=200.
实际得分0+100+100=200.
虽然分数还可以更美观,但是还好,至少正常发挥了,这次比赛还算满意。
第一题解法:
用 f[i]表示价值为 i 的背包的不同种数,可以用 DP 求出:
f[i]=∑f[i-w[j]]
其实就是01背包。然后从大到小枚举f[i],统计答案f[i]*i即可。

你可能感兴趣的