题解 CF922B【Magic Forest】

zljhenry · 2021-05-03 15:54:00 · 题解

先来解释一下题义：

• 这个东西的意思是按位比较，如果相同，值是0；不相同，值是 1 。

那么就可以写一个暴力了：

#include<bits/stdc++.h>
using namespace std;
int main(){
   //freope(".in","r",stdin);
   //freope(".out","w",stdout);
   int n;
   cin>>n;
   int ans=0;
   for(int a=1;a<=n;a++){
      for(int b=a;b<=n;b++){
         for(int c=b;c<=n;c++){//三重循环枚举
            int m=a^b^c;
            if(m==0&&a+b>c&&a+c>b&&b+c>a)ans++；
         }
      }
   }
   cout<<ans;
   //fclose(stdin);fclose(stdout);
   return 0;
}

没想到竟然 AC 了。。。

但还能不能再优化呢？

我们发现 a 异或 b 那个数肯定和 a 异或为0，和 b 异或为0 。

所以我们就可以去掉一层循环，然后把 c 表示出来。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
   //freope(".in","r",stdin);
   //freope(".out","w",stdout);
   int n;
   cin>>n;
   int ans=0;
   for(int a=1;a<=n;a++){
      for(int b=a;b<=n;b++){
         if(a^b==0){
            int c=a^b;
            if(a+b>c&&a+c>b&&b+c>a&&c>=b&&c<=n){
               cout<<a<<' '<<b<<' '<<c<<endl;
               ans++;
            }
         }
      }
   }
   cout<<ans;
   //fclose(stdin);fclose(stdout);
   return 0;
}