题解 - P15434 [蓝桥杯 2025 国 Python B] 三角形构造

这题挺好的。

题目说三角形边长需分别为 $x,y,x|y$，所以想到满足 $x+y>x|y$ 或 $x+(x|y)>y$ 或 $y+(x|y)>x$ 就能拼出非退化的三角形了。

但是一看数据范围，枚举 $y$ 是 $O (x)$ 的时间复杂度，肯定超时了，所以最可能提升效率的方法是利用按位或的性质。易得对于任意的正整数 $a,b$，满足 $a,b \le a|b \le a+b$ 而且 $a|b=a+b$ 时 $a$ 正好为 $b$ 按位取反后的值。所以只需满足 $x+y<x|y$ 就能构造三角形，所以 $x,y$ 的二进制中至少有 $1$ 位相同，要找所有满足该条件的 $y$。

这是经典的排列组合。设 $x,y$ 二进制第 $i$ 位分别为 $x_i,y_i$，$cx$ 为 $x$ 的二进制中 $1$ 的个数。要使 $x+y=x|y$，$x_i=1$ 时 $y_i=0$，$x_i=0$ 时 $y_i \in \{0,1\}$。利用乘法原理，不能构造三角形方案数为 $2^{cx}-1$。最后减 $1$ 是因为不能让 $y$ 二进制每一位都为 $0$，否则不满足 $1 \le y$。以上是使 $x+y=x|y$ 的方案数，答案即 $x-2^{cx}+1$，时间复杂度 $O(\log x)$。

#include<bits/stdc++.h> #define int long long using namespace std; string to2(int num) { string ans; while(num) { ans+=num%2+'0'; num/=2; } reverse(ans.begin(),ans.end()); return ans; } signed main() { int x,cnt=0; cin>>x; string xs=to2(x);//转二进制 for(int i=0;i<xs.size();i++) if(xs[i]=='0')cnt++; cout<<(x-(int)pow(2,cnt)+1);//排列组合 return 0; }