题目:CF Educational Codeforces Round 105 (Rated for Div. 2) B题
给你t个样例,每个样例给你一个n代表有n行n列的矩阵(一开始全都是白色块)
再给你最上一行的黑块数量u、最右一列的黑块数量r,最下一行的黑块数量d,最左一行的黑块数量l
问你根据这5个数据这样的矩阵是否存在(就是这几个数据不能有冲突)
样例:
题目网址:https://codeforces.com/contests
思路:枚举,这几个数据相互有关联的地方就在于四个对角点,每个对角点都会对旁边两行造成影响
那么我们可以枚举这四个对角点的情况来看是否存在这样的图形
而这里的枚举就可以用01枚举来解决,通过这个对角点涂黑还是不涂黑说明0与1两种情况
然后记录每行每列需要几个黑色块
当对应的行或列少于需要的黑色块或者超出n-2范围时说明不成立(超出时说明黑色块超出能填的块的数量了)
否则成立
AC代码:
#include <iostream> #include <string.h> using namespace std; int a[4]= {0}; int n; int main() { int t; cin>>t; while(t--) { memset(a,0,sizeof(a)); int u,d,l,r; cin>>n>>u>>r>>d>>l; int st=(1<<4)-1;//说明1111的情况,这里一定要加括号,不然是变成1<<3(因为这个WA了一发) int ok=0; for(int k=0;k<=st;k++){//从0000到1111的情况,依次枚举 memset(a,0,sizeof(a));//记得清空数组 int U=0,R=0,D=0,L=0;//记录每行每列需要的黑色块 int j=0; int i=k; while(i){//看每一位情况,是0还是1 if(i&1){ a[j]=1; } i>>=1; j++; } if(a[0]==1){//这里要画图,每个点对应的隔壁两行不要乱了 U++; L++; } if(a[1]==1){ U++; R++; } if(a[2]==1){ R++; D++; } if(a[3]==1){ D++; L++; } int c1=u-U,c2=r-R,c3=d-D,c4=l-L;//每个数据减去需要的黑色块 if(c1>=0&&c1<=n-2&&c2>=0&&c2<=n-2&&c3>=0&&c3<=n-2&&c4>=0&&c4<=n-2){//看是否满足要求 ok=1; } } if(ok) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } return 0; }