题目链接

分析:根据分析,关系的递推满足由[a,b]~[b,c]得:[a,c]=([a,b]+[b,c])%3;[a,d]=([a,b]+[b,c]+[c,d])%3.由rank数组表示关系

0 - 这个节点与它的父节点是同类

1 - 这个节点被它的父节点吃

2 - 这个节点吃它的父节点。

则:当 d = 1的时候,( d - 1 ) = 0,也就是我们制定的意义

当 d = 2的时候,( d - 1 ) = 1,代表Y被X吃,也是我们指定的意义。

逆推根节点与Y的关系

这部分也是穷举法推出来的,我们举例:

父相对于子的relation(即假如子是父的父节点,那么父的relation应该是什么,因为父现在是根节点,所以父.relation = 0,我们只能根据父的子节点反推子跟父节点的关系)

0             ( 3 - 0 ) % 3 = 0

1(父吃子)   ( 3 - 1 ) % 3 = 2 //父吃子

2(子吃父)    ( 3 - 2 ) % 3 = 1 //子吃父,一样的

因此合并时,x,y,a(x的根节点),b(y的根节点),d(x与y的关系),rank[x](x与a的关系),rank[y](y与b的关系)rank[b](b与a的关系)则:

[b,a]=([b,y]+[y,x]+[x,a])%3.而[b,y]=(3-[y,b])%3.因此rank[b]=(3-rank[y]+d+rank[x]).

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-9
#define N 50010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
int fa[N],rank[N];
int find(int x)
{
if(x==fa[x])return x;
int pa=fa[x];
fa[x]=find(fa[x]);
rank[x]=(rank[x]+rank[pa])%;
return fa[x];
}
void merge(int a,int b,int x,int y,int d)
{
fa[b]=a;
rank[b]=(-rank[y]+d-+rank[x])%;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++)
{
fa[i]=i;
rank[i]=;
}
int ans=;
while(m--)
{
int d,x,y;
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n||(d==&&x==y))ans++;
else
{
int a=find(x);
int b=find(y);
if(a!=b)merge(a,b,x,y,d);
else
{
if((rank[y]+-rank[x])%!=d-)ans++;
}
}
}
printf("%d\n",ans);
}

最新文章

  1. 查询阻塞的sql
  2. 01、AngularJs简介
  3. DatagramSocket收发UDP数据包
  4. 条件注释判断IE浏览器
  5. FbxDataType is ambiguous
  6. IAAS云计算产品畅想-云主机产品内涵
  7. MySQL 删除数据表
  8. Android消息机制(2)
  9. Java基础知识强化48:Java中哈希码
  10. .gitigore 相关
  11. TSQL语句和CRUD(20161016)
  12. JS Math.round()方法原理
  13. python_如何对迭代器进行切片操作
  14. ord()与char()
  15. Mybatis与Ibatis比较
  16. ajax的一些相关
  17. P5280 [ZJOI2019]线段树
  18. SSH使用Slf4j
  19. C#中使用Log4记录日志
  20. python模块整理30-uui模块

热门文章

  1. UFLDL 教程三总结与答案
  2. Android自定义View之CircleView
  3. 渲染物体到一张UITexture上
  4. javascript选取文档元素
  5. nyoj 284 坦克大战 (优先队列)
  6. HDU 1397 Goldbach&#39;s Conjecture(二分,查找素数)
  7. Part 2 Creating, altering and dropping a database
  8. BeanUtils在web项目中的应用
  9. 引用枚举进行对比时 enum需强制转换
  10. 笔记整理--Linux多线程
  11. 用lua+redis实现一个简单的计数器功能 (二)
  12. CRC32明文攻击
  13. js实现页面重新加载
  14. error C2371: &#39;IServiceProvider&#39; : redefinition; different basic types
  15. 命令提示符出现-bash-4.1$如何解决
  16. PWM实现ADC和DAC
  17. stm32 HAL库笔记(一)——普通IO口
  18. ABP框架 配置权限、本地语言文件、左侧菜单项
  19. 阅读Google Protocol Buffers 指南,整理pb语法
  20. SpringBoot-热部署Devtools