Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

两种主流做法 贪心+BIT or 差分约束系统 类似1201题目

Posted by 947186602 at 2020-09-09 17:18:20 on Problem 1716
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator