内推鸭

题解：二进制枚举

我们发现，每个摄像头都可以选择/不选择，因此我们可以使用二进制枚举算法来求解，不熟悉二进制枚举算法的同学，可以做一下这道模板题：字符串的子序列

使用二进制枚举的时间复杂度为 $O(2^n)$ ，其中 $n\le 25$ ，因此最坏情况为 $2^{25} \approx 32\times 10^6$ ，是不会超时的。

但是本题有一个头疼的问题， $m$ 的范围很大，使用二进制枚举每一个片区的监控状态，会超过int或者long long的最大范围，当然这对Python选手是没有影响的，但是对于C++/Java选手就不能使用这个方式来记录了，but！C++和Java都有bitset的库，我们可以使用bitset来存储每一个片区的监控状态，这样就不需要考虑数据范围的问题了，不熟悉bitset的同学，也可以通过这道题学习一下这个数据结构的存储，更新。

对于C++选手来说，只需要用到set()和count()这两个方法。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
vector<bitset<N>> state;   // 存储每个区域的摄像头位置
int maxv = 0;         // 最大监控的片区数
int res = 0;          // 最大监控片区数对应的方案数
bitset<N> cur;        // 当前监控区域的状态

// 递归枚举选取的摄像头组合
void dfs(int u, int cnt) {
    if (u == n) {  // 如果已经枚举完所有摄像头
        if (cnt > 0 && cnt <= 8) {  // 至少选择一个摄像头，并且不超过8个
            int num = cur.count();  // 当前监控的片区数
            if (num > maxv) {
                maxv = num;
                res = 1;
            } else if (num == maxv) {
                res++;
            }
        }
        return;
    }

    // 不选择第u个摄像头
    dfs(u + 1, cnt);

    // 选择第u个摄像头
    bitset<N> prev = cur;  // 保存当前状态，便于回溯
    cur |= state[u];       // 更新当前监控区域
    dfs(u + 1, cnt + 1);
    cur = prev;            // 回溯，恢复之前的状态
}

int main() {
    cin >> n >> m;
    state.resize(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        // 字符串转化为bitset，方便快速计算每个摄像头能监控到的片区
        for (int j = 0; j < m; j++) {
            if (s[j] == '1') {
                state[i].set(j);
            }
        }
    }

    dfs(0, 0);  // 从第0个摄像头开始枚举，初始计数为0
    cout << maxv << " " << res << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int N = 110;
    static int n, m;
    static List<BitSet> state = new ArrayList<>();  // 存储每个区域的摄像头位置
    static int maxv = 0;         // 最大监控的片区数
    static int res = 0;          // 最大监控片区数对应的方案数
    static BitSet cur = new BitSet(N);  // 当前监控区域的状态

    // 递归枚举选取的摄像头组合
    static void dfs(int u, int cnt) {
        if (u == n) {  // 如果已经枚举完所有摄像头
            if (cnt > 0 && cnt <= 8) {  // 至少选择一个摄像头，并且不超过8个
                int num = cur.cardinality();  // 当前监控的片区数
                if (num > maxv) {
                    maxv = num;
                    res = 1;
                } else if (num == maxv) {
                    res++;
                }
            }
            return;
        }

        // 不选择第u个摄像头
        dfs(u + 1, cnt);

        // 选择第u个摄像头
        BitSet prev = (BitSet) cur.clone();  // 保存当前状态，便于回溯
        cur.or(state.get(u));       // 更新当前监控区域
        dfs(u + 1, cnt + 1);
        cur = prev;            // 回溯，恢复之前的状态
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            BitSet bitSet = new BitSet(N);
            // 字符串转化为BitSet，方便快速计算每个摄像头能监控到的片区
            for (int j = 0; j < m; j++) {
                if (s.charAt(j) == '1') {
                    bitSet.set(j);
                }
            }
            state.add(bitSet);
        }

        dfs(0, 0);  // 从第0个摄像头开始枚举，初始计数为0
        System.out.println(maxv + " " + res);
        scanner.close();
    }
}

n, m = map(int, input().split())
state = []  # 存储每个区域的摄像头位置
maxv = 0  # 最大监控的片区数
res = 0  # 最大监控片区数对应的方案数
cur = 0  # 当前监控区域的状态，使用整数表示

# 递归枚举选取的摄像头组合
def dfs(u, cnt):
    global maxv, res, cur
    if u == n:  # 如果已经枚举完所有摄像头
        if cnt > 0 and cnt <= 8:  # 至少选择一个摄像头，并且不超过8个
            num = bin(cur).count('1')  # 当前监控的片区数
            if num > maxv:
                maxv = num
                res = 1
            elif num == maxv:
                res += 1
        return

    # 不选择第u个摄像头
    dfs(u + 1, cnt)

    # 选择第u个摄像头
    prev = cur  # 保存当前状态，便于回溯
    cur |= state[u]  # 更新当前监控区域
    dfs(u + 1, cnt + 1)
    cur = prev  # 回溯，恢复之前的状态

for _ in range(n):
    s = input()
    bitset = 0
    # 字符串转化为整数，方便快速计算每个摄像头能监控到的片区
    for j in range(m):
        if s[j] == '1':
            bitset |= (1 << j)
    state.append(bitset)

dfs(0, 0)  # 从第0个摄像头开始枚举，初始计数为0
print(maxv, res)