主题

主题

 
   

1202: [HNOI2005]狡猾的商人

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=1202

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


个人解法:

我记得曾经HNSDFZ的NOIP培训中讲过此题。当时那个一脸懵逼啊……

但是现在看来,的确是比较水的题了。毕竟2005年的HNOI,是不是当时是跟着NOI走,狂考并查集呢?

这个写一个带权并查集就可以水了。


代码如下:

https://code.csdn.net/snippets/2199462


遗憾没有进入BZOJ第一页。似乎排在Rank30……

 
 
评论