算法训练审美课

àì夳堔傛蜴生んèń 2022-03-02 05:50 156阅读 0赞

算法训练 审美课

时间限制：1.0s   内存限制：256.0MB

问题描述

《审美的历程》课上有n位学生，帅老师展示了m幅画，其中有些是梵高的作品，另外的都出自五岁小朋友之手。老师请同学们分辨哪些画的作者是梵高，但是老师自己并没有答案，因为这些画看上去都像是小朋友画的……老师只想知道，有多少对同学给出的答案完全相反，这样他就可以用这个数据去揭穿披着皇帝新衣的抽象艺术了（支持帅老师^\_^）。  
　　答案完全相反是指对每一幅画的判断都相反。

输入格式

第一行两个数n和m，表示学生数和图画数；  
　　接下来是一个n\*m的01矩阵A：  
　　如果aij=0，表示学生i觉得第j幅画是小朋友画的；  
　　如果aij=1，表示学生i觉得第j幅画是梵高画的。

输出格式

输出一个数ans：表示有多少对同学的答案完全相反。

样例输入

3 2  
1 0  
0 1  
1 0

样例输出

样例说明

同学1和同学2的答案完全相反；  
　　同学2和同学3的答案完全相反；  
　　所以答案是2。

数据规模和约定

对于50%的数据：n<=1000；  
　　对于80%的数据：n<=10000；  
　　对于100%的数据：n<=50000，m<=20。

**题解：只有01两种状态，又要找出不同的对数，就需要用到异或^，异或就是相同为0，不同为1，1^1=0,0^0=0,1^0=1,0^1=1，相当于不进位的加法，这道题给出了最多20位，把它们转换成十进制，在进行异或，标记累加，最后当前出现的数标记累加（为什么要异或？这里这样理解：因为转成十进制后的当前num和要和num完全相反的数组成一队，异或每一位都是1的数就能找到当前num相反的数，如10110^11111=01001     根据异或相当于不进位的二进制加法01001就和10110相反**

#include<bits/stdc++.h>
    using namespace std;
    #define N 2^20 //1048576
    int n,m,a[1048576],ans;
    int main()
    {
        cin>>n>>m;
        int xx=(1<<m)-1;//定义变量所有位全为1
        for(int i=0; i<n; i++)
        {
            int  num=0,x;
            for(int j=0; j<m; j++)
            {
                cin>>x;
                num=num*2+x; //转换成十进制
            }
            ans+=a[xx^num]; //当前num与xx异或，表示当前num和xx^num组成一队完全相反的数，累加到ans上
            a[num]++;		//当前num个数+1
        }
        cout<<ans<<endl;
        return 0;
    }

\------------------------------------------------------------------------------------------------------------------------------------------------------------------------

![20190321210546803.gif][]

![20190321210541386.gif][]

[20190321210546803.gif]: /images/20220302/587227509c8448c1988ccbfea443765a.png
[20190321210541386.gif]: /images/20220302/59c99ab61d454eaaae6c677b9e6dc185.png