今天我們來看看CF846D 題目連結
題目描述
Luba 最近買了一個顯示器，其顯示器可以看作一個 $n \times m$ 的矩陣。隨著時間的推移，部分像素會停止工作。當存在一個大小為 $k \times k$ 的正方形區域，其內所有像素均停止工作時，Luba 認為顯示器已經「壞掉」。
輸入格式
- 第一行包含四個整數：$n$, $m$, $k$, $q$
其中：- $1 \le n, m \le 500$
- $1 \le k \le \min(n, m)$
- $0 \le q \le n \cdot m$
- 接下來 $q$ 行，每行包含三個整數：$x_i$, $y_i$, $t_i$
表示位於第 $x_i$ 行、第 $y_i$ 列的像素在時刻 $t_i$ 停止工作，其中- $1 \le x_i \le n$
- $1 \le y_i \le m$
- $0 \le t_i \le 10^9$
輸出格式
輸出一個整數，表示顯示器第一次「壞掉」的最小時刻（即出現全壞的 $k \times k$ 正方形的時刻），如果即使所有 $q$ 個像素都停止工作後仍不存在這樣的正方形，則輸出 $-1$。
前言
我有想到要二分搜螢幕最早壞$k\times k$方塊的時間，但是居然在最簡單的，要怎麼快速算出一個$k\times k$方塊有沒有全都壞掉那邊卡住了
想法
由於只會有$500\times500$個壞掉的pixel，所以我們不用被時間$t\le10^9$嚇到，只要把壞掉的pixel用時間排序就好。
注意到時間$t$如果電視已經壞掉了，對於時間$t’>t$是一定會壞掉的，那麼我們就有單調性，可以去二分搜最早壞掉的時間，這部分二分搜的複雜度是$O(\lg q)$
那麼我們只要想想看，對於某個時間$t$，我們要怎麼知道螢幕有沒有$k\times k$的壞掉的區域。
可以對每個點$(x,y)$，維護從螢幕$(1,1)$到$(x,y)$有多少個壞點。那麼對於任何方形區域，我們都可以利用這個資訊去得到方形區域裡有多少壞點。只要我對所有$k\times k$區域去看壞點數量是不是$k^2$即可。
要維護這個數量就是簡單的利用dp思想：
$$
cnt[i][j] = cnt[i – 1][j] + cnt[i][j – 1] – cnt[i – 1][j – 1] + (tv[i][j]在此時已經壞掉了嗎 ? 1 : 0)
$$
注意到，如果要快速判斷一個點$(i,j)$在時間$time$有沒有壞掉，只要事先維護一個陣列$tv[n][m]$，如果有壞點，就在$tv[i][j]$寫上壞掉的時間點即可。
程式碼:
const int _n = 500 + 10;
int n, m, k, q, tv[_n][_n], cnt[_n][_n];
struct Query {
int x, y, t;
bool operator<(const auto& rhs) const {
return t < rhs.t;
}
};
vector<Query> qs;
bool hasKxK(int qsIdx) {
int time = qs[qsIdx].t;
memset(cnt, 0, sizeof(cnt));
cnt[0][0] = tv[0][0] <= time ? 1 : 0;
rep(i, 1, n + 1) {
cnt[i][0] = cnt[i - 1][0] + (tv[i][0] <= time ? 1 : 0);
}
rep(j, 1, m + 1) {
cnt[0][j] = cnt[0][j - 1] + (tv[0][j] <= time ? 1 : 0);
}
rep(i, 1, n + 1) {
rep(j, 1, m + 1) {
cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + (tv[i][j] <= time ? 1 : 0);
}
}
rep(i, k, n + 1) {
rep(j, k, m + 1) {
int cntInKxK = cnt[i][j] - cnt[i - k][j] - cnt[i][j - k] + cnt[i - k][j - k];
if (cntInKxK == k * k) return true;
}
}
return false;
}
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k >> q;
rep(i, 0, n + 1) rep(j, 0, m + 1) {
tv[i][j] = 0x7f7f7f7f;
}
rep(i, 0, q) {
int x, y, t;
cin >> x >> y >> t;
qs.pb(Query{x, y, t});
tv[x][y] = t;
}
sort(all(qs));
int MAXB = (int)log2(qs.size()) + 2;
int tmp = -1;
per(i, 0, MAXB) {
if ((tmp + (1 << i)) < qs.size() and !hasKxK(tmp + (1 << i))) {
tmp = tmp + (1 << i);
}
}
if (tmp == qs.size() - 1) {
cout << -1 << '\n';
} else {
cout << qs[tmp + 1].t << '\n';
}
return 0;
}
標頭、模板請點Submission看 Submission