CodeForces 1017B-The Bits

秒速五厘米 2022-05-17 11:51 131阅读 0赞

*  # CodeForces 1017B-The Bits #

--------------------

*  ## 题目链接：[B. The Bits][] ##
 *  ## 思路： ##

题目大意是给两个位数相同的二进制数a，b，**交换a中两位**，问有多少种交换方式，使得a，b的或运算结果改变。

按或运算的性质，交换a中的两位，如果b对应位置为1，那么无论怎么交换该位是始终为1的，所以要改变，只能b在该位为0

这样只要处理两种情况，**1 \[ a 0 b 1 \]**   **2\[ a 1 b 1\]**

![70][]

**对于第一种情况，Str1中 位=0 的都满足要求**

**对于第二钟情况，只有当Str1\[j\] = Str2\[j\] = 1 才能让或运算结果改变（因为Str\[i\]=0,Str\[j\]=1 这种情况在①中已经交换过，不能重复)**

两种情况的交换方案之和就是结果啦

对Str1，Str2进行预处理，统计Str1中 0的个数，统计Str1\[i\] = Str\[i\] = 1 的个数

*  ## 代码： ##

#include<iostream>
    using namespace std;
    
    #define Max_Size 100005
    
    char Str1[Max_Size], Str2[Max_Size];
    
    int Len;
    long long Change_Time;   //Wa的原因：原先用int，后来发现数据很大
    int main()
    {
    	Change_Time = 0;
    	int Zero_num_1 = 0;
    	int One_num_2 = 0;
    	cin >> Len;
    	cin >> Str1 >> Str2;
    	for (int i = 0; i < Len; i++)
    	{
    		if (Str1[i] == '0')
    			Zero_num_1++;
    		if (Str1[i] == '1'&&Str2[i] == '1')
    			One_num_2++;
    	}
    	
    	for (int i = 0; i < Len; i++)
    	{
    		if (Str2[i] == '0')
    		{
    			if (Str1[i] == '1')
    				Change_Time += Zero_num_1;
    			else
    				Change_Time += One_num_2;
    		}
    	}
    	cout << Change_Time << endl;
    	return 0;
    }

*  ## 我踩的坑： ##

一开始结果没有定义成long long，结果Error in 7，数据很大！！！

下午一直被卡，原因是我是按冒泡逐个扫，结果超时了，没救

*  ### 附上我WA的代码： ###

#include<iostream>
    #include<cstdio>
    using namespace std;
    #define MAX_Length 100005
    int len;
    char Str1[MAX_Length],Str2[MAX_Length];
    
    int main()
    {
        cin>>len;
        scanf("%s",Str1);
        scanf("%s",Str2);
        int Time=0;
        for(int i=0;i<len-1;i++)
        {
            for(int j=i+1;j<len;j++)
            {
                if(Str1[i]==Str1[j])
                    continue;
                else
                {
                    if(Str2[i]=='1'&&Str2[j]=='1')
                        continue;
                    //cout<<i+1<<" "<<j+1<<endl;
                    Time++;
                }
            }
        }
        cout<<Time<<endl;
    }

*  ### WA的思路： ###

要论思路简单肯定是我这个（理不直气也壮），梯度循环（看代码，我意淫的循环方式），如果两个位相等，没必要交换。不相等时，如果Str2中对应两位都是1，也没必要交换，其他情况交换了都会改变或运算结果。

[B. The Bits]: http://codeforces.com/problemset/problem/1017/B
[70]: /images/20220517/a2899a8ed6664b0a8efe656d210f9f9c.png