题目链接:https://codeforc.es/contest/1711/problem/C
大意是给一个n×m的矩形,有k种颜料,每种颜料有ai个,一个颜料可以涂一格方格,问是否能构建一幅美丽的画,一幅美丽的画被定义为一个方格周围至少有3个格子和他颜色相同,同时,定义第1行和 第n行,第1列和第m列是相邻的。
需要注意的是,邻居是指的周围四个格子。
我们易知,行或列的颜色必须一样,且连续行列必须>=2,这样图形的走向一定是 行 或 列,不可能交叉走向。
需要注意的是,如果我们填充行,那么如果列是奇数,那么我们需要存在一个 a[i]/2 >=3 对于 1-n,因为我们需要将奇数次的填充>=3行或列。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int nn = 1e5+10; int a[nn]; void solve() { memset(a,0,sizeof a); ll n,m,k; n=read(),m=read(),k=read(); ll sum1 = 0,sum2 = 0; bool ji1 = false,ji2 = false; for(int i=1;i<=k;i++) { a[i] = read(); if(a[i]/n>=2) sum1+=a[i]/n; if(a[i]/m>=2) sum2+=a[i]/m; if(a[i]/n>=3) ji1 = true; if(a[i]/m>=3) ji2 = true; } if(m%2&&ji1&&sum1>=m) printf("YES\n"); else if(m%2==0&&sum1>=m) printf("YES\n"); else if(n%2&&ji2&&sum2>=n) printf("YES\n"); else if(n%2==0&&sum2>=n) printf("YES\n"); else printf("NO\n"); } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }