Bit Compression 两种解决方案 O(∩_∩)O哈哈~
题目链接
作者：rhapHsody
方法一（暴力）：这题很容易看出来是个典型的dfs题，只要注意剪枝（把结果一定为0的情况进行剪枝）就能过,下面是代码：
#include
using namespace std;
bool a[1 <>= 1; bool b[n]; int ans = 0, h1 = 0, h2 = 0, h3 = 0;
for(int i=0;i<n;++i)h1+=b[i]=(s[i<<1]&s[i<<1|1]); if(h1)ans+=dfs(n,b);
for(int i=0;i<n;++i)h2+=b[i]=(s[i<<1]|s[i<<1|1]); if(h2)ans+=dfs(n,b);
for(int i=0;i<n;++i)h3+=b[i]=(s[i<<1]^s[i<<1|1]); if(h3)ans+=dfs(n,b);
return ans;
}
int main() {
int n; scanf("%d%*c", &n);
for(int i=0;i<(1<<n);++i) a[i]=getchar()-'0';
printf("%d\n", dfs(1 << n, a));
return 0;
}
方法二（非暴力）: 对dfs进行记忆优化，用数位dp求得二进制颠倒排序，高精度压位防止数据溢出等。（速度要比暴力法快很多）代码如下:
#include
using namespace std;
const int N = 1 << 18;
int a[N], pos[N], b[N];// a存储输入串，pos存储序列，b存储记忆化
unsigned c[N], d[N];// c存储高精度压位，d存储过程临时数据
void Bitsort(int n) { // 数位dp
for(int i = 0; i <= (1 <>1]>>1|(i&1)<>= 1;
int x = last, y = last >> n;
return pre(n,x&y)+pre(n,x|y)+pre(n,x^y);
}
int dfs(int n, unsigned* last, unsigned* next) { // dfs
if (n == 1 ) return last[0] & 1;
if (n == 16) return b[last[0] & 0xffff];
int ans = 0;
if (n > 32){
int temp = n / 64;
for(int i = 0; i < temp; ++i) next[i] = last[i] & last[i+temp];
ans += dfs(n / 2, next, next + temp);
for(int i = 0; i < temp; ++i) next[i] = last[i] | last[i+temp];
ans += dfs(n / 2, next, next + temp);
for(int i = 0; i > n / 2;
next[0] = x & y;
ans += dfs(n / 2, next, next + 1);
next[0] = x | y;
ans += dfs(n / 2, next, next + 1);
next[0] = x ^ y;
ans += dfs(n / 2, next, next + 1);
}
return ans;
}
int main() {
int n;
scanf("%d%*c", &n);
/********************************
二进制颠倒排序
以二进制颠倒序列输入
高精度压位(以二进制32位 -> 十进制)
在进行深搜前对n=4,进行记忆化
***********************************/
Bitsort(n);
for(int i=0;i<1<<n;++i) a[pos[i]]=getchar()-'0';
for(int i=0;i<1<<n;++i) c[i/32]|=(unsigned)a[i]<<(i%32);
for(int i=0;i<1<<16;++i) b[i]=pre(16,i);
printf("%d\n", dfs(1 << n, c, d));
return 0;
}
作者：rhapHsody
