G-丹青玩游戏

G-丹青玩游戏

/ 0评 / 1347次 / 1

Description

在半年的林大生活里,很多同学喜欢来丹青学习,而丹青教室的灯却总是忽明忽暗,非常不利于我们学(wan)习(you xi),为此,一些同学决定修改丹青的电路。 现在,我们已知一个教室里有m个灯,n个开关,每个灯由其中几个开关控制,对于灯泡i,相关开关为“on”的数量对2取模与pi相同时,该灯泡亮,问: 想要所有的灯泡都亮,开关的“on”和“off”状态有几种组合方式(比如:5个开关中1 2 4号为“on”和3 4号开关为“on”是两种不同的组合方式)

Input

多组输入。 第一行:开关数量n和灯泡数量m 第2行至第m+1行:第一个数字ki是第i个灯泡相关的开关数量,其后是开关编号(1~n) 最后一行:pi每个灯泡亮的状态 数据范围:\( 1≤n,m≤10 1≤ki≤N \) Pi 为0或1 所有输入均为整数。

Output

输出一个整数,表示总的开关组合数量。

Analysis

清晰明了的二进制枚举(深度优先搜索题)只要能够理清楚控制具体灯泡的具体开关数量,(我这里利用结构体加以存储)就可以轻松AC

Accepted Code

/*
 * @Author: Gehrychiang
 * @LastEditors: Gehrychiang
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;
struct $
{
    int asc[12]; //开关相关数组,下标记录  1为相关 0为无关
    int sta;
};
$ light[12];
int n; //开关数量
int m; //灯泡数量
int main()
{
    while (cin >> n >> m)
    {
        //input
        memset(light, 0, sizeof(light));
        for (int i = 0; i < m; i++)
        {
            int tmp; //相关个数
            cin >> tmp;
            while (tmp--)
            {
                int xg;
                cin >> xg;
                light[i].asc[xg] = 1;
            }
        }

        for (int i = 0; i < m; i++)
        {
            cin >> light[i].sta;
        }
        //input
        int cnt = 0;
        for (int i = 0; i < (1 << n); i++) //有n个开关就有2^n中排列
        {
            int dpkaiguan[12] = {0}; //用来记录每个灯泡对应开关开了的个数
            //cout<<"i:"<<i<<endl;
            for (int j = 0; j < n; j++)
            {

                if (i & (1 << j)) //第j为有值,第j个开关为开的状态
                {
                    //cout<<"j:"<<j<<endl;
                    for (int x = 0; x < m; x++)
                    {
                        if (light[x].asc[j + 1] == 1)
                        {
                            dpkaiguan[x]++;
                        }
                    }
                }
            }
            //检查是否满足题目要求
            /*
            for (int i = 0; i < m; i++)
            {
                cout<<dpkaiguan[i]<<" ";
            }
            cout<<endl;
            */
            int liangdengshu = 0;
            for (int i = 0; i < m; i++)
            {
                if (dpkaiguan[i] % 2 == light[i].sta)
                {
                    ++liangdengshu;
                }
            }
            if (liangdengshu == m)
            {
                ++cnt;
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.63970