题解：B4175 [BCSP-X 2024 6 月初中组] 打孔纸带

· · 题解

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

0\operatorname{and}0=0 0\operatorname{and}1=0 1\operatorname{and}1=1 0\operatorname{or}0=0 0\operatorname{or}1=1 1\operatorname{or}1=1 0\operatorname{xor}0=0 0\operatorname{xor}1=1 1\operatorname{xor}1=0

由此可知！如果只有两个 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 代码。最后这道题综合算法难度、思维难度、代码量等因素来看，建议评橙。