【Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) D】The Wu

给你n个字符串放在multiset中。
这些字符串都是长度为m的01串。
然后给你q个询问
s,k
问你set中存在多少个字符串t
使得∑(t[i]==s[i])*w[i]的值

【题解】

虽然询问很多。
但分类一下最多也只有2^12个01串类型。
(01串可以和10进制数字一一对应)
我们可以先预处理一下答案。到时候直接输出。
2^12将近4500的样子
两重循环i,j
算出来01串i它和其他字符串j的特殊值为pair(i,j)的j的个数。
然后f[i][pair(i,j)]+=cnt[j]
那么我们再求个前缀和->f[i][j]+=f[i][j-1];
那么到时候直接输出f[s][k]就可以了。

用scanf。。不然会超时。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define res(x) scanf("%s",x)

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int N = 12;

int n,m,q,w[N+5],k;

int sum[(1<<N)+5][100+10];

int cnt[(1<<N)+5];

char s[N+5];

int get_value(int x,int y){

    int cur = 0;

    for (int i = n;i >=1;i--){

        if ((x&1)==(y&1)){

            cur += w[i];

        }

        x>>=1;y>>=1;

    }

    return cur;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

    scanf("%d%d%d",&n,&m,&q);

    rep1(i,1,n) scanf("%d",&w[i]);

    rep1(i,1,m){

        scanf("%s",s);

        int cur = 0;

        for (int i = 0;i < n;i++){

            cur<<=1;

            if (s[i]=='1') cur++;

        }

        cnt[cur]++;

    }

    for (int i = 0;i < (1<<n);i++){

        for (int j = 0;j < (1<<n);j++)

            if (cnt[j]>0){

                int value = get_value(i,j);

                if (value<=100) sum[i][value]+=cnt[j];

            }

        for (int j = 0;j <= 100;j++) sum[i][j] += sum[i][j-1];

    }

    while (q--){

        int k;

        scanf("%s%d",s,&k);

        int cur = 0;

        for (int i = 0;i < n;i++){

            cur<<=1;

            if (s[i]=='1') cur++;

        }

        printf("%d\n",sum[cur][k]);

    }

	return 0;

}

巴特西

【Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) D】The Wu

最新文章

热门文章