题面 一开始想到一个错误策略: 每次在当前油量能走到的范围内找油最多的加油站...后面发现有可能会要在范围内多次加油才可能走到终点, 需要根据油量从大到小依次选择加油站, 于是容易想到用一个大根堆来维护所有可以走到的油站, 直到不能再走就不断依次选择油站来继续往前走. 如果没有油站可以选就走不到终点. 注意输入的是到终点的距离. [collapse…

题面 首先面值大于$ C$的硬币肯定只能直接计入答案. 剩下的硬币肯定要凑出尽可能接近$ C$的面值, 策略是在面值不超过$ C$的前提下优先使用大面值, 因为这样可以在使现在和将来避免浪费钱的前提下凑近$ C$. 如果不能恰好凑出$ C$而剩余$ x$必须浪费钱时, 就可以优先用小面值补全$ x$, 来使浪费最小化. [collapse titl…

题面 题意: 要用尽量少的6*6的箱子放入一些1*1~6*6的物品, 设他们分别有$ a_i$个. 首先答案至少要$ a_6+a_5+a_4$这么多, 因为他们是不能多个并存的. 然后对于5*5和4*4的物品我们就可以贪心地在空隙中插入物品. 对于放了5*5的箱子每个可以插11个1*1. 对于放了4*4的箱子每个可以放5个3*3和7个1*1, 如果…

题面 感觉这题最水... 显然$ a$越低就越难赢, 而只要每次比赛$ a$之差都在$ k$内就可以赢. 所以每个人都要尽量和第一个$ a$比它大的人比, 如果在n-1场比赛中有一场$ a$的差值大于$ k$就不行, 而且所有比它$ a$小的都不行了(因为都要和它比$ a$还比它小). 于是可以升序排序然后从后往前统计答案. [collapse t…

这篇文章受密码保护，输入密码才能阅读

这篇文章受密码保护，输入密码才能阅读

题面 贪心策略: 按照每个大臣左右手的乘积升序排列为最优解. 这可以采用临项交换的方法证明, 常见于涉及以某关键字排序的贪心策略.设第$ i$个人左手为L[i], 右手为R[i], 国王为第0个人, 则: 考虑对一对临项$ i$, $ i+1$顺序的决策. 交换顺序前$ coin[i]=\prod_{j=0}^{i-1} L[j] \div R[i…

题面 首先这道题容易想到降维, 一个点P(x, y)能够被圆心O在X轴上的一个圆覆盖, 等价于O在线段[$ x-\sqrt{r^2-y^2}$, $ x+\sqrt{r^2-y^2}$]上. 这样就转化为要用最少的点标记所有的区间. 考虑贪心, 根据之前类似区间问题[POJ3190]Stall Reservations[贪心]和[POJ3614]S…

题面 第一反应断环为链, 转化为均分纸牌, 但复杂度为$ O(N^2)$根本不对. 实际上这道题比均分纸牌只多了1与n之间的转移, 设 n给1 $ x_n$个糖果, i给i+1 $ x_i$个糖果, 则有: $$\left\{ \begin{array}{ll} a_1+x_n-x_1=av \\ a_2+x_1-x_2=av \\ a_i+x_{…

题面 首先要把牛按照开始时间升序排序, 不然安排一头牛时这头牛开始时间之前我们都管不了了, 可能造成浪费一段正好可以安排后面一头开始时间更早的牛的空档. 而按开始时间排序后就能线性的安排每头牛, 保证安排到每一头牛时这头牛的开始时间之前已经排满, 只要考虑这头牛结束后的安排. 事实上许多含上界下界的问题都不能同时考虑上下界, 必须先保证一端线性变化…