二进制开关的状态的计算问题,如何利用C程序的设计的思想的办法来解决的

Problem Description
There are N lamps in a line and M switches control them. Each switch is connected to a subset of these lamps. When a switch is flipped, all the lamps connected to it change its state (on to off and off to on).

Input
The input contains multiple test cases. Each test case starts with two integers N and M (0<N<=50, 0<M<=100), which stand for the number of lamps and swithes. Then M lines follows, each line contains N characters. The jth character of the ith line is '1' if the ith switch is connected to the jth lamp, and '0' otherwise. The next line is a integer Q, which is the number of queries. Each of following Q lines contains the initial and target state of lamps ('0' is off and '1' is on).

Output
For each query, output "Yes" if it is possible to change the state from initial to target with these swithes. Otherwise, output "No".

Sample Input
5 3
00000
10101
01010
3
00000 11111
10101 01010
11111 10001

Sample Output
Yes
Yes
No

1个回答

每盏灯的状态用一个bit就能表示,但是每组灯最大可能有50个,所以需要用long long。开关与灯的连接关系也是一样,每个开关也无非『开』与『关』两种状态, 假设初始状态为『关』开的话其实就是拿灯的状态与开关按位异或就行了。但是开关的个数最大可能有100个,long long的位数都不够,只能用数组表示,同时用一个 数组来记录每个开关的状态。遍历每个开关状态的时候类似二进制运算,从0开始,每试一种状态就加1,该进位进位,直到溢出为止。

#include <stdio.h>
long long bstr_to_int(char* p,int len){
    long long tmp=0;
    for(int i=0;i<len;i++){
        tmp<<=1;
        if(*p++!='0')
            tmp|=1;
    }
    return tmp;
}
int main(){
    int n,m,q;
    long long swithes[100];
    char str1[50],str2[50];
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%s",str1);
        swithes[i]=bstr_to_int(str1,n);
    }
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        long long initial,target,halfway;
        int status[100];
        int prt=0;
        scanf("%s %s",str1,str2);
        initial=bstr_to_int(str1,n);
        target=bstr_to_int(str2,n);
        if(initial==target){
            printf("Yes\n");
           continue;
        }
        while(prt<m){
            status[prt]^=1;
            if(!status[prt]){
                prt++;
                continue;
            }
            halfway=initial;
            for(int j=0;j<m;j++){
                if(status[j])
                    halfway^=swithes[j];
            }
            if(halfway==target){
                printf("Yes\n");
                break;
            }else{
                prt=0;
                continue;
            }
        }
        if(prt>=m){
            printf("No\n");
        }

    }
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

6
c++针对二进制补码算术中整数的算术运算问题,请大神指点
2
关于32单片机 十进制转换二进制,保存至数组的问题
4
java中double二进制浮点计算问题
3
c++中用openCV的IplImage*或Mat读取图片后如何转化为File文件流(或者二进制数据)的格式
3
求助,本人小白;用C语言怎么用2种不同思路输出OXE3的二进制?
2
java上传文件时,前台的如何把文件以二进制的方式传到后台
2
用BCP如何导出二进制格式的bin文件?
3
python3 图片的二进制流转图片的方法
2
C# 读取C++写的 二进制文件
1
C语言求问这个二进制转换的问题怎么计算,要用到图的知识
2
这个问题,,用C语言解决,计算二进制的位数的问题,很难
3
关于float类型在计算机中的二进制表示的疑问
6
怎么接收Post过来的一段把图片转成二进制流的东西
0
最大二进制公共子序列的一个算法的问题如何利用C语言的办法去实现怎么做?
0
C语言的编程的技术,去解决这里二进制的序列的一个问题的算法怎么实现的思路
1
单独设置二进制位的问题,怎么利用C语言的办法实现呢
0
二进制线段数列的枚举的典型问题,使用C语言编写程序设计解决这个算法是怎么做的
0
最大的二进制子序列的查找算法,运用C语言的程序的设计的原理实现
0
用二进制的方式来解决一下这个棋盘问题的做法,使用C语言程序设计的思路
0
定义周期二进制字符串的问题,运用C程序的办法的思维解决怎么做