【牛客小白月赛23 A】膜法记录（二进制枚举）

Antonia ·

更新时间:2024-11-11

· 966 次阅读

【题目传送门】

题目描述：

牛牛最近在玩一款叫做《膜法记录》的游戏，这个游戏的机制是这样的：在一局游戏中，所有的敌人都排布在一个 n{n}n 行 m{m}m 列的网格中，牛牛指挥着他的魔法少女对敌人进行攻击。攻击有两种类型：行blast，列blast 行blast能消灭一整行的敌人，列blast能消灭一整列的敌人牛牛总共能够释放 a{a}a 次行blast，b{b}b 次列blast 给定某局游戏的初始局面，请问牛牛能否将敌人全歼？

输入描述:

第一行包含一个正整数T，表示测试数据组数，接下来是T组测试数据每组测试数据的第一行有四个正整数 n,m,a,b接下来有n{n}n行，每行是一个长度为m的字符串，第i行第j列的字符如果是 * 则说明这里有一个敌人，如果是 . 说明这里没有

输出描述:

对每组测试数据输出一行，如果能消灭所有的敌人，就输出yes，否则输出no

说明

第一个样例，我可以在第一行放一个行blast，然后前两列都放一个列blast，就把敌人给全歼了。第二个样例，我不管怎么安排攻击策略，都没法全歼敌人

备注:

在这里插入图片描述

分析：

这道题的n很小，只有20，我们可以利用二进制数来枚举可操作的行，我们可以认为1是对行操作，0是不操作；比如n=4时，若对3,4行操作对应的二进制数表示为1100。
由此我们对 0到2^n-1 （0表示都不操作，2^n-1表示的二进制数每一位都为1，即表示对n行都操作）范围内的数进行遍历，即枚举各种可操作行的组合。
然后再对整个矩阵进行遍历，选出来没有被行操作过得敌人，让列进行操作,如果列操作的次数小于题目中给定的次数，即满足，反之不满足。

代码如下：

#include 
using namespace std;
const int N=1e6+100;
string s[N];//字符串数组
int main() {
	int n,m,a,b,t;
	int flag;
	cin>>t;
	while(t--)
	{
		flag=0;
		cin>>n>>m>>a>>b;
		for(int i=0;i>s[i];
		for(int i=0;i<(1<<n);i++)//枚举0-2^n-1范围内的数，即枚举各种组合；
		{
			int x=0;
			for(int j=0;j>j)&1) x++;//判断有几个位有1，即对 几行 操作
     	    if(x!=a) continue;
		int y=0;
		for(int j=0;j<m;j++)
		for(int k=0;k>k)&1))//判断一下这个行有没有操作过，如果行操作过，就不用列操作了
        {
           y++;
           break;//这一列消灭完了，就跳出这一列到下一列；
        }
		if(y<=b) flag=1;
	    }
		if(flag) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
	}
	return 0;
}

six day~