CF215C-题解

原题链接 Link

题面描述

题中所给的“十字”的定义不太好懂，翻译一下，一个十字其实是两个矩形的叠加。第一个矩形长宽分别为 \(2a+1,2b+1\)，第二个矩形长宽分别为 \(2c+1,2d+1\)，且这两个矩形的中心点都在 \((x0,y0)\)。另外，题中有一点说的不清楚，就是“十字”不能超过矩阵的限制，整个“十字”都应该在 \(n \times m\) 的矩阵范围内。

求的是有多少“十字”大小正好为 \(s\)。

解题思路

由上面的题面描述，我们可以知道：“十字”的大小只和 \(a,b,c,d\) 有关。如果设大小为 \(size\)，具体的计算公式为：

\[ size=(2a+1)(2b+1)+(2c+1)(2d+1)-\min(2a+1,2c+1)\times \min(2b+1,2d+1) \]

首先想到的是枚举。枚举什么呢？如果枚举 \((x0,y0)\) ，剩下的 \(a,b,c,d\) 不好枚，并且难以判断是否等于 \(s\)。

所以我们枚举 \(a,b,c,d\)，并保证这个形状的十字大小为 \(s\)，再计算这样的十字能放在多少个不同的地方。

但是如果枚举四个变量一定会超时，所以我们可以枚举前三个，然后计算出能使十字大小为 \(s\) 的那个 \(d\)。

具体怎么计算呢？

显然，当 \(a,b,c\) 都确定时，随着 \(d\) 的增大，十字的大小是单调递增的。考虑到这个单调性，我们就可以二分找到符合条件的 \(d\)。

对应的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for (int a = 0; a <= ((n - 1) >> 1); a++) {
    for (int b = 0; b <= ((m - 1) >> 1); b++) {
        for (int c = 0; c <= ((n - 1) >> 1); c++) {
            int l = 0, r = ((m - 1) >> 1), mid;
            while (l < r) {
                mid = (l + r) >> 1;
                if (calc(a, b, c, mid) < s) l = mid + 1;
                else r = mid;
            }
            if (calc(a, b, c, l) == s) { // calc是上文提到的计算方法
                int ta = (max(a, c) << 1) + 1, tb = (max(b, l) << 1) + 1;
                ans += (n - ta + 1) * (m - tb + 1);
            }
        }
    }
}

但是这一段代码是有漏洞的：当 \(c,d\) 对应的矩阵被 \(a,b\) 对应的矩阵完全包含的时候，其实是有多个 \(d\) 符合题意的（因为较小的矩阵被覆盖了，不管是什么形状，最终只看大矩阵的大小）。所以要做一个修改：当 \(c \le a\) 时，\(d\) 应该有 \(\max(d,b)-d+1\) 种取法。且这些取法最终看上去都是一样的，所以对答案的贡献都是相同的。

修改后的计算贡献如下：

1

ans += (n - ta + 1) * (m - tb + 1) * (c <= a ? (max(b, l) - l + 1) : 1);

完整的代码几乎都出来了，所以就不放了。