TCO2016 练习记录

Posted by sjj118 on 2017-01-17

已弃坑

1A EllysTree

Description

给出一棵有根树,每次跳跃可以跳向当前节点的祖先或者是它子树中的节点。要求从根节点开始,经过每个节点一次且仅一次,求字典序最小的路径,或者说路径不存在。

Solution

假如没有字典序最小的限制,我们可以按照这样的策略:每次跳向能跳的节点中深度最大的节点。这个策略保证如果有解,那么这个策略一定能找到解。于是这个策略可以判断是否有解。

事实上,这个策略还能判断一个路径前缀是否有解,比如我们假设第一步跳到节点4,然后再按照这种策略判断是否有解,如果无解代表第一步不能跳到节点4。于是我们可以依次枚举每一位跳到哪个节点,也就是按位贪心就好了。

1B SettingShield

Description

给一个数组a,给出h个区间\([l_i,r_i]\),对于每个区间可以花费p的代价使得a数组中该区间的每个数字减少p,另外还可以花费p*t的代价使整个a数组都减少p,求最小的代价使a数组每一个元素都非正。

Solution

首先假设我们已经确定了整个数组减少x,那么我们考虑怎么最小化剩余的代价。这是一个简单的贪心:首先我们把被其他区间包含的区间都去掉,接下来把所有区间从左到右排序。如果有某一个点的a[i]>x且不被任意区间包含,则无解。接下来从左到右依次考虑每一个区间,找到所有在这个区间内且不在下一个区间内的数中的最大值,把这个区间的数字都剪去最大值。易证这样一定是最小的。

接下来我们就要确定x。我们设g(x)=全局减去x时剩下的最小代价,f(x)=g(x)-g(x+1)。如果f(x)大于t,则说明x+1比x更优。可以证明f(x)是单调不升的(我也不会证,不过感觉是对的。。),于是答案是凸的,可以三分。