【蓝桥杯每日一题】3.17

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();

        for(int st = 0; st < (1 << n); st++)
        {
            vector<int> tmp;
            for(int i = 0; i < n; i++)
            {
                if((st >> i) & 1) tmp.push_back(nums[i]); 
            }
            ret.push_back(tmp);
        }
    return ret;
    }
};

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10;

int a[N], t[N];

int calc(int push)
{
	int cnt = 0;
	while (push)
	{
		cnt++;
		push &= (push - 1);
	}
	return cnt;
}

int main()
{
	int n; cin >> n;
	while (n--)
	{
		// 清空上一组的数据
		memset(a, 0, sizeof a);
		// 输入数据，每一排用十进制数字存储二进制
		for (int i = 0; i < 5; i++)
		{
			for (int j = 0; j < 5; j++)
			{
				char ch; cin >> ch;
				if (ch == '0') a[i] |= (1 << j);
			}
		}

		int ret = 0x3f3f3f3f;
		// 枚举第一排的情况
		for (int st = 0; st < (1 << 5); st++)
		{
			memcpy(t, a, sizeof a);
			int push = st;
			int cnt = 0; // 记录按了几次

			for (int i = 0; i < 5; i++)
			{
				cnt += calc(push);
				t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);
				t[i] &= (1 << 5) - 1; // 清除影响

				t[i + 1] ^= push; // 修改下一行的状态
				push = t[i];
			}

			if (t[4] == 0) ret = min(ret, cnt);
		}
		if (ret > 6) cout << "-1" << endl;
		else cout << ret << endl;
	}

	return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n;
int a[N]; // ⽤⼆进制存储状态
int t[N]; // 备份

// 判断 x->y 是否合法
// 返回 -1，表⽰不合法
// 其余的数，表⽰合法，并且表⽰ 0->1 的次数
int calc(int x, int y)
{
	int sum = 0; for (int i = 0; i < n; i++)
	{
		if (((x >> i) & 1) == 0 && ((y >> i) & 1) == 1) sum++;
		if (((x >> i) & 1) == 1 && ((y >> i) & 1) == 0) return -1;
	}
	return sum;
}
int solve()
{
	int ret = 0x3f3f3f3f; // 记录最⼩的改变次数
	// 枚举第⼀⾏的最终状态
	for (int st = 0; st < (1 << n); st++)
	{
		memcpy(t, a, sizeof a);
		int change = st;
		int cnt = 0; // 统计 0->1 的次数
		bool flag = 1;
		for (int i = 1; i <= n; i++)
		{
			// 先判断 change 是否合法
			int c = calc(t[i], change);
			if (c == -1)
			{
				flag = 0;
				break;
			}
			cnt += c; // 累加次数
			// 当前⾏的最终状态
			t[i] = change;
			// 计算下⼀⾏的最终状态
			change = t[i - 1] ^ (t[i] << 1) ^ (t[i] >> 1);
			change &= (1 << n) - 1;
		}
		if (flag) ret = min(ret, cnt);
	}
	if (ret == 0x3f3f3f3f) return -1;
	else return ret;
}

int main()
{
	int T; cin >> T;
	for (int k = 1; k <= T; k++)
	{
		// 多组测试数据，记得清空
		memset(a, 0, sizeof a);
		cin >> n;
		for (int i = 1; i <= n; i++) // 避免越界访问
		{
			for (int j = 0; j < n; j++)
			{
				int x; cin >> x;
				if (x) a[i] |= 1 << j;
			}
		}
		printf("Case %d: %d\n", k, solve());
	}
	return 0;
}