1 solutions
-
0
网上好像都是用差分做的,我提供一个更直观的做法吧。
突破口是根据每次更新的点去调整答案。
显然,每一个位置只会更新一次,并且同一时刻内,至多只能被一个水印包含。
因此可以考虑对已经形成水印的每一个点指向一个起始坐标。
思考答案的记录方式(记录当前时刻的每一个水印):
1.没有更新,和之前的答案数量一致。
2.更新后增加了一个水印,内部每一个点指向起始坐标。
3.更新的点已经有起始坐标,则答案数减一,同时再次扫描一遍。
最坏时间复杂度 。
#include <bits/stdc++.h> using namespace std; typedef pair <int, int> pii; const int N = 205; bool val[7][11], b[N][N]; int n, L, a[N][N], ans[70000]; pii ptr[N][N]; vector <pii> vec[70000]; void init() { for (int i = 1; i <= 9; i ++) val[1][i] = 1; val[2][1] = val[2][4] = val[2][7] = val[2][9] = 1; val[3][1] = val[3][4] = val[3][5] = val[3][6] = val[3][7] = val[3][8] = 1; val[4][1] = val[4][6] = val[4][7] = 1; for (int i = 1; i <= 7; i ++) val[5][i] = 1; } bool chk(int x, int y) { for (int i = x; i <= x + 4; i ++) for (int j = y; j <= y + 8; j ++) if (b[i][j] != val[i - x + 1][j - y + 1]) return 0; for (int i = x; i <= x + 4; i ++) for (int j = y; j <= y + 8; j ++) ptr[i][j] = pii(x, y); return 1; } void clear(int x, int y) { for (int i = x; i <= x + 4; i ++) for (int j = y; j <= y + 8; j ++) ptr[i][j] = pii(-1, -1); } int main() { init(); scanf("%d%d", &n, &L); for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) { scanf("%d", &a[i][j]); vec[a[i][j]].push_back(pii(i, j)); ptr[i][j] = pii(-1, -1); } int cnt = 0; for (int num = L - 1; num >= 0; num --) { for (auto [x, y] : vec[num]) { b[x][y] = 1; if (ptr[x][y] != pii(-1, -1)) { auto [i, j] = ptr[x][y]; clear(i, j), cnt --; } } for (auto [x, y] : vec[num]) for (int i = max(1, x - 4); i <= min(x, n - 4); i ++) for (int j = max(1, y - 8); j <= min(y, n - 8); j ++) if (ptr[i][j] == pii(-1, -1) && chk(i, j)) {cnt ++; break;} ans[num] = cnt; } for (int i = 0; i < L; i ++) if (ans[i]) printf("%d\n", i); return 0; }
- 1
Information
- ID
- 256
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 2
- Tags
- # Submissions
- 324
- Accepted
- 47
- Uploaded By