居然让我们做NOIP模拟卷吗。
思路
枚举矩形的右上角，可以唯一确定出左上角在哪里。
注意到一个黑色正方形必须要下面一行和右边一列都是白的才行，于是可以确定：只有这些蓝色位置可以作为左上角。
枚举蓝色位置，然后从左往右枚举他右边的白色格子，统计答案。
向右枚举可行的长度会对一个值取 min。这个需要预处理从 (i,j) 开始连续下去有多少白色格子, 结合二维前缀和即可
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
for (int j = 1; j <= m; j++)
{
g[n + 1][j] = n + 1;
}
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 1)
g[i][j] = i;
else
g[i][j] = g[i + 1][j];
}
}
for (int i = n; i >= 1; i--)
{
for (int j = m; j >= 1; j--)
{
if (a[i][j] == 0)
{
f[i][j] = 0;
continue;
}
int k = f[i + 1][j + 1];
int len_r = k + 1;
int sum1 = get_sum(i, j, i, j + k);
int sum2 = get_sum(i, j, i + k, j);
if (sum1 == len_r && sum2 == len_r)
{
f[i][j] = k + 1;
}
else
f[i][j] = 1;
}
}
LL int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 0)
continue;
int k = f[i][j];
int base_r = i + k;
if (base_r > n + 1)
continue;
int res = 0x3f3f3f3f;
for (int col = j; col <= j + k - 1; col++)
{
res = min(res, g[base_r][col]);
}
for (int col = j + k; col <= m; col++)
{
if (get_sum(i, col, i + k - 1, col) != 0)
break;
res = min(res, g[base_r][col]);
if (res > base_r)
ans += (res - base_r);
}
}
}
好，成功的水了一篇题解（下次一定不水）