首页 > 代码库 > 二模09day2解题报告
二模09day2解题报告
T1.domino骨牌
n张有黑有白的骨牌排一排,连续三张同色排一起就不好看,求共多少方案不好看。
分析一下,f[3]=2,f[4]=6,f[n]:如果n-1==n 那么方案数为f[n-2],如果不同,那就f[n-1]。所以f[n]=f[n-1]+f[n-2]但是不规则。然而数据需要高精度,但是不够。所以用一下高端大气上档次的万进制优化就好了。
T2.超车(overtaking)
有n辆车,有不同的position和speed,满足pos[i]<pos[j],speed[i]>speed[j]那就表示一次超车。求总超车数。
本质是逆序对,现根据speed排序,缩小数据(应该不难理解),然后pos从大到小排序,再采用树状数组插入speed,每插入一个前先求speed-1的个数和,再全加起来就好了。
T3.最小奖励(minaw)
有n个村庄,m条有向边,(可能重边),每条边可能有奖励也可能有花费,求1->n的最小奖励(没有奖励就最大花费)。
很神的一道题啊,做法还挺多的。。。
(图转)
可以先拓扑排序,然后按顺序来求。Minaw为最小奖励,只要满足i->j且更新后可以得到奖励就更新。
然后。。。还有spfa做法,没写过先不讲了。
二模09day2解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。