[Codeforces 1017.D] The Wu（位运算，meet in the middle）

Posted on | In ,
Codeforces 1017D

题目

链接

解题思路

观察数据范围，发现 $n\leqslant 12$，即最多有 $2^{12}=4096$ 种字符串，所以输入的 $s$ 和 $t$ 肯定有很多重复的。
那么可以先预处理出 $4096\times 4096$ 的所有情况的”Wu value”，又由于 $k \leqslant 100$，再预处理出所有的答案，询问时 $O(1)$ 回答即可。
算一下复杂度：$O(n\cdot 2^n\cdot 2^n + 2^n\cdot k) \approx O(2e8)$，这道题时间限制2s，好像可以卡过——事实上是，codeforces评测机太快了，用时最多的点仅有592ms。$qwq$

可是追求卓越的我们并不甘心就此止步，于是 meet in the middle 再度粉墨登场。
观察上面的复杂度，发现 $4096\times 4096=16777216$，只不过再乘以一个 $n$ 就变成 $2e8$了，所以可以想办法不乘 $n$。预处理出一半长度的字符串，最多 $2^6=64$ 种，然后再用这 $64$ 种情况预处理 $4096\times 4096$ 所有情况即可。
复杂度 $O(\frac{n}{2}\cdot 2^{\frac{n}{2}}\cdot 2^{\frac{n}{2}} + 2^n \cdot 2^n + k\cdot 2^n) \approx O(2e7)$
（好吧，再加点常数） codeforces 上最多389ms

Code

Code#1 O(2e7)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<bits/stdc++.h>

using namespace std;

#define fo0(i,a,b) for(int i=(a);i<(b);i++)
#define fo1(i,a,b) for(int i=(a);i<=(b);i++)
#define fd0(i,a,b) for(int i=(a);i>(b);i--)
#define fd1(i,a,b) for(int i=(a);i>=(b);i--)
//此处省略 define 的一些东西和读入输出优化

int n, m, q, k, w[20], v1[70][70], v2[70][70], val, cnt[4100], ans[4100][105];
char s[20];

inline int trans(char s[]){
	int res = 0;
	fd1(i, n, 1)	res = (res << 1) + s[i] - '0';
	return res;
}

int main(){
	in(n); in(m); in(q);
	fo0(i, 0, n)	in(w[i]);
	fo1(i, 1, m){
		scanf("%s", s+1);
		cnt[trans(s)]++;
	}
	fo0(i, 0, 1 << (n/2))
		fo0(j, 0, 1 << (n/2))
			fo0(b, 0, n/2){
				v1[i][j] += w[b] * ((i>>b&1) == (j>>b&1));
				v2[i][j] += w[b+(n+1)/2] * ((i>>b&1) == (j>>b&1));
			}
	fo0(i, 0, 1 << n){
		fo0(j, 0, 1 << n){
			int t = (1 << (n / 2)) - 1;
			val = v1[i&t][j&t] + v2[i>>((n+1)/2)][j>>((n+1)/2)];
			if(n & 1)	val += w[n/2] * ((i>>(n/2)&1) == (j>>(n/2)&1));
			if(val <= 100)	ans[i][val] += cnt[j];
		}
	}
	fo0(i, 0, 1 << n)
		fo1(j, 1, 100)
			ans[i][j] += ans[i][j-1];
	while(q--){
		scanf("%s", s+1);
		in(k);
		outln(ans[trans(s)][k]);
	}
	return 0;
}

Code#2 O(2e8)

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
38
39
40
41
42
43
44
45

#include<bits/stdc++.h>

using namespace std;

#define fo0(i,a,b) for(int i=(a);i<(b);i++)
#define fo1(i,a,b) for(int i=(a);i<=(b);i++)
#define fd0(i,a,b) for(int i=(a);i>(b);i--)
#define fd1(i,a,b) for(int i=(a);i>=(b);i--)
//此处省略 define 的一些东西和读入输出优化

int n, m, q, k, w[20], val, cnt[4100], ans[4100][105];
char s[20];

inline int trans(char s[]){
	int res = 0;
	fd1(i, n, 1)	res = (res << 1) + s[i] - '0';
	return res;
}

int main(){
	in(n); in(m); in(q);
	fo0(i, 0, n)	in(w[i]);
	fo1(i, 1, m){
		scanf("%s", s+1);
		cnt[trans(s)]++;
	}
	fo0(i, 0, 1 << n){
		fo0(j, 0, 1 << n){
			val = 0;
			fo0(b, 0, n)
				val += w[b] * ((i>>b&1) == (j>>b&1));
			if(val <= 100)	ans[i][val] += cnt[j];
		}
	}
	fo0(i, 0, 1 << n)
		fo1(j, 1, 100)
			ans[i][j] += ans[i][j-1];
	while(q--){
		scanf("%s", s+1);
		in(k);
		outln(ans[trans(s)][k]);
	}
	return 0;
}