模拟DAY5

模拟DAY5

题目:noin2017模拟测试(day1).pdf
密码:233

T1题解:
长久以来少有的一眼秒的题啊!简单的递推
dp[i][j]表示i长度的基因第i位放j的方案数
显然:
dp[i][0]=dp[i-1][0]+dp[i-1][1];
dp[i][1]=dp[i-1][0];
那么就AC了呗!
//吐槽电脑慢……,std啥的也都被卡……,虽然最后都是AC

AC代码:

T2题解:
题面很长,但是题并不难……虽然……
对于我们现在所在的鱼,我们要找到他往下走要最优的点,那么什么是最优的点?
考试的时候我想的是他能到的点中度最大的,然而事实不是这样的,eg:

如果右面是一条链,那么显然我应该先走右边……所以不能用度啊!gg哦
那是什么?
应该是找到花费时间最长的内个点先走,既然我们在dfs,那么我们就这样找他的所有儿子要花费的时间return上来,然后放在一个数组里
在这个数组里,我们要更新的所在的点的时间就是sort后的a[i]+i+1(如果从0开始存),为啥加i+1呢,因为我要一个一个通知,所以其他的点会有延时
所以dfs就可以解决这道题了啊!
//正解的名字好像是树形dp,据说实际上是一样的……

AC代码:

T3题解:
一道很迷的题,第一个想法就是写一个spfa按速度最优跑一跑,事实上是可以做出样例的(讲个笑话)
然而物理学的好的人(不是我)就会发现按速度判断是不对的,所以我们要做一些变化……
对于一个我们做出来的ans的话,如果要更新它,那么我们一定要满足条件:
(P1+P2+……+Pk)/(T1+T2+……+Tk)>Ans
对这个式子进行变化,移项,就得到了:
P1–T1Ans+P2–T2Ans+……+Pk–TkAns>0
所以我们二分答案,然后check()
怎么check?
我们用一个数组记录P-T
Ans,把他当做边权跑spfa,如果我们正权到了n,也就是最后答案大于0,那么显然是满足条件的
但是我们做过样例的人都会发现,这个人会绕着圈跑啊跑啊跑啊跑,只为了有最大速度……(chun)
所以遇到环怎么办,不就TLE了吗!
这时候我们就想起了spfa的特性,可以判环,简单的来说,如果一个点入队列太多次,那么它一定在环上,所以在这个式子中,如果遇到了正权的环,那么这个式子最后一定满足>0,所以直接return 1即可
//听说如果学过01分数规划,会很简单?
//为什么会想到二份答案呢?

AC代码:

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注