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

YZren · 2025-04-08 21:06:13 · 题解

题目传送门

一道有难度的数位 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

#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");}