[ABC260G] Scalene Triangle Area题解

q0y1 · 2023-05-10 17:56:51 · 题解

[ABC260G] Scalene Triangle Area

题意

有一个 n \times n 的矩阵，里面由 XO 组成，对于一个 O，如果它的坐标是 (u, v) 那么它所可以影响的点的坐标是 (x, y)，其中 (x, y) 满足以下条件：

u\le x
v\le y
(x-u)+\dfrac{(y-v)}{2}<M

给定 N,M,Q 和 Q 次询问 X_i,Y_i，询问这个位置被几个 O 控制。

思路

1.暴力（虽然也能过）

对于一个 O,它肯定可以影响几行，而每一行也肯定是连续的一段，那么可以枚举行然后计算连续的一段的左端点和右端点，然后前缀和计算（由于后面有正解，这里就不详细解释了）。

#include <iostream>

using namespace std;

const int MaxN = 2010;

int f[MaxN][MaxN], n, m, l, r, q, ans;
char c[MaxN][MaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> c[i][j], f[i][j] = f[i][j - 1] + (c[i][j] == 'O');
    }
  }
  for (cin >> q; q; q--) {
    cin >> l >> r, ans = 0;
    for (int i = max(l - m, 1); i <= l; i++) {
      int j = max(r - (m - (l - i)) * 2, 0);
      (j <= r) && (ans += f[i][r] - f[i][j]);
    }
    cout << ans << '\n';
  }
  return 0;
}

2.正解差分

我们来看这样一组数据

OXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

而 m 设为

``` 111111000 111100000 110000000 000000000 …………………… ``` 那么由于是二位差分所以先以列的方向做差分，可以得到： ``` 1,0,0,0,0,0,-1,0,0 1,0,0,0,-1,0,0,0,0 1,0,-1,0,0,0,0,0,0 …………………… ``` 得到这个后会发现如果直接以行的方向做差分是不行的所以可以把它拆开得到： ``` 1,0,0,0,0,0,0,0,0 1,0,0,0,0,0,0,0,0 1,0,0,0,0,0,0,0,0 …………………… ``` 和： ``` 0,0,0,0,0,0,-1,0,0 0,0,0,0,-1,0,0,0,0 0,0,-1,0,0,0,0,0,0 …………………… ``` 这时第一个矩阵可以做以行的方向做差分了： ``` 1,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0 -1,0,0,0,0,0,0,0,0 …………………… ``` 那第二个矩阵怎么办？很简单，只要以斜着做差分就行了，如下图所示： ``` 0,0,0,0,0,0,-1,0,0 0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0 1,0,0,0,0,0,0,0,0 …………………… ``` ![](https://cdn.luogu.com.cn/upload/image_hosting/j80f4k2b.png) 这样就可以了，这四个差分点分别就是（$i, j$ 表示 `O` 的位置）：$(i, j), (i + m, j), (i, j + 2 \times m), (i + m, j)

最后反着还原原数组即可。

#include <iostream>

using namespace std;

const int MaxN = 2010;

int n, m, t, l, r;
char c[MaxN][MaxN];
int q[MaxN * 3][MaxN], x[MaxN * 3][MaxN * 5], st[MaxN * 3][MaxN * 5];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> c[i][j];
      if (c[i][j] == 'O') {
        q[i][j]++, q[i + m][j]--, x[i][j + 2 * m]--, x[i + m][j]++;
      }
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n + 2 * m; j++) {
      x[i][j] += x[i - 1][j + 2];
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n; j++) {
      q[i][j] += q[i - 1][j];
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n + 2 * m; j++) {
      st[i][j] = q[i][j] + x[i][j];
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n + 2 * m; j++) {
      st[i][j] += st[i][j - 1];
    }
  }
  for (cin >> t; t; t--) {
    cin >> l >> r;
    cout << st[l][r] << '\n';
  }
  return 0;
}

这是本蒟蒻的第一篇题解，请管理大大放宽放宽吧。