[蓝桥杯][基础练习VIP]芯片测试

忍不住说在前面，其他做法都是错的！！！ 题目

题目链接

题解

二进制枚举。

纠正他人博客错误

错误做法：网上全部。 正确做法：二进制枚举。

这篇博客，我写了两遍，第一遍是因为觉得自己的思路没有问题却过不了，而那些错误思路的却过了，导致第一篇写的非常激动，脏话满篇；我写博客生气的时候，无意发现了一个小细节错了，之后改过来就AC了，心情好多了，就重写一篇，不骂他们了。

先说明一下为什么网上的都是错的，最起码百分之90吧都是错的。 题目给的n=20的数据量不是让你用O(n^2)的算法解决的！！！ 很多博客都是两重循环搞定，那些思路就是误导人的，没有一点自己的见解，看到别人思路什么样就直接copy思路，最终博客全是错误做法，居然没有一个人出来指正？？？

举这个例子：

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

正确答案是无解。 网上的AC代码都是输出2 3。首先输出2 3也不满足“已知好芯片比坏芯片多”啊，而且，你看看2 3是好芯片这能对么？？？

越想越奇怪，为什么会所有人都一个思路，还都是错误思路，虽然能AC，但是真没人用其他思路？很离谱。

正确思路

我采用的是二进制枚举的方法。

二进制的每一位0 1分别代表一个芯片的坏与好；对于n=20的数据规模，总情况数为2^20 = 1024*1024，1e6左右。

对于枚举的每一种情况，我们找出好的芯片，遍历好的芯片对于其他芯片的检测，是否与咱们枚举的情况一致，只有当我们枚举的这种情况中的全部好芯片对其他芯片的检测都与当前枚举的情况一致，才能说明枚举的这个情况是正确的。

看不懂啥意思？看举例吧。 还是这个例子

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

网上答案是2 3是好芯片，那么也就是说芯片2对其他芯片的检测是对的，芯片3对其他芯片的检测也是对的。芯片2对芯片1的检测表明芯片1是坏的，而芯片3对芯片1的检测表明芯片1是好的，这部矛盾嘛。

假设我现在枚举到的状态是0110从左至右表示1~4号芯片，判断当前情况是否为可行情况（先不保证“好>坏”）。只有当我们枚举的0110与第二行一致且与第三行一致时才能说明0110可行。也就是说好芯片对其他芯片的检测必须也要满足枚举的状态。

如果我们将第三行的第一个，即芯片3对芯片1的检测改为0：

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

此时芯片2和芯片3就可以是好芯片，但是若加上“好芯片的数量大于坏芯片的数量”的条件，仍不能看作是正确答案。所以还是无解。

代码

#include
using namespace std;

int n, a[30][30], b[30], s[30];

int main()
{
	cin>>n;
	for(int i = 1;i a[i][j];
	
	int m = (1