[Codeforces Round #816 (Div. 2)] D. 2+ doors

这次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;

}

巴特西

[Codeforces Round #816 (Div. 2)] D. 2+ doors

最新文章

热门文章