2020牛客寒假算法基础集训营3 B 牛牛的DRB迷宫II
https://ac.nowcoder.com/acm/contest/3004/B
利用二进制进行构造
假设一个方形迷宫，主对角线都是B，B上面一个位置是D，其余位置都是R
那么到第i行第i列的方案数就是2^i
所以方案数的二进制形式，如果第i位是1，那就需要第i行第i列这一格的贡献
将这一格下面的一个格改为B，这一列这一格下面剩下的都改成D
在方形迷宫的基础上，最后面再加一行，全都是R
这样上面的‘D’就能将2^i的贡献下传到最后一行，最后一行通过‘R’传到最后一个格子
#include<cstdio> using namespace std; #define N 31 int bit[N]; char a[N][N]; int main() { int n,m=0; scanf("%d",&n); if(!n) { printf("1 2 DD"); return 0; } while(n) bit[m++]=n&1,n>>=1; for(int i=0;i<=m;++i) for(int j=0;j<m;++j) a[i][j]='R'; for(int i=0;i<m;++i) { a[i][i]='B'; if(i) a[i-1][i]='D'; } for(int i=0;i<m;++i) if(bit[i]) { a[i+1][i]='B'; for(int j=i+2;j<m;++j) a[j][i]='D'; } printf("%d %d ",m+1,m); for(int i=0;i<=m;++i) printf("%s ",a[i]); return 0; }