自动搬运

查看原文

来自洛谷，原作者为

	wbqhasvcf 为了你唱下去，为你将希冀传递

搬运于2025-08-24 21:17:35，当前版本为作者最后更新于2025-03-04 21:21:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先将问题简化成给定若干个长度为 $1$ 的纸带（即纸带上的数非 $0$ 即 $1$），看何种情况下可以确定机器对于长度为 $1$ 的二进制数的运算逻辑。为了更清晰地思考，首先罗列出来 $0$ 和 $1$ 的所有位运算情况与结果：

由此可知！如果只有两个 $0$，吐出来的只能是 $0$，根本无法确定是哪种运算；如果有一个 $0$ 和一个 $1$，机器吐出 $1$ 就无法确定是 $\operatorname{or}$ 运算还是 $\operatorname{xor}$ 运算；如果有两个 $1$，同理机器吐出 $1$ 就死翘翘了，无法确定是 $\operatorname{and}$ 运算还是 $\operatorname{or}$ 运算。

由于可以无数次塞纸带，所以很明显，第二、三种情况可以优势互补。即如果至少有一个 $0$ 和两个 $1$ 就完全可以确定机器的运算逻辑！（此句是金句，也是本题的AC要点）这个结论的证明很好想，只要塞两次纸条，一次塞 $0$ 和 $1$，一次塞 $1$ 和 $1$，先吐出 $0$ 就一次确定是 $\operatorname{and}$ 运算了，先吐出 $1$ 后吐出 $1$ 可确认是 $\operatorname{or}$ 运算，否则后吐出 $0$ 可确认是 $\operatorname{xor}$ 运算。

所以如果我们有且仅有 $0$，还差两个 $1$，至少需要再制作两张纸带；有至少一个 $0$ 并有且仅有一个 $1$，还差一个 $1$，至少需要再制作一张纸带；有且仅有 $1$ 的话也至少需要再制作一张纸带，因为只有 $1$ 管够是不够的，还差一个 $0$；有至少一个 $0$ 和至少两个 $1$，就不需要制作纸带。

这仅仅是对于纸带长度全为 $1$ 的情况的分析。如果长度为 $n$，那么按照上面的逻辑逐个分析每一位，只需要先求出第 $i$ 位至少需要制作多少个纸带，记为 $a_{i}$（由上述分析可知 $a_{i}$ 只可能是 $2$ 或 $1$ 或 $0$），再取所有 $a_{i}$ 的最大值，即为最终至少需要制作的纸带数。

这就是正解思路了，本题正常 AC 代码时间复杂度应为 $O(n)$，难点仅在于思路分析，下面展示本人的参考代码，还是相当简洁清晰易懂的：

#include<iostream>
using namespace std;

int n,cnt1[105],ans;
string s;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		for(int j=0;j<s.size();j++)
		    cnt1[j]+=(s[j]=='1');//《爱缩行の屑鄙人》 
	}
	for(int i=0;i<s.size();i++)
	    if(cnt1[i]==1||cnt1[i]==n)//注意此处还要判断是否第i位上全都是1，即根本没有0，这种情况下需要再制作一个纸带，不加此判断会得90分 
	        ans=max(ans,1);
	    else if(cnt1[i]==0)
	        ans=2;
	cout<<ans;
	return 0;
}

后记：本题为 BCSP-X 上半年复赛初中组第二题，你以为我跟第一题“厂房”一样赛时 A 了，其实我没有，恰相反我赛时爆零了！！！因为当时题根本没看懂，题意理解错了。所以其实这道题的题意描述有点儿问题，容易引发歧义，我也是赛后调试好的 AC 代码。最后这道题综合算法难度、思维难度、代码量等因素来看，建议评橙。