「CF468B」Two Sets

2014年9月21日3,1530

Little X has n distinct integers: p₁, p₂, …, p_n. He wants to divide all of them into two sets A and B. The following two conditions must be satisfied:

If number x belongs to set A, then number a - x must also belong to set A.
If number x belongs to set B, then number b - x must also belong to set B.

Help Little X divide the numbers into two sets or determine that it’s impossible.

Input

The first line contains three space-separated integers n, a, b (1 ≤ n ≤ 10⁵; 1 ≤ a, b ≤ 10⁹). The next line contains n space-separated distinct integers p₁, p₂, …, p_n (1 ≤ p_i ≤ 10⁹).

Output

If there is a way to divide the numbers into two sets, then print “YES” in the first line. Then print n integers: b₁, b₂, …, b_n (b_i equals either0, or 1), describing the division. If b_i equals to 0, then p_i belongs to set A, otherwise it belongs to set B.

If it’s impossible, print “NO” (without the quotes).

Sample test(s)

input

4 5 9
2 3 4 5

1 2	4 5 9 2 3 4 5

output

YES
0 0 1 1

1 2	YES 0 0 1 1

input

3 3 4
1 2 4

1 2	3 3 4 1 2 4

output

NO

Note

It’s OK if all the numbers are in the same set, and the other one is empty.

为什么你们都会做。。。

我的思路完全偏了。。。

可以先确定一个数在某个集合，然后可以确定一系列和它相关的数所在集合，看是否矛盾

具体用dfs来搞

一个点最多被搜2次

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#define inf 2147483647
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int A=0,B=1;
int n,a,b,p[100005],ans[100005];
map<int,int> mp;
bool dfs(int x,int f)
{
    if(!mp.count(a-p[x])&&!mp.count(b-p[x]))return 0;
    if(!mp.count(a-p[x])&&mp.count(b-p[x]))
    {
        ans[x]=B;
        int pos=mp[b-p[x]];
        if(ans[f]==A)return 0;
        else return f||dfs(pos,x);
    }
    else if(mp.count(a-p[x])&&!mp.count(b-p[x]))
    {
        ans[x]=A;
        int pos=mp[a-p[x]];
        if(ans[f]==B)return 0;
        else return f||dfs(pos,x);
    }
    else 
    {
        int pos1=mp[a-p[x]],pos2=mp[b-p[x]];
        if(pos1==f)
        {
            ans[x]=ans[f];
            return dfs(pos2,x);
        }
        if(pos2==f)
        {
            ans[x]=ans[f];
            return dfs(pos1,x);
        }
        ans[x]=A;
        bool flag=dfs(pos1,x)&&dfs(pos2,x);
        if(!flag)
        {
            ans[x]=B;
            flag=dfs(pos1,x)&&dfs(pos2,x);
            if(!flag)
                return 0;
        }
        return 1;
    }
    return 1;
}
void work()
{
    for(int i=1;i<=n;++i)
        if(ans[i]==-1)
            if(!dfs(i,0))
            {puts("NO");return;}
    puts("YES");
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    printf("\n");
}
int main()
{   
    n=read();a=read();b=read();
    if(a==b)b=inf;
    for(int i=1;i<=n;++i)
    {
        p[i]=read();
        mp[p[i]]=i;
    }
    memset(ans,-1,sizeof(ans));
    work();
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<set>

#include<map>

#define inf 2147483647

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int A=0,B=1;

int n,a,b,p[100005],ans[100005];

map<int,int> mp;

bool dfs(int x,int f)

{

if(!mp.count(a-p[x])&&!mp.count(b-p[x]))return 0;

if(!mp.count(a-p[x])&&mp.count(b-p[x]))

{

ans[x]=B;

int pos=mp[b-p[x]];

if(ans[f]==A)return 0;

else return f||dfs(pos,x);

}

else if(mp.count(a-p[x])&&!mp.count(b-p[x]))

{

ans[x]=A;

int pos=mp[a-p[x]];

if(ans[f]==B)return 0;

else return f||dfs(pos,x);

}

else

{

int pos1=mp[a-p[x]],pos2=mp[b-p[x]];

if(pos1==f)

{

ans[x]=ans[f];

return dfs(pos2,x);

}

if(pos2==f)

{

ans[x]=ans[f];

return dfs(pos1,x);

}

ans[x]=A;

bool flag=dfs(pos1,x)&&dfs(pos2,x);

if(!flag)

{

ans[x]=B;

flag=dfs(pos1,x)&&dfs(pos2,x);

if(!flag)

return 0;

}

return 1;

}

return 1;

}

void work()

{

for(int i=1;i<=n;++i)

if(ans[i]==-1)

if(!dfs(i,0))

{puts("NO");return;}

puts("YES");

for(int i=1;i<=n;++i)

printf("%d ",ans[i]);

printf("\n");

}

int main()

{

n=read();a=read();b=read();

if(a==b)b=inf;

for(int i=1;i<=n;++i)

{

p[i]=read();

mp[p[i]]=i;

}

memset(ans,-1,sizeof(ans));

work();

return 0;

}

« 「BZOJ3687」「FJ2014集训」简单题「BZOJ3631」[JLOI2014] 松鼠的新家 »

hzwer.com _ Home | http://hzwer.com

「CF468B」Two Sets

分类目录

热门文章

Myfriends

近期评论