首页 > 代码库 > 2016HDU校赛

2016HDU校赛

A: 真正的粉丝,就算不写题解也知道怎么做

B: 最基础的数位dp

C: 贪心

  易得要洗衣服的地位比要脱干衣服的地位高,于是先尽可能的按10件洗衣服,最后剩下要洗的衣服数量就是0~9。

  再分成0~3,4~6,7~9三种情况

    0~3:这时候用要脱干的衣服来补,分别补成3、6、10,分别计算代价取最小

    4~6:这时候易得如果用一个3件衣服方案加上另一个方案肯定没单独一个方案优,所以这是只有补成6,10两种情况,分别计算代价取最小

    7~9:同理,只存在一种情况补成10

  再考虑补完后仍需要脱干的衣服,如果数量>0说明有剩余,那么就按照唯一一种脱干方式脱干。

D: dp

  先对Fire和Ice做背包,得出f[2][j],表示这两种物品花费水晶为j得到的最大伤害

  对于Dog和Evolved,注意到水晶数和伤害数的比值都是2,同样也是dp一下得出g[0..10],g[i]表示这两种卡牌的组合能否表示水晶数量为i

  然后就可以枚举在buff卡牌上花费的水晶数i,在Fire和Ice上花费的水晶数就是10-i,得到此时的最大伤害

  最大伤害和m比较就行

E: bfs

  bfs枚举走向,注意统计答案时候要将每个中间状态的数值都统计到答案中(和答案矩阵做或运算)

F: MST+倍增

  裸到不能再裸,先MST,再树上倍增,注意边权下放到点权

G: QvQ

H: 注意结果输出整数,计算下整数最多到6w多,所以可以枚举每个整数进行判定是否相遇

  也可以写出有关t或者s的方程,三分求解(sin函数与直线的交点问题),但精度不知道能不能保证

2016HDU校赛