1 solutions

  • 0
    @ 2025-11-11 17:47:24

    网上好像都是用差分做的,我提供一个更直观的做法吧。

    突破口是根据每次更新的点去调整答案。

    显然,每一个位置只会更新一次,并且同一时刻内,至多只能被一个水印包含。

    因此可以考虑对已经形成水印的每一个点指向一个起始坐标。

    思考答案的记录方式(记录当前时刻的每一个水印):

    1.没有更新,和之前的答案数量一致。

    2.更新后增加了一个水印,内部每一个点指向起始坐标。

    3.更新的点已经有起始坐标,则答案数减一,同时再次扫描一遍。

    最坏时间复杂度 O(4545n2)O(45*45n^2)

    #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