Ps:想看偏移向量的直接翻到下边
这是我第三次做这道题了,如愿以偿的AC了,,
今听了snake神犇的点拨,他说可以假设每一种生物属于ABC三种
如果a,b+n是同一颗树,那么a会吃掉b,
如果a,b+2*n是同一棵树,那么a会被b吃掉。
如果a,b是同类,那么a,b, a+n,b+n a+2*n,b+2*n两两合并
a吃b的话,a,b+n a+n,b+2*n a+2*n,b两两合并
那么判断a,b的关系也就只要判断a,b+n a,b+2*n是否是同一棵树了!
这种思路真的很奇妙!看上去好像挺耗时的,其实对比偏移向量并查集,也并没有慢很多
先附上这种思路的代码
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; #define MAX (50000+1) int n,m,mot[MAX*3],ans; int find(int x) { if ( x != mot[x] ) { mot[x] = find(mot[x]); } return mot[x]; } int merge(int a,int b) { a = find(a); b = find(b); mot[b] = a; } int main() { scanf("%d %d",&n,&m); for (int i = 1; i <= 3 * n; i++) { mot[i] = i; } int swi,a,b; for (int i = 1; i <= m; i++) { scanf("%d %d %d",&swi,&a,&b); if ( a > n || b > n ) { ans++; } else if ( swi == 1 ) { if ( find(a) == find(b+n) || find(a) == find(b+n+n) ) { ans++; } else { merge(a,b); merge(a+n,b+n); merge(a+n+n,b+n+n); } } else { if ( find(a) == find(b) || find(a) == find(b+n+n) ) {//如果是同类或者b吃a ans++; } else { merge(a,b+n); merge(a+n,b+n+n); merge(a+n+n,b); } } } cout<<ans; return 0; }
不过我的主要目标是搞懂偏移向量的,
所以又写了个偏移向量的
我们用一个dir[]数组表示每一个物种与他上级的关系,我们很容易能发现
利用a,b b,c的关系,可以推导出a,c的关系!
我定义如果i和上级是同物种,dir[i] = 0
i吃上级,dir[i] = 1;
i被上级吃,dir[i] = 2;
为什么这么定义呢?(其实你也可以把值改变,但关系传递时你就慢慢写if来判断吧)
我的合并操作还是把a所在树当做b的子树,那么a的上级与b的关系也可以根据a,b的关系&&a和上级的关系推出
代码:
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; #define MAX (50000+1) int n,m,mot[MAX],dir[MAX],ans; int find(int x) { if ( x != mot[x] ) { int fat = mot[x]; mot[x] = find(mot[x]); dir[x] += dir[fat]; dir[x] %= 3; } return mot[x]; } void merge(int a,int b,int c) { if ( a == mot[a] ) { mot[a] = b; dir[a] = c; } else { mot[ mot[a] ] = b; dir[ mot[a] ] = ((c + 9) - dir[a]) % 3; } } int main() { scanf("%d %d",&n,&m); for (int i = 1; i <= n; i++) { mot[i] = i; } int swi,a,b; for (int i = 1; i <= m; i++) { scanf("%d %d %d",&swi,&a,&b); if ( a > n || b > n ) { ans++; } else if ( swi == 1 ) { if ( find(a) == find(b) ) { if ( dir[a] != dir[b] ) { ans++; } } else { merge(a,b,0); } } else { if ( find(a) == find(b) ) { if ( ( 1 + dir[b] ) % 3 != dir[a] ) { ans++; } } else { merge(a,b,1); } } } cout<<ans; return 0; }