牛客小白月赛 23 A. 膜法记录

发表于 分类于

链接

https://ac.nowcoder.com/acm/contest/4784/A

题意

所有的敌人都排布在一个 $n*m$ 的网格中

总共能够 $a$ 次消灭一整行的敌人，$b$ 次消灭一整列的敌人

求能否将敌人全歼

思路

状压枚举选择行的状态

预处理每种状态能够消灭多少列的敌人（前缀和）

$cnt[i]$ 即为在 $i$ 的状态下有多少列上没有敌人

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[21][100001];
int cnt[1100000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        int n,m,a,b;
        cin>>n>>m>>a>>b;
        for(int i=0;i<1<<n;i++) cnt[i]=0;
        for(int i=1;i<=n;i++) cin>>s[i]+1;
        for(int j=1;j<=m;j++) {
            int t=0;
            for(int i=1;i<=n;i++)
                if(s[i][j]=='*')
                    t|=1<<i-1;
            cnt[t]++;
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<1<<n;j++)
                if(j&1<<i)
                    cnt[j]+=cnt[j-(1<<i)];
        bool f=false;
        for(int i=0;i<1<<n;i++)
            if(__builtin_popcount(i)<=a&&m-cnt[i]<=b) {
                f=true;
                break;
            }
        if(f==true) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}