CF1494B Berland Crossword 题解
阅读原文时间:2023年07月09日阅读:4

有一种叫做 Berland crossword 的拼图游戏。这个拼图由 \(n\) 行 \(n\) 列组成,你可以将里面的一些格子涂成黑色。现在给出 \(T\) 个这样的拼图,每个拼图都含有如下限制:

  • 第一行最多有 \(u\) 个黑色格子。
  • 第 \(n\) 列最多有 \(r\) 个黑色格子。
  • 第 \(n\) 行最多有 \(d\) 个黑色格子。
  • 第一列做多有 \(l\) 个黑色格子。

问是否有满足如上限制的拼图(不需要输出方案)。

数据范围:\(2\leqslant n\leqslant 100\),\(0\leqslant u,r,d,l\leqslant n\),\(1\leqslant T\leqslant 10^3\)。

第二题还是一样的暴力,只不过可能和其他那些直接暴力枚举 \(16\) 种情况的不太一样,这里讲讲。

首先,我们可以想到,如果 \(u=n\),那么第一列和第 \(n\) 列都至少有 \(1\) 个黑色格子,\(d=n\) 同理;如果 \(r=n\),那么第一行和第 \(n\) 行都至少有一个黑色格子,\(l=n\) 同理。

另外还有一种比较特殊的情况,就是当上面的四个数中的某些数 \(=n-1\)。如果 \(u=n-1\),那么第一列和第 \(n\) 列中的一列至少会有 \(1\) 个黑色格子,\(d=n-1\) 同理;如果 \(r=n-1\),那么第一行和第 \(n\) 行中的一行至少会有 \(1\) 个黑色格子,\(l=n-1\) 同理。

于是,我们不妨先设出所有的 \(u,r,d,l\) 所在的行列在输入限制下的最小黑色格子数。先把所有的 \(=n\) 的情况所影响的行列的最小黑色格子数加 \(1\),然后对于 \(=n-1\) 的情况,我们看当前还有那些行列的最小黑色格子数小于输入限制,就把那个行列的最小黑色格子数加 \(1\)(如果两个行或者两个列当前的最小黑色格子数都小于输入限制,随便加进去哪一个行列都行)。最后再来判断是否超过了输入限制即可。

如果上面的文字你并没有听懂,可以参考一下下面的代码实现。

int n, u, r, d, l, limit[7], num[7];

int main() {
    MT {
        memset(limit, 0, sizeof(limit));
        memset(num, 0, sizeof(num));
        n = Rint, u = Rint, r = Rint, d = Rint, l = Rint;
        if(u >= n - 1) limit[1] = u - (n - 2);
        if(r >= n - 1) limit[2] = r - (n - 2);
        if(d >= n - 1) limit[3] = d - (n - 2);
        if(l >= n - 1) limit[4] = l - (n - 2);
        num[1] += (limit[2] == 2) + (limit[4] == 2), num[2] += (limit[1] == 2) + (limit[3] == 2), num[3] += (limit[2] == 2) + (limit[4] == 2), num[4] += (limit[1] == 2) + (limit[3] == 2);
        if(limit[1] == 1) {(num[2] < r ? num[2] : num[4])++;}
        if(limit[2] == 1) {(num[1] < u ? num[1] : num[3])++;}
        if(limit[3] == 1) {(num[2] < r ? num[2] : num[4])++;}
        if(limit[4] == 1) {(num[1] < u ? num[1] : num[3])++;}
        puts((u >= num[1] && r >= num[2] && d >= num[3] && l >= num[4]) ? "YES" : "NO");
    }
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章