题解：P13136 [GCJ 2018 #1A] Waffle Choppers

首先，一个显然的判断是：如果巧克力的总数不是

({H}+1)({V}+1)

的倍数，那么一定没有正确的切割方案。但是从样例就能看出来，只判断这一条是过不了的。

观察较小的数据，注意到

H = V = 1

，此时的做法应为使横方向那一刀上下的巧克力数相等、纵方向那一刀左右的巧克力数相等。

这启示我们正确的划分方案中，横着切的每一刀之间的巧克力数量都应该相等。纵向同理。

但还有一种反例：在样例中的第四组数据中，可以找到上述划分方案，但最后的结果却不合法。

所以最后我们还要按照找出的方案划分，再验证一下分出的每一块的巧克力是否相等。

CPP

#include <bits/stdc++.h>
#define _eggy_ using
#define _party_ namespace
#define pf printf
#define sf scanf
_eggy_ _party_ std; _party_ llamn{
int n,m,i,j,k,t0,t1,t2,t3;
int $, _, sum1[110], sum2[110], sum[110][110], q1, q2;
int p1[110], p2[110], tp1, tp2;

#define IMP {puts("IMPOSSIBLE");continue;}
int main()
{
	sf("%d",&$); for (_ = 1; _ <= $; _++)
	{
		pf("Case #%d: ",_);
		
		sf("%d%d%d%d",&n,&m,&q1,&q2);
		memset(sum1,0,sizeof(sum1));
		memset(sum2,0,sizeof(sum2));
		memset(sum,0,sizeof(sum));
		for (i = 1; i <= n; i++)
		{
			sf("%*[^.@]");
			for (j = 1; j <= m; j++)
			{
				sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
				if (getchar() == '@') sum1[i]++, sum2[j]++, sum[i][j]++;
			}				
		}if (sum[n][m] % ((q1 + 1) * (q2 + 1))) IMP
		
		t1 = sum[n][m] / (q1 + 1), t2 = t3 = tp1 = 0;
		for (i = 1; i <= n; i++)
		{
			t2 += sum1[i];
			if (t2 > t1) {t3 = 1; break;}
			if (t2 == t1) p1[++tp1] = i, t2 = 0; // 在 i 行后切蛋糕 
		}if (t3) IMP
		
		t1 = sum[n][m] / (q2 + 1), t2 = t3 = tp2 = 0;
		for (i = 1; i <= m; i++)
		{
			t2 += sum2[i];
			if (t2 > t1) {t3 = 1; break;}
			if (t2 == t1) p2[++tp2] = i, t2 = 0; // 在 i 列后切蛋糕 
		}if (t3) IMP
		
		t1 = sum[n][m] / (q1 + 1) / (q2 + 1), t3 = 0;
		for (i = 1; i <= tp1; i++)
		{
			for (j = 1; j <= tp2; j++)
			{
				if (sum[p1[i]][p2[j]] - sum[p1[i-1]][p2[j]] - sum[p1[i]][p2[j-1]] + sum[p1[i-1]][p2[j-1]] != t1)
				{
					t3 = 1;
					break;
				}
			}if (t3) break;
		}if (t3) IMP
		puts("POSSIBLE");
	}
    return 0;
}
}signed main(){return llamn::main();}

题解：P13136 [GCJ 2018 #1A] Waffle Choppers

文章操作

相关推荐

评论

题解：P13136 [GCJ 2018 #1A] Waffle Choppers