问题分析

有一个 $N \times N$ 的网格，每个位置有一个灯泡，灯泡可以是：

• 水平型 (H)：照亮整行
• 垂直型 (V)：照亮整列

目标：找出一种方案，用最少的灯泡点亮整个房间（即所有格子至少被一个灯泡照亮）。

约束：

• 不知道每个灯泡的类型
• 可以进行实验：打开某些灯泡，获得被照亮的格子总数
• 最多 2000 次实验，实验次数越少分数越高

算法思想：信息论与概率推理

关键观察

1. 问题本质：这是二分图匹配问题

   • 行节点：$N$ 个，需要选择一些行灯泡
   • 列节点：$N$ 个，需要选择一些列灯泡
   • 每个灯泡 $(i,j)$ 要么是行类型（对应行 $i$），要么是列类型（对应列 $j$）
   • 目标：选择最小数量的行和列，覆盖所有格子

2. 最小覆盖：根据 Kőnig 定理，二分图的最小点覆盖 = 最大匹配

   • 这里就是选择最少的行和列，使得每个格子 $(i,j)$ 要么行 $i$ 被选，要么列 $j$ 被选

3. 信息获取：每次实验告诉我们打开了某些灯泡后，总共照亮了多少格子

   • 这个数值包含了重叠照明的信息

算法详解

数据结构

#define Board bitset<200>  // 表示可能的配置
vector<int> unknownX, unknownY;  // 未知的行和列
int knownX[100], knownY[100];    // 已知的匹配
vector<pair<int, int>> keys;     // 关键灯泡位置
vector<Board> boards;            // 所有可能的配置

算法流程

1. 初始化

• 所有行和列都未知
• boards 初始包含一个空配置

2. 添加关键灯泡

while ((int)keys.size() < (int)unknownX.size() + (int)unknownY.size() 
       && (int)boards.size() < 1024) {
    // 随机选择一个未知行和未知列的交点
    int x = unknownX[rnd(0, (int)unknownX.size() - 1)];
    int y = unknownY[rnd(0, (int)unknownY.size() - 1)];
    
    if (keyId[x][y] != -1) break;
    
    keyId[x][y] = (int)keys.size();
    keys.emplace_back(x, y);
    
    // 为每个配置添加两种可能性（H或V）
    vector<Board> newBoards;
    for (Board i : boards) {
        i[keyId[x][y]] = 0;  // 假设是垂直（照亮列）
        newBoards.push_back(i);
        i[keyId[x][y]] = 1;  // 假设是水平（照亮行）
        newBoards.push_back(i);
    }
    swap(boards, newBoards);
}

3. 设计最优实验

目标：选择一组灯泡进行实验，使得实验结果能最大程度地区分不同配置。

使用信息熵最大化策略：

for (int test = 0; test < 64; test++) {
    // 随机生成实验方案
    int p = test < 4 ? 100 : rnd(1, 99);
    Board enable;
    bool useKnownX = rnd(0, 1), useKnownY = rnd(0, 1);
    
    for (int i = 0; i < (int)keys.size(); i++)
        enable[i] = rnd(0, 99) < p;
    
    // 计算该实验在不同配置下的结果分布
    vector<int> cnt(n * n + 1, 0);
    for (Board i : boards)
        cnt[calculate(i, enable, useKnownX, useKnownY)]++;
    
    // 计算信息熵
    double sum = 0;
    for (int i = 0; i <= n * n; i++) {
        if (!cnt[i]) continue;
        sum += log((int)boards.size() * 1.0 / cnt[i]) 
               * cnt[i] / (int)boards.size();
    }
    
    // 选择信息熵最大的实验
    if (best < sum) {
        best = sum, bestEnable = enable;
        bestUseKnownX = useKnownX, bestUseKnownY = useKnownY;
    }
}

4. 执行实验并更新配置

// 发送实验请求
printf("?\n");
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++)
        printf("%d", query[i][j]);
    printf("\n");
}
fflush(stdout);

// 接收实验结果
int x;
scanf("%d", &x);

// 过滤掉与实验结果不符的配置
vector<Board> newBoards;
for (Board i : boards)
    if (calculate(i, bestEnable, bestUseKnownX, bestUseKnownY) == x)
        newBoards.push_back(i);
swap(boards, newBoards);

5. 推导确定信息

for (int i = 0; i < (int)keys.size(); i++) {
    int cnt0 = 0, cnt1 = 0;
    for (Board board : boards)
        (board[i] ? cnt1 : cnt0)++;
    
    // 如果所有配置都同意该灯泡的类型
    if (cnt0 && cnt1) continue;
    
    if (!cnt0) {  // 所有配置都认为该灯泡是垂直的
        knownX[keys[i].first] = keys[i].second;
        unknownX.erase(find(unknownX.begin(), unknownX.end(), keys[i].first));
    }
    
    if (!cnt1) {  // 所有配置都认为该灯泡是水平的
        knownY[keys[i].second] = keys[i].first;
        unknownY.erase(find(unknownY.begin(), unknownY.end(), keys[i].second));
    }
    
    // 移除已确定的灯泡
    keyId[keys[i].first][keys[i].second] = -1;
    keys.erase(keys.begin() + i);
    // ... 更新其他数据结构
}

6. 终止条件

当所有行或所有列都确定时，可以输出答案：

if (unknownX.empty()) {
    printf("!\n");
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++)
            printf("%d", knownX[x] == y);
        printf("\n");
    }
    return 0;
}

计算函数详解

auto calculate = [&](Board board, Board enable, bool useKnownX, bool useKnownY) {
    vector<int> x(n), y(n);
    
    // 根据配置设置行和列的覆盖
    for (int i = 0; i < (int)keys.size(); i++)
        if (enable[i])
            (board[i] ? x[keys[i].first] : y[keys[i].second]) = 1;
    
    // 加入已知的覆盖
    for (int i = 0; i < n; i++) {
        if (useKnownX && knownX[i] != -1) x[i] = 1;
        if (useKnownY && knownY[i] != -1) y[i] = 1;
    }
    
    // 计算被照亮的格子数
    int cntX = 0, cntY = 0;
    for (int i : x) cntX += i;
    for (int i : y) cntY += i;
    
    return (cntX + cntY) * n - cntX * cntY;  // 容斥原理
};

算法优势

1. 信息论优化：每次实验最大化信息熵，快速缩小可能配置的空间
2. 概率推理：维护所有可能的配置，逐步消除不一致的假设
3. 自适应策略：根据当前知识状态动态选择最佳实验
4. 资源控制：通过限制 boards.size() < 1024 避免状态爆炸

复杂度分析

• 空间复杂度：最多维护 1024 个配置，每个配置用 200 位表示
• 时间复杂度：每次实验设计需要 $O(64 \times 1024 \times N)$ 计算
• 实验次数：通常远少于 2000 次，可以满足题目要求