2018牛客多校07 C Bit Compression (DP)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.nowcoder.com/acm/contest/145/C

一个长度为$2^n$的01串，每次允许相邻两个数字进行与、或、异或操作，最终希望结果是1，问有多少种不同的操作路径。

$f(i,j)$表示01串从$2^n$开始，扫到长度为$2^i$时，01串变为j时的路径数，用一个map来记录状态，然后暴力dp转移到下一层就行。整体复杂度是$O(2^nn)$，可以过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

const int maxn = 300200;
int n;
char s[maxn];
map<string,int> f[22];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d",&n)) {
    scanf("%s", s);
    for(int i = 0; i < 22; i++) f[i].clear();
    string tmp;
    int tot;
    f[n][s] = 1;
    map<string,int>::iterator it;
    string a, b, c;
    for(int i = n; i >= 1; i--) {
      for(it = f[i].begin(); it != f[i].end(); it++) {
        tmp = it->first, tot = it->second;
        int nn = (1 << i);
        a = b = c = "";
        for(int j = 0; j < nn; j+=2) {
          a += ((tmp[j]-'0') & (tmp[j+1]-'0')) + '0';
          b += ((tmp[j]-'0') | (tmp[j+1]-'0')) + '0';
          c += ((tmp[j]-'0') ^ (tmp[j+1]-'0')) + '0';
        }
        f[i-1][a] += tot;
        f[i-1][b] += tot;
        f[i-1][c] += tot;
      }
    }
    printf("%d\n", f[0]["1"]);
  }
  return 0;
}