L2-3 花非花,雾非雾
题目描述 :
CC 在梦中遇到了一个美丽序列,但是醒来已经记不清具体数值了。但幸运的是他还记得些某两个数的异或值,和某些具体值。需要你来帮助他完成序列回忆。
即现在有一个长度为 n 的数列 a1 , a2 , a3 ··· an,但是不知道具体数值,现在有 q 条信息,每条信息只会是以下 2 种之一。
1 : U x y w 表示 ax ^ ay = w。
2 : S x y 表示 ax = y。输入格式
第一行包含 2 个整数 n、q。 (1≤n≤4×104,1≤q≤4×105)
第二到 q+1 行每行给出一条信息。 (1≤x,y≤n,1≤ai≤109)输出格式 :
对于每条信息,若与前面能得出的信息发生矛盾则忽略本条信息。最后只需输出数列 a,如果不能确定唯一的数列则输出
sad
。输入输出样例:
输入样例1
5 6 U 1 3 6 U 3 5 2 U 1 5 5 S 2 4 S 1 5 U 1 4 7
输出样例1
5 4 3 2 1
输入样例2
5 4 U 1 3 6 U 3 5 2 U 1 2 5 U 1 4 1
输出样例2
sad
样例解释
对于样例一,最开始每个数都不知道
第一条信息 a1 ^ a3 = 6
第二条信息 a3 ^ a5 = 2
第三条信息 a1 ^ a5 = 5 (与前面能得出的信息矛盾,忽略该信息)
第四条信息 a2 = 4
第五条信息 a1 = 5
第五条信息 a1 ^ a4 = 7
最终可以得出 a 数列为 5 4 3 2 1对于样例二,可证明不能确定唯一的数列。
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
#define int long long
typedef pair<int,int> pii;
const int N=400010;
int n,q;
int cnt[N],p[N],ans[N];
vector<pii>g[N];
int st[N];
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void dfs(int x,int fa)
{
st[x]=1;
for(auto [a,b]:g[x])
{
if(a==fa)continue;
ans[a]=ans[x]^b;
dfs(a,x);
}
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
ans[i]=-1;
p[i]=i;
}
while(q--)
{
char op;
cin>>op;
if(op=='U')
{
int a,b,c;
cin>>a>>b>>c;
int aa=find(a),bb=find(b);
if(aa!=bb&&cnt[aa]+cnt[bb]<=1)
{
p[aa]=bb;
cnt[bb]+=cnt[aa];
g[a].push_back({b,c});
g[b].push_back({a,c});
}
}else{
int a,b;
cin>>a>>b;
int aa=find(a);
if(cnt[aa]==0)
{
cnt[aa]++;
ans[a]=b;
}
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]!=-1&&st[i]==0)
{
dfs(i,-1);
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]==-1)
{
cout<<"sad"<<endl;
return;
}
}
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
}
signed main()
{
int good_luck_to_you;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
good_luck_to_you=1;
// cin>>good_luck_to_you;
while(good_luck_to_you--)
{
solve();
}
}
思路:比赛的时候想着应该是dfs一类的,但是不能排除冲突条件,所以不知道怎么写。
正确思路是并查集+dfs,因为如果a^b=c,那么a和b一定是有关系,我们就可以想到他们是一个连通块,而且只要这个连通块里面有一个确定的值,其他的数就都可以确定,所以不管冲不冲突,对于a^b=c我们只需要判断a和b是否再同一个连通块中并且确定值必须<=1,对于a=b,我们就判断a所在的连通块是否已经有了一个确定的值,如果没有,我们就把下标为a的值赋成b并且a所在的连通块就已经有了值 。
我们用dfs来填充最后的值,加入st数组判断这个下标的数是否已经被填过,最后判断一下数组中是否有-1,如果有,则按照题目输出即可。