关灯2

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
string ss[1005];
map<string, int> m;
int ans = 0;
// 当前串有 cnt1 个 '1'
// num1 个当前串，num2 个互补串，更新答案
void cal(int cnt1, int num1, int num2)
{
    int cnt0 = n - cnt1;
    int now;
    // 操作当前串的零
    if (k >= cnt0)
    {
        // 当前串全都变成全 ’1' 了，一共变了 num1 个
        // 还有 k-cnt0 次操作机会
        // 可以把 min(k-cnt0, num2) 个互补串，变为 全 '1'
        now = num1;
        now += min(k - cnt0, num2);
        // 还剩这么多次操作：k - cnt0 - min(k - cnt0, num2);
        if (now == n &&
            (k - cnt0 - min(k - cnt0, num2)) % 2 == 1)
            now--;
        ans = max(ans, now);
    }
    // 操作互补串的零
    swap(num1, num2); // 让互补串作为当前串，两种串的数量翻转
    swap(cnt0, cnt1); // 此时当前串的 01 数量刚好和之前相反
    if (k >= cnt0)
    {
        // 当前串全都变成全 ’1' 了，一共变了 num1 个
        // 还有 k-cnt0 次操作机会
        // 可以把 min(k-cnt0, num2) 个互补串，变为 全 '1'
        now = num1;
        now += min(k - cnt0, num2);
        // 还剩这么多次操作：k - cnt0 - min(k - cnt0, num2);
        if (now == n &&
            (k - cnt0 - min(k - cnt0, num2)) % 2 == 1)
            now--;
        ans = max(ans, now);
    }
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            char c;
            cin >> c;
            ss[j] += c;
        }
    for (int i = 1; i <= n; i++)
        m[ss[i]]++;
    ans = 0;
    for (auto now : m)
    {
        // 钦定 now 需要全 1
        string s = now.first;
        int numS = now.second;
        string ss = now.first; // 互补串
        for (int i = 0; i < ss.size(); i++)
            if (ss[i] == '0')
                ss[i] = '1';
            else
                ss[i] = '0';
        int numSS = m[ss];
        int cnt1 = 0;
        for (int i = 0; i < s.size(); i++)
            if (s[i] == '1')
                cnt1++;
        // 处理当前列的情况
        cal(cnt1, numS, numSS);
    }
    cout << ans << "\n";
    return 0;
}

错误代码

hack数据：

4 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

#include <bits/stdc++.h>
using namespace std;
int n, k;
string ss[1005];
map<string, int> m;
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			char c;
			cin >> c;
			ss[j] += c;
		}
	for (int i = 1; i <= n; i++)
		m[ss[i]]++;
	int ans = 0;
	for (auto now : m)
	{
		// 钦定 now 需要全 1
		string s = now.first;
		int num = now.second;
		int nowAns = 0; // 能搞定几个
		int nowCnt = k; // 还要动几次
		for (char c : s)
			if (c == '0')
				nowCnt--;
		if (nowCnt < 0)
			continue;
		nowAns += num;
		// 生成互补串并检查互补串数量
		for (int i = 0; i < s.length(); i++)
			s[i] = 1 - (s[i] - '0') + '0';
		num = m[s]; // 互补串数量
		nowAns += min(nowCnt, num);
		nowCnt -= min(nowCnt, num);
		// 消耗剩余次数
		if (nowAns == n)
			nowAns -= nowCnt % 2;
		ans = max(ans, nowAns);
	}
	cout << ans << "\n";
	return 0;
}