UOJ Logo SocietyNiu的博客

博客

高一T2真题解

2018-08-28 13:31:25 By SocietyNiu

由于我的失误,题解放早了十几分钟,导致有些同学抄袭,在这里我不再追究,请大家弄清楚题解后自己打一遍,本身题目不难。 还有考试时没有网,导致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;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。