当前位置:首页 > 差分约束 > 正文
BZOJ1202[HNOI2005]狡猾的商人
2074+

题目大意:判断一个账本是不是假的,只需要看里面的记录有没有冲突,现有m条表示某段时间收入情况的记录,请判断账本真假。

Description

刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了n个月以来的收入情况,其中第i 个月的收入额为Ai(i=1,2,3…n-1,n), 。当 Ai大于0时表示这个月盈利Ai 元,当 Ai小于0时表示这个月亏损Ai 元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。 刁姹的任务是秘密进行的,为了调查商人的账本,她只好跑到商人那里打工。她趁商人不在时去偷看账本,可是她无法将账本偷出来,每次偷看账本时她都只能看某段时间内账本上记录的收入情况,并且她只能记住这段时间内的总收入。 现在,刁姹总共偷看了m次账本,当然也就记住了m段时间内的总收入,你的任务是根据记住的这些信息来判断账本是不是假的。

Input

第一行为一个正整数w,其中w < 100,表示有w组数据,即w个账本,需要你判断。每组数据的第一行为两个正整数n和m,其中n < 100,m < 1000,分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。接下来的m行表示刁姹偷看m次账本后记住的m条信息,每条信息占一行,有三个整数s,t和v,表示从第s个月到第t个月(包含第t个月)的总收入为v,这里假设s总是小于等于t。

Output

包含w行,每行是true或false,其中第i行为true当且仅当第i组数据,即第i个账本不是假的;第i行为false当且仅当第i组数据,即第i个账本是假的。

Sample Input

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

Sample Output

true
false

解题思路

如果m条记录中有冲突,说明账本是假的,否则是真的。如[a,b]收入为x,[b+1,c]收入为y,那么[a,c]收入一定是x+y,如果出现[a,c]收入为z且z!=x+y,那么账本就是假的。判断这些条件是否冲突,方法有很多种,如差分约束系统、带权并查集、贪心等。

程序实现

差分约束:对于[a,b]收入为c,说明的是b时刻比a-1时刻多了c,如果f数组表示收入,那么f[b] = f[a-1] + c,这个等式可以转化成两个差分约束的式子:f[b] >= f[a-1] + c以及f[b] <= f[a-1] + c,后者可以写成f[a-1] >= f[b] – c,这相当于点a-1向点b连一条长c的边,点b向点a-1连一条-c的边。将所有点入队求最长路即可,因为f[b]越长越满足条件,只要找到满足条件的就说明是真的;如果出现正环死循环,那么说明是假的。(当然,代码31行改成<求最短路也是可以的,这个图是对称的,有正环就一定有负环。)

带权并查集:[a,b]收入为x,那么b比a-1多x,如果下次知道a-1和b的差,比较一下就可以判断真假;如果再知道[b+1,c]收入为y,那么就知道b和c的差,此时a-1、b和c任意两点之间的差都可以计算出来。任意两点的差都知道的话,就用并查集合并,选右端点做公共祖先。f数组记录祖先,d数组记录节点到祖先的距离。

第一次合并:[a,b]收入为x,那么f[a-1] = b,d[a-1] = x。

第二次合并:[b+1,c]收入为y,那么f[b] = c, d[b] = y,压缩路径后,f[a] = c,d[a] = x + y。

后面的合并,情况类似于a___fa___b___fb,a到fb的距离,在a到fa的距离基础上,加上fa到fb的距离;fa到fb的距离,就是a到b的距离加上b到fb的距离减去a到fa的距离。其他情况也能得出同样的公式,如果祖先点不在最右边,会出现负数抵消。

贪心:每一个区间看成一根线段,用完就删掉。按照左端点排序,左端点相同按照右端点排序。依次取出最小的两根线段,如果左端点不相同,那么最小的那根就没有意义了,因为前面那一小段时间的收入可以是任意的;如果左端点相同,右端点也相同,那么是重复的,如果收入不同就不行,说明账本是假的;如果仅是右端点不同,那么可以得出右边一小段的值是多少,然后最小那根线段就没有利用价值了,因为第二小和右边那一段能够得出他的信息。

BZOJ1202[HNOI2005]狡猾的商人:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!