CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
=====A - Multiples of Length=====

====题意====

给定一个长度为n的序列。一次操作要选中一个区间，将这个区间里的每个数加上区间长度的整数倍。构造一个三次操作将序列全变为0的方案。

====限制====

$1\le n \le 10^5$

====题解====

第一次操作选第一个数，加$-a_1$，第二次选[2,n]，加$(n-1)a_i$，这时保证每个数都是n的倍数。第三次选[1,n]。

=====B - Stoned Game=====

====题意====

n堆石子，两人轮流取，每次取一个，但不能从上一个人选的那堆中取石子。问谁赢。

====限制====

$1\le n \le 100,1\le a_i \le 100$

====题解====

若存在一堆石子大于其余所有石子之和，则先手胜。否则石子总数之和为奇数则先手胜，为偶数则后手胜。

=====C - Rainbow Rectangles=====

====题意====

n层塔，每层有$a_i$个小怪和一个大怪。小怪有一滴血，大怪两滴血。在一层有三种操作。第一是$r_1$的代价打一个怪1滴血，第二是$r_2$的代价打所有怪1滴血，第三是$r_3$秒杀一个怪。上一层或下一层需要花费d。如果对大怪造成了伤害却没有杀死大怪，则强制立即上一层或下一层（需要花费d）。一开始在第一层。问杀死所有怪的最小花费。

====限制====

$1\le n \le 10^6$,$1\le r_1 \le r_2 \le r_3$

====题解====

最优策略下，不会连续下两层（因为上二下二上二和上一下一上二下一上一是一样的）。因此可以用dp1[i]表示第i层怪全部杀死，当前在第i+1层的最小花费，dp2[i]表示第i层还剩一滴血大怪，当前在第i+1层的最小花费。转移比较复杂，但不是很难推。注意只推到dp[n-1]，最后一层和之前情况不太一样。
CVBB ACM Team

用户工具

站点工具

页面工具
