Tövlənin boyanması (gümüş)#10345

Tövlənin boyanması (gümüş) (Həll təhlili)

Əvvəlcə məsələnin bir ölçülü variantını nəzərdən keçirək. Tutaq ki, say xəttinin üzərində $n$ intervalı $[a_{i}, b_{i}]$ [a_i, b_i] verilmişdir, harada $0 \leq a_{i}, b_{i} \leq 1000$ 0 \le a_i, b_i \le 1000. Bu xəttin üzərində hər bir tam ədədin neçə intervalla əhatə olunduğunu müəyyən etmək lazımdır.

Tam ədədli $d p$ massivini elan edirik və onu sıfırlarla başladırırıq. Sonra hər bir interval üçün $[a_{i}, b_{i}]$ [a_i, b_i] iki əməliyyat yerinə yetiririk:

d p [a_{i}] + +; d p [b_{i} + 1] - -;

dp[a_i]++; dp[b_i + 1]--;

Daha sonra $d p$ massivində prefiks cəmlərini hesablayırıq. $d p [i]$ qiyməti $i$ ədədini əhatə edən intervaların sayına bərabərdir.

Məsələn, aşağıdakı intervallar verilmişdir: $[3; 7], [6; 9], [1; 4], [3; 8], [2; 5]$ [3; 7], [6; 9], [1; 4], [3; 8], [2; 5]. $d p$ massivini başladırırıq:

Hər bir interval üçün $[a_{i}, b_{i}]$ [a_i, b_i] iki əməliyyat yerinə yetiririk: $d p [a_{i}] + +; d p [b_{i} + 1] - -$ dp[a_i]++; dp[b_i + 1]--.

İndi məsələnin iki ölçülü variantını nəzərdən keçirək. Məsahə $n$ düzbucaqlının $(x_{1}, y_{1}) - (x_{2}, y_{2}) (0 \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 1000)$ (x_1, y_1) - (x_2, y_2)~(0 \le x_1, y_1, x_2, y_2 \le 1000) koordinatları ilə verilir. Hər bir yerin neçə düzbucaqlı ilə əhatə olunduğunu müəyyən etmək lazımdır.

Tam ədədli iki ölçülü $d p$ massivini elan edirik və onu sıfırlarla başladırırıq. Sonra hər bir düzbucaqlı üçün $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) dörd əməliyyat yerinə yetiririk:

d p [x_{1}] [y_{1}] + +; d p [x_{1}] [y_{2} + 1] - -; d p [x_{2} + 1] [y_{1}] - -; d p [x_{2} + 1] [y_{2} + 1] + +;

dp[x_1][y_1]++; dp[x_1][y_2 + 1]--; dp[x_2 + 1][y_1]--; dp[x_2 + 1][y_2 + 1]++;

Bundan sonra $d p$ massivində prefiks cəmlərini hesablayırıq. $d p [i] [j]$ dp[i][j] qiyməti $(i, j)$ yerini əhatə edən düzbucaqlıların sayına bərabər olacaq.

Məsələn, $(2, 2) - (4, 5)$ (2, 2) - (4, 5) düzbucaqlı nümunəsini nəzərdən keçirək.

Nümunə

Üç düzbucaqlı ehtiva edən verilmiş nümunəni nəzərdən keçirək.

$k = 2$ k = 2 təbəqə ilə boyanmış $8$ kvadrat var.

Alqoritmin həyata keçirilməsi

İki ölçülü $d p$ massivini elan edirik.

#define MAX 1001
int dp[MAX][MAX];

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &n, &k);
while (n--)
{

Hər bir düzbucaqlı üçün $(a, b) - (c, d)$ (a, b) - (c, d) dörd əməliyyat yerinə yetiririk.

  scanf("%d %d %d %d", &a, &b, &c, &d);
  dp[a][b]++;
  dp[a][d]--;
  dp[c][b]--;
  dp[c][d]++;
}

$k$ təbəqə ilə boyanmış divar hüceyrələrinin sayını $r es$ dəyişənində hesablayırıq.

res = 0;

$d p$ massivində prefiks cəmlərini hesablayırıq.

for (i = 0; i < MAX; i++)
  for (j = 0; j < MAX; j++)
  {
    if (i) dp[i][j] += dp[i - 1][j];
    if (j) dp[i][j] += dp[i][j - 1];
    if (i && j) dp[i][j] -= dp[i - 1][j - 1];

Əgər $(i, j)$ hüceyrəsi $k$ təbəqə ilə boyanıbsa, $r es$ 1 artırılır,

    if (dp[i][j] == k) res++;
  }

Cavabı çıxarırıq.

printf("%d\n", res);