Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
两种主流做法 贪心+BIT or 差分约束系统 类似1201题目1. 贪心 + BIT(线段树) 将区间按右端从小到大排列,每次尽量取右边(这样下一个区间少取的可能性更大) ,每次从区间[a,b]中两个,需要判断区间[a,b]之前已经取了多少(判断用区间前缀和,树状数组sum(b)-sum(a-1)或者线段树都行),如果还需要取,从右边开始,逐个逐个单点区间查询sum(j)-sum(j-1)看能不能取,最后记录结果输出 2. 差分约束系统 同样是区间前缀和sum[i]代表0~i的取点数 满足 sum[i+1] - sum[i] >= 0 s[i+1] - s[i] <= 1 sum[b] - sum[a-1] >= 2 差分约束系统最常见的是最短路模型 有d[e.to] <= d[e.from] + cost[e.from][e.to] 于是上面转化为 sum[i+1] + 0 >= sum[i] s[i+1] <= 1 + s[i] sum[b] - 2 >= sum[a-1] 依据最短路模型建图,问题转化为求带负权的最短路问题 使用Bellman 或者 SPFA 最终整个区间的去点数就是最短路求出来的从最小区间左端--->d[MAX]的值 效率上 BIT 16ms 差分约束据说是 300MS Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator