CF985B Switches and Lamps【矩阵操作/枚举】

【链接】CF985B
【题意】：给n盏灯，m个开关，每次按开关只能将灯从灯灭的状态转变为灯亮，问是否存在不按所有开关就将所有灯打开的方法。
【分析】：有两种办法，一种代码复杂点，容易想到枚举去掉每一行,看看能不能有一行去掉后保证其他的每一列至少有一个1，注意如果去掉某行后有一列为0则这一行不行，那么要枚举下一行，就要把减去的加回来，相当于还原现场。
第二种代码简单，但是不易想到，就是判断只要存在某行位置为‘1’且对应列的‘1’的个数只有1个，那去掉这行就把唯一的1个去掉了，是绝对不行的。
核心代码：

for (int i=0; i<n; i++)
{  
        int f= 1;  
        for (int j=0; j<m; j++)
        {  
            if (a[i][j] == '1' && k[j]==1)
            {  
                    f= 0;  
            }  
        }  
        if (f)
        {  
            printf("YES\n");  
            return 0;  
        }  
    }  
    printf("NO\n");  
return 0；

【代码】：

#include <iostream>
#include<queue>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 2005
const int  INF =  0x3f3f3f3f;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define ll long long
int n,m,x,y;
char a[M][M];
int k[M];
//枚举去掉每一行,看看能不能有一行去掉后保证其他的每一列至少有一个1
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) //这样要以0为起点,若以1开头scanf("%s", a[i] + 1);
    {
        scanf("%s",&a[i]);
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='1')
            {
                k[j]++;
            }
        }
    }
    int f=1;
    for(int i=0; i<n; i++)
    {
        f=1;
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='1')
            {
                k[j]--;
            }
        }
        for(int j=0; j<m;j++)
        {
            if(!k[j]) f=0;
            if(a[i][j]=='1') k[j]++; //有点回溯的味道,相当于还原现场
        }
        if(f) break;

    }
    f?puts("YES"):puts("NO");
}
//找是否存在一个开关，他控制的每盏灯均由至少两个开关控制

---

#include <iostream>
#include<queue>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 2005
const int  INF =  0x3f3f3f3f;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define ll long long
int n,m,x,y;
char a[M][M];
int k[M];
//枚举去掉每一行,看看能不能有一行去掉后保证其他的每一列至少有一个1
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) //这样要以0为起点,若以1开头scanf("%s", a[i] + 1);
    {
        scanf("%s",&a[i]);
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='1')
            {
                k[j]++;
            }
        }
    }
    for (int i=0; i<n; i++)
    {
        int f = 1;
        for (int j=0; j<m; j++)
        {
            if (a[i][j] == '1' && k[j] == 1)
            {
                f = 0;
            }
        }
        if (f)
        {
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}