1202: [HNOI2005]狡猾的商人

1202: [HNOI2005]狡猾的商人

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1554  Solved: 745

[Submit][Status]

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

HINT

Source

 题解:这个题乍一看我直接蒙了,完全没辙。直到我看了下题解,结果居然是个前缀和+并查集——细细想来,这道题出现冲突的前提必然是对于同一个区间(无论是直接给的还是间接推出来的),出现了两个不同的区间和。于是假如把每个月看成图的一个点,则意味着这张图里面两个点之间的所有路径均必须相等,则并查集这时候就会被用于找环啦——其实只要在并查集基本的getfat(找父亲点,详见百度百科——并查集)里面再加入一些维护操作即可,这样子前缀和以及重复边的相容性判断就手到擒来啦*^_^*么么哒(HansBug:多多卖萌有利于身心健康么么哒~ phile:。。。。。。)

 1 var
 2    i,j,k,l,m,n,x,y,z,vx,vi:longint;
 3    c,a:array[0..10000] of longint;
 4    flag:boolean;
 5 function getfat(k:longint):longint;
 6          var a1:longint;
 7          begin
 8               if k=c[k] then exit(k);
 9               a1:=getfat(c[k]);
10               inc(a[k],a[c[k]]);
11               c[k]:=a1;
12               exit(c[k]);
13          end;
14 procedure doit(x,y,z:longint);
15           var a1,a2,a3,a4,a5,a6:longint;
16           begin
17                a1:=getfat(x);a2:=getfat(y);
18                a3:=a[x];a4:=a[y];
19                if a1<>a2 then
20                   begin
21                        c[a1]:=a2;
22                        a[a1]:=a4-a3-z;
23                   end
24                else if (a4-a3)<>z then flag:=false;
25           end;
26 begin
27      readln(vx);
28      for vi:=1 to vx do
29          begin
30 
31      fillchar(c,sizeof(c),0);
32      fillchar(a,sizeof(a),0);
33      readln(n,m);
34      for i:=0 to n do c[i]:=i;
35      flag:=true;
36      for i:=1 to m do
37          begin
38               readln(x,y,z);
39               doit(x-1,y,z);
40          end;
41      if flag then writeln('true') else writeln('false');
42 
43          end;
44 end.
45                

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

漏洞预警 | SMT智能合约整型溢出漏洞

SmartMesh Token是基于Ethereum的合约代币,简称SMT。Ethereum是一个开源的、公共的分布式计算平台,SmartMesh代币合约Sma...

793
来自专栏企鹅号快讯

以德加密货币交易所DNS遭黑客劫持 损失超26.6万美元

以德(EtherDelta)是用于以太坊(Ethereum)与ERC20兼容代币(已经部署在Ethereum区块链上的代币)之间进行交易的加密货币交易所。它并不...

2289
来自专栏数据结构与算法

BZOJ1202: [HNOI2005]狡猾的商人(带权并查集)

刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了n个月以来的收入情况,其中第i 个月的收入额为Ai(i=1,2,3...n-1...

1433
来自专栏程序猿DD

看完此文再不懂区块链算我输,用Python从零开始创建区块链

如果你还没有听说过 3 点钟区块链群,说明你还不是链圈的人;如果你还没有加入 3 点钟区块链群,说明你还不是链圈的大佬;如果你还没有被 3 点钟区块链群刷屏,说...

5148
来自专栏区块链大本营

真相只有一个 !God.Game 代币被盗事件原理分析

8月22日中午,区块链游戏God.Game宣布游戏内所有代币被攻击者卷走,项目方筹备两个月,游戏却在运营不久后迅速夭折。

954
来自专栏区块链大本营

套利、投资、创业,从0到1打造更好的点对点交易协议

1573
来自专栏区块链大本营

“冰封”合约背后的老牌劲敌——拒绝服务漏洞 | 漏洞解析连载之二

眼观目前区块链发展的步伐越来越急促,似乎我们已无暇回首当初那些辉煌与挫败,只能低着头继续跟从与追赶。

641
来自专栏友弟技术工作室

区块链 价值互联网的基石

这是我很久之前看的一本书,对区块链的概念解释简单易懂,适合入门, 好久没有写区块链的开发,所以现在重拾起。这本书也推荐给想要入门的朋友。

1811
来自专栏申龙斌的程序人生

解密Coin.Dance【区块链生存训练】

在比特币分叉时期,关注区块链动向的网站有很多,CoinDance网站 (https://coin.dance)就是非常有名的一个,里面提供了包括市值、价格、节点...

4126
来自专栏华章科技

看完此文再不懂区块链算我输:手把手教你用Python从零开始创建区块链

导读:如果你还没有听说过 3 点钟区块链群,说明你还不是链圈的人;如果你还没有加入 3 点钟区块链群,说明你还不是链圈的大佬;如果你还没有被 3 点钟区块链群刷...

962

扫码关注云+社区

领取腾讯云代金券