E. Compatible Numbers(SoSdp入门)

传送门

题意

给出 n n n个数 a i a_i ai,为每个 a i a_i ai找到一个 a j a_j aj使得 a i a j = = 0 a_i\a_j==0 aiaj==0,若不存在输出 − 1 -1 1

其中 n , a i n,a_i n,ai均小于 4 ∗ 1 0 6 4*10^6 4106


SOSDP

因为 s o s d p sosdp sosdp求的是 f [ m a s k ] = ∑ i m a s k = i a i f[mask]=\sum\limits_{i\mask=i}a_i f[mask]=imask=iai

现在只需要把定义换一下, f [ m a s k ] f[mask] f[mask]装的是某个 m a s k mask mask子集的数字

那么对每个 a i a_i ai来说,需要找到某个 a j a_j aj a i a_i ai完全没有交集

转化一下,就是 a j a_j aj a i a_i ai补集的子集

所以答案为 f [ ∼ a i ] f[\sim a_i] f[ai]

再说一下 f f f数组的初始化

即当所有二进制都和 m a s k mask mask相同时的答案, f [ m a s k ] = m a s k f[mask]=mask f[mask]=mask

前提是 m a s k mask mask这个数字存在,否则仍然无法作为答案

#include bits/stdc++.h
using namespace std;
const int mx = 122;
int n,a[mx],f[mx];
int main()
{
	scanf("%d",n);
	for(int i=1;i=n;i++)	scanf("%d",a[i] ),f[a[i]] = a[i];
	for(int i=0;i22;i++) 
	for(int j=0;jmx;j++)
	{
		if( f[j] )	continue;//已经找到了答案 
		if( j(1i) )	f[j] = f[j^(1i)];
	}
	for(int i=0;imx;i++)	if( !f[i] )	f[i] = -1;
	for(int i=1;i=n;i++)	printf("%d ",f[(mx-1)^a[i]]);
}
最新回复(0)
/jishudjt_2F4QETSP3U4b13MO_2FQ61fbZwEDdFwWXICKTzTBV10_3D4834426
8 简首页