由于我的失误,题解放早了十几分钟,导致有些同学抄袭,在这里我不再追究,请大家弄清楚题解后自己打一遍,本身题目不难。 还有考试时没有网,导致markdown的图例没有显示,对大家说一句抱歉
首先要了解:^
运算符优先级低于==
知道这个,其实已经50分到手了(是不是特别水)
//50分代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
if((i^j^k)==0)//```^```运算符优先级低于```==```,所以要加i^j^k括号
if(i+j>k&&i+k>j&&k+j>i)
sum++;
cout<<sum;
}
可是这个方法时间复杂度为O(n^3)
,过不了2500以上的数据。这时就要优化
假设我只枚举a和b,那么如何求c呢?
首先我们要推出异或的一个运算法则,a^b^c=(a^b)^c
知道这个后,我们就可以进行胡搞推导.
题目要求a^b^c==0
,即(a^b)^c==0
,根据异或的运算法则可知(a^b)
与c
按位相等,二进制上每一位都是一样的,所以(a^b)==c
这时候就可以枚举了啊(属实不难啊)
代码如下
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
int k=(i^j);
if(i+j>k&&i-j<k)
if(k<j&&k<i)
sum++;
}
cout<<sum;
}