Codeforces 517 #B

http://codeforces.com/contest/1072/problem/B

开始想的只有搜索，时间复杂度$O(4^n)$,明显有问题。

想了半个小时没有思路，然后想到了正难则反，就开始步入正轨。

题目给出了$a[ ]$和$b[ ]$数组，首先与处理，我们枚举每一种情况的$a[i]$和$b[i]$，然后枚举ans[i]表示当为$ans[i]$时下一个数可以填几，预处理完你会发现，有合法的数对的情况只有一种。

预处理时间复杂度$O(4^4)$

接下来我们可以枚举答案序列的第一位填啥，从而可以推出其他的数字填啥。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int f[][][];

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

bool check()

{

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

    {

        ans[i]=f[a[i]][b[i]][ans[i-]];

        if(ans[i]==-)return ;

    }

    return ;

}

int main()

{

    memset(f,-,sizeof(f));

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

    {

        for(int j=;j<=;j++)

        {

            for(int k=;k<=;k++)

            {

                for(int p=;p<=;p++)

                {

                    int x=p|k,y=p&k;

                    if(x==i&&y==j)f[i][j][k]=p;

                }

            }

        }

    }

    bool flag=;

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)scanf("%d",&b[i]);

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

    {

        ans[]=i;

        if(check())

        {

            flag=;

            break;

        }

    }

    if(!flag)printf("NO");

    else

    {

        printf("YES\n");

        for(int i=;i<=n;i++)printf("%d ",ans[i]);

    }

}

巴特西

Codeforces 517 #B

最新文章

热门文章