2017杭电ACM集训队单人排位赛 - 6

acm 2017年7月 hdu 个人训练

入口：2017杭电ACM集训队单人排位赛 - 6

1000. 合理的电梯

比较一下走楼梯和走电梯花费的时间大小即可

1001. bx和妹子的游戏

假设u和v的LCA为p, 则$s(u,p)=s(u,1)-s(p,1)+a[p]$
因此可以预处理出1到所有点的路径值，排个序，那么所有$s(u,1)*cnt[u]$值之和，即是第一部分的值，其中$cnt[u]=1+(n-i)*2$。
考虑第二部分的值，处理出每个点的每个分支的节点数，那么$cnt2[u]=\sum_{v为u的子节点} sz[v]*sz[v]$

1003. bx回文

dp[i]：表示1~i位可以获得的最大的愉悦值

转移：$dp_i=max(dp_j + a[i - j + 1])，若str[j...i]是回文串$

1004. 电影票

注意读题！！！

1007. bx值

考虑每个数的贡献，举个栗子：

考虑数字1，它在任何不含数字2的子串中都有贡献，因此1的贡献为：$含有数字1的子串个数-含有数字12的子串个数$

其他数字也同理。

1008. 对抗女巫的魔法碎片

题意有点问题。

最终求的是在占领村庄数尽可能多的情况下，获得魔法碎片的最大值。

因此可以把村庄按c-b从大到小排序，用set维护a。

对于每一个村庄，在set中二分出恰好大于其防御值b的a，重复操作，可以得到最后可占领的村庄数。

最后根据可占领的村庄数，每次用尽可能大的a去匹配即可。

1009. 小P玩游戏2

首先明确一点，最多只能有1个人杀了大于1只怪。

把所有人按从0只怪到1只怪的收益，即a+b-c排序，这样，对于每个b，二分出大于当前b的a+b-c的位置，那么从这个位置开始给予一个怪都能更优。枚举每个b，取最大值即可。