台州网站推广技巧付费,网页制作的步骤,html5网络公司网站模板,seo基础培训机构链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
题目描述
动物王国中有三类动物A,B,C#xff0c;这三类动物的食物链构成了有趣的环形。A吃B#xff0c;B吃C#xff0c;C吃A。
现有N个动物#xff0c;以1#xff0d;N编号。每个动物都…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
题目描述
动物王国中有三类动物A,B,C这三类动物的食物链构成了有趣的环形。A吃BB吃CC吃A。
现有N个动物以1N编号。每个动物都是A,B,C中的一种但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述
第一种说法是“1 X Y”表示X和Y是同类。
第二种说法是“2 X Y”表示X吃Y。
此人对N个动物用上述两种说法一句接一句地说出K句话这K句话有的是真的有的是假的。当一句话满足下列三条之一时这句话就是假话否则就是真话。
1 当前的话与前面的某些真的话冲突就是假话
2 当前的话中X或Y比N大就是假话
3 当前的话表示X吃X就是假话。
你的任务是根据给定的N1≤N≤50,000和K句话0≤K≤100,000输出假话的总数。 输入描述:
第一行是两个整数N和K以一个空格分隔。
以下K行每行是三个正整数 DXY两数之间用一个空格隔开其中D表示说法的种类。
若D1则表示X和Y是同类。
若D2则表示X吃Y。
输出描述:
只有一个整数表示假话的数目。 种类并查集
#includebits/stdc.h
typedef long long ll;
using namespace std;
ll n;
ll fa[150004];
ll find(ll x)
{return xfa[x]?x:fa[x]find(fa[x]);
}
void merge(ll a,ll b)
{afind(a),bfind(b);fa[a]b;
}
void solve()
{ll n,k;cinnk;ll ans0;for(ll i1;i150003;i){fa[i]i;}ll op,x,y;for(ll i0;ik;i){cin op x y;if (x n || y n || (op 2 x y)) {ans;continue;}if (op 1) {if (find(x) find(y n) || find(x) find(y 2 * n)) {ans;}else {merge(x, y);merge(x n, y n);merge(x 2 * n, y 2 * n);}}else {if (find(x) find(y) || find(x) find(y 2 * n)) {ans;}else {merge(x, y n);merge(x n, y 2 * n);merge(x 2 * n, y);}}}coutans\n;
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t1;while(t--)solve();return 0;} 带权并查集
#includebits/stdc.h
typedef long long ll;
using namespace std;
ll n;
ll fa[50004];
ll re[50004];
ll find(ll x)
{if(x!fa[x]){ll tfa[x];fa[x]find(fa[x]);re[x](re[x]re[t])%3;}return fa[x];
}
void merge(ll a,ll b,ll k)//012,同类捕食被捕食
{ll xfind(a),yfind(b);if(a!b){fa[x]y;re[x](kre[b]-re[a]3)%3;}
}
void solve()
{for(ll i1;i50002;i){fa[i]i;re[i]0;}ll n,k;cinnk;ll nums0;for(ll i1;ik;i){ll d,x,y;cindxy;ll afind(x),bfind(y);if(xn||yn||(d2xy)){nums;}else if(d1){if(a!b){merge(x,y,0);}else if(re[x]!re[y]){nums;}}else{if(a!b){merge(x,y,1);}else if((re[x]-re[y]3)%3!1){nums;}}}coutnums;
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t1;while(t--)solve();return 0;}
