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、写完程序要核对自己想的复杂度和实现是否有差异。

#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;
}