Codeforces Round #461 (Div. 2)B-Magic Forest+位运算或优雅的暴力

题意：就是在1 ~ n中找三个值，满足三角形的要求，同时三个数的异或运算还要为0；

, where denotes the bitwise xor of integers x and y.

我已开始没想到a^b^c=0相当于c = a^b;

这样的转化就可以是三次的变成二次的；

#include <cstdio>

#include <algorithm>

#include <iostream>

using namespace std;

int dp[];

int main(){

    int ans =;

    int n;

    scanf("%d",&n);

    for(int i=; i<=n; i++)

    {

        for(int j = i+; j<=n; j++)

        {

            int k = i^j;

            if(k<i+j && i<j+k && j<i+k && k<=n && k>j)

                ans++;

        }

    }

    printf("%d\n",ans);

    return ;

}

当然用三次的循环也是没问题的；

但是 K 要求在j+1,i+j间循环就ok；

#include <cstdio>

#include <algorithm>

#include <iostream>

using namespace std;

int dp[];

int main(){

    int ans =;

    int n;

    scanf("%d",&n);

    for(int i=; i<=n; i++)

    {

        for(int j = i+; j<=n; j++)

        {

            for(int k = j+; k<=min(n,i+j); k++)

            {

                if(i+j<=k)continue;

                //if(i==3&&j==5&&k==6)cout<<1<<endl;

                if((i^j^k)==)ans++;

            }

        }

    }

    printf("%d\n",ans);

    //printf("%d\n",3^5^6);

    return ;

}

巴特西

Codeforces Round #461 (Div. 2)B-Magic Forest+位运算或优雅的暴力

最新文章

热门文章