Codeforces 1017D(暴力+状压)

Codeforces 1017D
题意:给你$n,m,q$,表示在这一组数据中所有的$01$串长度均为$n$,然后给你一个含有$m$个元素的multiset,之后有$q$次询问。每次询问会给你一个$01$串$t$和一个给定常数$k$,让你输出串$t$和multiset里面多少个元素的$Wu$值不超过$k$。对于$Wu$值的定义:如果两个$01$串$s$和$t$在位置$i$上满足s[i]=t[i],那么加上$w[i]$,处理完$s$和$t$的所有$n$位之后的结果即为这两个$01$串的$Wu$值。

发现本题有$n$和$k$小,那么从这两个下手。$2^n≈4000$很小,我们可以将二进制数两两求$Wu$值之后$O(1)$查询。然后因为$k=100$, 那么我们再开一个二维数组记录某个二进制数能与multiset里面的元素组成某值的个数。这个状态非常好用。

知识点:
1、这种题目数据范围小是突破点。
2、写完程序要核对自己想的复杂度和实现是否有差异。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, m, q, wi[20], bs[500000 + 5], whw[20], gg[5005][1205], tax[5005], xmx[5005];
void clean() {
ms(xmx, 0), ms(tax, 0), ms(bs, 0);
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &wi[i]);
whw[0] = 1;
for (int i = 1; i <= 13; i++) whw[i] = whw[i - 1] * 2;
char s[20];
for (int len, i = 1; i <= m; i++) {
scanf("%s", s); len = strlen(s);
for (int j = len - 1; j >= 0; j--) bs[i] += whw[len - 1 - j] * (s[j] - '0');
tax[bs[i]]++;
}//mn
std::bitset<20 > bs;
for (int i = 0; i < (1 << n); i++) {
bs = i;
for (int j = 0; j < n; j++) if (!bs[j]) xmx[i] += wi[n - j];
}//n2^n
for (int x = 0; x < (1 << n); x++)
for (int y = 0; y < (1 << n); y++) gg[x][xmx[x ^ y]] += tax[y]; //2^{2n},对于x^y就是将两个位置上不同的位转为1,因为上面预处理的 xmx 是以位为 0 来加权,方便了后面这里不用取反
while (q--) {
int k; scanf("%s%d", s, &k);
int now = 0, len = strlen(s), ans = 0;
for (int j = len - 1; j >= 0; j--) now += whw[len - 1 - j] * (s[j] - '0');
for (int i = 0; i <= k; i++) ans += gg[now][i];//gg[状态][值]=个数 比 gg[状态][状态]=值 好很多,从 2^n 到 k
printf("%d\n", ans);
}//q(n+k)
return 0;
}
int main() {
scanf("%d%d%d", &n, &m, &q), solve();
return 0;
}
------ 本文结束 ------