开关问题

输入第一行有一个数K，表示以下有K组测试数据。
每组测试数据的格式如下：
第一行一个数N（0 < N < 29）
第二行 N个0或者1的数，表示开始时N个开关状态。
第三行 N个0或者1的数，表示操作结束后N个开关的状态。
接下来每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。每组数据以 0 0 结束。

C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 300K, 提交时间: 2023-01-08 16:31:47

#include<iostream>
#include<algorithm>
using namespace std;

int a[100],n,t,ans;

int main(void)
{
    int t;
    cin>>t;
    while(t--)
    {
        ans=1;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1,temp;i<=n;i++)
        {
            cin>>temp;
            a[i]^=temp;
            a[i]|=1<<i;
        }
        int x,y;
        while(cin>>x>>y&&x&&y) a[y]|=1<<x;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
                if(a[j]>a[i])
                {
                    swap(a[j],a[i]);
                }
            if(a[i]==0) {ans=1<<(n-i+1);break;}
            if(a[i]==1) {ans=0;break;}
            for(int k=n;k;k--)
            {
                if(a[i]>>k&1)
                {
                    for(int j=1;j<=n;j++) if(i!=j&&a[j]>>k&1) a[j]^=a[i];
                    break;
                }
            }
        }
        if(ans==0) cout<<"Oh,it's impossible~!!"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 2ms, 内存消耗: 356K, 提交时间: 2020-08-18 10:27:58

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1010];
int main()
{
	int t;scanf("%d",&t);
	while(t--)
	{
		int n;scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		{
			int c;scanf("%d",&c);
			a[i]^=c;a[i]|=1<<i;
		}
		int x,y;
		while(~scanf("%d %d",&x,&y)&&x&&y)
		{
			a[y]|=1<<x;
		}
		int ans=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			if(a[j]>a[i])swap(a[j],a[i]);
			if(a[i]==0){ans=1<<(n-i+1);break;}
			if(a[i]==1){ans=0;break;}
			
			for(int k=n;k;k--)
			if((a[i]>>k)&1)
				for(int j=1;j<=n;j++)
					if(i!=j&& (a[j]>>k &1))a[j]^=a[i];
		}
		if(!ans)printf("Oh,it's impossible~!!\n");
		else printf("%d\n",ans);
	}
	return 0;
}

详情