题解：P11724 [JOIG 2025] ポスター 2 / Poster 2

No_commander · 2025-02-13 14:42:33 · 题解

明显可以枚举哪个位置的颜色会变，对于左上，右上，左下，右下四个 2 \times 2 的正方形统计一下变化后的答案，和全局答案取个 \max 即可。

实现有个小细节，对于 k 比较小的情况可以暴力枚举换成哪种颜色，k 比较大时换成一种没有出现过的颜色即可。

大概就是这样：

il void mian(){
    read(n, k);
    L(i, 1, n) L(j, 1, n) a[i][j] = read();
    int ans = 0;
    L(i, 1, n - 1){
        L(j, 1, n - 1){
            set<int> st;
            st.insert(a[i][j]), st.insert(a[i + 1][j]), st.insert(a[i][j + 1]), st.insert(a[i + 1][j + 1]);
            if (st.size() >= 3) ans++;
        }
    }
    int ret = 0;
    L(i, 1, n){
        L(j, 1, n){
            int cnt = ans;
            set<int> st, st1, st2, st3, st4;
            if (i > 1) st1.insert(a[i - 1][j]), st2.insert(a[i - 1][j]), st.insert(a[i - 1][j]);
            if (j > 1) st1.insert(a[i][j - 1]), st3.insert(a[i][j - 1]), st.insert(a[i][j - 1]);
            if (i < n) st3.insert(a[i + 1][j]), st4.insert(a[i + 1][j]), st.insert(a[i + 1][j]);
            if (j < n) st2.insert(a[i][j + 1]), st4.insert(a[i][j + 1]), st.insert(a[i][j + 1]);
            if (i > 1 && j > 1) st1.insert(a[i - 1][j - 1]), st.insert(a[i - 1][j - 1]);
            if (i > 1 && j < n) st2.insert(a[i - 1][j + 1]), st.insert(a[i - 1][j + 1]);
            if (i < n && j > 1) st3.insert(a[i + 1][j - 1]), st.insert(a[i + 1][j - 1]);
            if (i < n && j < n) st4.insert(a[i + 1][j + 1]), st.insert(a[i + 1][j + 1]);
            int tot = 0;
            if (k <= 5000 && st.find(k) != st.end()){
                L(c, 1, k){
                    int rrt = 0;
                    set<int> sst1 = st1, sst2 = st2, sst3 = st3, sst4 = st4;
                    int flg1 = 0, flg2 = 0, flg3 = 0, flg4 = 0;
                    if (st1.size() == 2) flg1++;
                    if (st2.size() == 2) flg2++;
                    if (st3.size() == 2) flg3++;
                    if (st4.size() == 2) flg4++;
                    if (st1.find(c) == st1.end()) sst1.insert(c);
                    if (st2.find(c) == st2.end()) sst2.insert(c);
                    if (st3.find(c) == st3.end()) sst3.insert(c);
                    if (st4.find(c) == st4.end()) sst4.insert(c);
                    if (sst1.size() == 3 && st1.find(a[i][j]) != st1.end() && flg1) rrt++;
                    if (sst2.size() == 3 && st2.find(a[i][j]) != st2.end() && flg2) rrt++;
                    if (sst3.size() == 3 && st3.find(a[i][j]) != st3.end() && flg3) rrt++;
                    if (sst4.size() == 3 && st4.find(a[i][j]) != st4.end() && flg4) rrt++;
                    // if (i == 4 && j == 5){
                    //  wtsp(c), wtln(rrt);
                    // }
                    ckmax(tot, rrt);
                }
                cnt += tot;
            }
            else{
                int flg1 = 0, flg2 = 0, flg3 = 0, flg4 = 0;
                set<int> sst1 = st1, sst2 = st2, sst3 = st3, sst4 = st4;
                sst1.insert(a[i][j]), sst2.insert(a[i][j]), sst3.insert(a[i][j]), sst4.insert(a[i][j]);
                if (sst1.size() == 2) flg1++;
                if (sst2.size() == 2) flg2++;
                if (sst3.size() == 2) flg3++;
                if (sst4.size() == 2) flg4++;
                // wtsp(flg1), wtsp(flg2), wtsp(flg3), wtln(flg4);
                // wtsp(st1.size()), wtsp(st2.size()), wtsp(st3.size()), wtln(st4.size());
                st1.insert(k), st2.insert(k), st3.insert(k), st4.insert(k);
                if (st1.size() == 3 && flg1) cnt++;
                if (st2.size() == 3 && flg2) cnt++;
                if (st3.size() == 3 && flg3) cnt++;
                if (st4.size() == 3 && flg4) cnt++;
            }
            // if (st1.size() == 3) cnt++;
            // if (st2.size() == 3) cnt++;
            // if (st3.size() == 3) cnt++;
            // if (st4.size() == 3) cnt++;
            // wtsp(i), wtsp(j), wtln(cnt);
            ckmax(ret, cnt);
        }
    }
    write(ret);
}