Codeforces 554B「掃房間」題解：字符串頻率統計的巧妙轉化

Codeforces 554B「掃房間」題解：字符串頻率統計的巧妙轉化

題目大意

• n × n 網格，每格 0（髒）或 1（乾淨）。
• 操作：選擇整列翻轉（0↔1）。
• 目標：最大化全 1 行的數量。
• n ≤ 100，輸出最大全 1 行數。

核心洞察：行等價類不變性

觀察發現：任意兩行若初始狀態完全相同，則無論如何翻轉列，它們始終保持相同（因為列操作對所有行同等作用）。
反之，若最終某些行變為全 1，則它們在初始時刻必須逐列相同。
因此，問題轉化為：找出現頻率最高的行模式（字符串），其頻率即為答案。

算法流程

1. 讀入 n 及 n 行字符串。
2. 用哈希表（或排序+計數）統計每行字符串出現次數。
3. 輸出最大頻率。

C++ 參考實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    unordered_map cnt;
    string row;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> row;
        ans = max(ans, ++cnt[row]);
    }
    cout << ans << '\n';
    return 0;
}

原始 C 實現（教學用）

#include <stdio.h>
#include <string.h>

char a[102][102];

int main() {
    int n, i, j, maxCnt = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%s", a[i]);
    for (i = 1; i <= n; i++) {
        int c = 0;
        for (j = 1; j <= n; j++)
            if (strcmp(a[i], a[j]) == 0) c++;
        if (c > maxCnt) maxCnt = c;
    }
    printf("%d\n", maxCnt);
    return 0;
}

複雜度：O(n² * L)（L=n），n=100 完全可接受。實際工程建議用哈希表降至 O(n * L)。

樣例驗證

輸入:
4
0101
1000
1111
0101

行模式頻率:
0101 → 2
1000 → 1
1111 → 1
答案 = 2 ✓

延伸思考

• 若允許翻轉行而非列？同理，統計列模式頻率。
• 若操作是「翻轉任意子矩陣」？問題變為 NP-hard（等價於最大二部團）。
• 本題本質是不變量識別 + 頻率統計，是競程中常見的「看似複雜操作，實則尋找等價類」套路。

掌握這類「反向思維：從目標狀態反推初始條件」，能化解大量看似無解的構造類問題。