题解：P8766 [蓝桥杯 2021 国 AB] 异或三角

原题传送门

思路

我们先假设

a>b>c

，由

a \oplus b \oplus c=0

我们可得

a=b \oplus c

。又因

a

，

b

，

c

可构成三角形，所以

a<b+c

，联系

a=b \oplus c

，所以

b \oplus c<b+c

，那么

b

和

c

在二进制下一定有一位都为

1

。所以我们运用状压的思想，将

a>b

，

b > c

以及

b

和

c

在二进制下一定有一位都为

1

化作三种状态判断即可。

代码

CPP

#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int T , dp[60][2][10] , a[60] , n , pos;
inline int dfs(int nows , int zt , bool flag) {
	if(!nows) return zt == 7;
	if(dp[nows][flag][zt] != -1) return dp[nows][flag][zt];
	int maxx = flag ? a[nows] : 1 , tmp = 0;
	if(maxx >= 0) tmp += dfs(nows - 1 , zt , (flag && a[nows] == 0));
	if(maxx >= 0 && (zt & 1) && (zt >> 1 & 1)) tmp += dfs(nows - 1 , zt | 4 , (flag && a[nows] == 0));
	if(maxx == 1) {
		tmp += dfs(nows - 1 , zt | 2 , (flag && a[nows] == 1));
		tmp += dfs(nows - 1 , zt | 1 , (flag && a[nows] == 1));
	}
	dp[nows][flag][zt] = tmp;
	return tmp;
}
inline int work(int x) {
	pos = 0;
	while(x) {
		a[++pos] = x & 1;
		x >>= 1;
	}
	return dfs(pos , 0 , 1) * 3;
}
inline void solve() {
	memset(dp , -1 , sizeof(dp));
	n = read();
	cout << work(n) << endl;
}
signed main(){
	T = read();
	while(T--) solve();
	return 0;
}

注意事项：

这里的

dp

数组一定要开三维，把当前位是否有限制加进去，不然会 T 飞。

题解：P8766 [蓝桥杯 2021 国 AB] 异或三角

文章操作

原题传送门

思路

代码

注意事项：

相关推荐

评论

题解：P8766 [蓝桥杯 2021 国 AB] 异或三角