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

llamn · 2025-07-30 19:04:49 · 题解

首先，一个显然的判断是：如果巧克力的总数不是 ({H}+1)({V}+1) 的倍数，那么一定没有正确的切割方案。但是从样例就能看出来，只判断这一条是过不了的。

观察较小的数据，注意到 H = V = 1，此时的做法应为使横方向那一刀上下的巧克力数相等、纵方向那一刀左右的巧克力数相等。

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

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

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

#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();}