这次Div.2比之前我打的有些要难啊,前三道题就耗了好多时间,D题干脆摆烂了。。。
还是太逊了
对于一个\(x\),有\(x|y_i=z_i\),那么我们设\(num[x]=z_1\)&\(z_2\)&\(z_3\)....
若\(z_i\)的第\(pos\)位为0,则说明\(x\)与\(y_i\)的第\(pos\)位一定为0;若\(z_i\)的第\(pos\)位为0,则说明\(x\)与\(y_i\)第pos至少 有一个为1,即\(x\)的第\(pos\)位可能为1,\(y_i\)的第\(pos\)位可能为1
所以,对于初始的\(num[x]\),它就是第\(x\)个数的所有答案中最大的
既然答案要求字典序最小,那么遍历第一个数到最后一个数,将当前数记为\(x\),将所有与\(x\)有题目给定的关系的\(y\)与\(z\)都遍历一遍,记 \(t|=z_i\)&(~\(num[y_i]\))
\(z_i\)&(~\(num[y_i]\))显然意味着在当前这个关系中,\(x\)必须取到的1
所以\(t|=z_i\)&(~\(num[y_i]\))也就意味这对于\(x\)的所有关系,\(x\)必须取的数
前文说了对于初始的\(num[x]\),它是第\(x\)个数的所有答案中最大的,所以这时求出的\(t\)也一定 是第一个数最小的答案
再将\(num[x]\)更新为\(t\),继续上述过程,得到的就是字典序最小的答案
#include<bits/stdc++.h>
#define pr pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,q,num[N];
vector<pr> cdt[N];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) num[i]=(1<<30)-1;
for(int i=1,x,y,z;i<=q;++i){
scanf("%d%d%d",&x,&y,&z);
num[x]&=z,num[y]&=z;
cdt[x].push_back(pr(y,z));
cdt[y].push_back(pr(x,z));
}
for(int i=1;i<=n;++i){
int t=0;
for(int j=0;j<cdt[i].size();++j){
int x=cdt[i][j].fi,s=cdt[i][j].se;
t|=(s&(~num[x]));
if(x==i){ t=s; break; }
}
printf("%d ",(num[i]=t));
}
return 0;
}