codechef January Lunchtime 2017简要题解

题目地址https://www.codechef.com/LTIME44

Nothing in Common

签到题,随便写个求暴力交集就行了

Sealing up

完全背包算出得到长度≥x的最小花费,然后对每条边的长度向上取整分别算一下。本来也是签到题的结果我调了1h+。。

Segment Queries

定义连续段为被激活的极长子串,一条线段被激活当且仅当它的两个端点在同一个连续段,用set和并查集维护连续段内的询问,修改时当前点成为新的连续段,并和两侧连续段(如果有)启发式合并一下,O(nlog2(n))勉强卡了过去

Improve the Permutation

贪心从大到小把数移到对应位置,但在向右移的过程中如果一个操作将使另一个数也归位但它右边还有更小的数被卡住,就要进行调整,先把那个数移到左边再操作

例如:2563417,当前操作6,但若右移会使1不能回到左边,所以先操作2563147 2561347 然后再变为2516347 2513647 2513467

每个数只会被左移不超过n次,右移不超过n次,因此总次数符合要求

原文地址:https://www.cnblogs.com/ccz181078/p/6356614.html