~~一道有难度的数位 DP，感觉比一些紫题还难。~~

思路

可以发现 $a,b,c$ 没有顺序，所以令 $a>b$ 并且 $a>c$ 最后答案乘三即可。
引用状压的思想，用二进制表示状态，其中令 $1$ 表示 $a>b$ 然后 $10$ 表示 $a>c$ 接着 $100$ 表示 $a,b,c$ 构成三角形。
其中关于证明 $a,b,c$ 是否可以构成三角形，理由如下：根据三角形性质得 $a<b + c$ 其中 $a$ 是最大的，所以 $a=b \oplus c$ 即 $b \oplus c=b + c$ 易证 $b,c$ 的二进制数至少有一位同为一，所以只要 $b,c$ 至少有一位同为一就是三角形。

Code

CPP

#include<bits/stdc++.h>
#define int long long
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
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;
}
inline void write(int x){
	if(x<0) {x=~(x-1); putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int T=read(),dp[2][40][8],loc[40],cnt;
inline int dfs(int pos,int vis,int st){
	if(!pos) return st==7;
	if(dp[vis][pos][st]!=-1) return dp[vis][pos][st];
	int nex=vis?loc[pos]:1,res=0;
	res+=dfs(pos-1,vis&&nex==0,st);
	if((st&1)&&(st>>1&1)) res+=dfs(pos-1,vis&&nex==0,st|4);
	if(nex==1) res+=dfs(pos-1,vis,st|1)+dfs(pos-1,vis,st|2);
	return dp[vis][pos][st]=res;
}
inline void get(){
	int x=read(); cnt=0; memset(dp,-1,sizeof(dp));
	while(x) loc[++cnt]=x&1,x>>=1;
	write(dfs(cnt,1,0)*3); puts("");
}
inline void work(){while(T--) get();}
signed main(){work();return !!!!!("YZren");}

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

文章操作

思路

Code

相关推荐

评论

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