首页 > 代码库 > 二模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解题报告