题解：P11662 [JOI 2025 Final] 方格染色 / Grid Coloring

· · 题解

此题评价：本题思想工作挺难的，但想好后就容易多了。

正文

相信各位都读懂题意了，在此我就不再赘述了。

定义：在网格图中，第一列第 n 个数记作 A_{n} 。第一行第 n 个数记作 B_{n} 。网格图中第 i 列第 j 行的格子记作 O_{i,j} 。（不存在 O_ {i,0},O_{0,j}）。

如果只是单纯的暴力加模拟，一定会 TLE or MLE。

那么，该如何解决呢？

MLE 问题

注意到：对于任意 O_{i,j} 都有 O_{i,j}=\max(A_{1}\dots A_{i},B_{1}\dots B_{j})。

为了简化操作 ， 我们用一种类似于前缀和的方式做预处理。 使得 A_{i}=\max(A_{1}\dots A_{i}) ， B_{i}=\max(B_{1}\dots B_{i}) 。 即：让序列 A ，序列 B 单调不降。

这样， O_{i,j}=\max(A_{i},B_{j}) 。 我们可以直接从预处理的序列 A ，序列 B 推出网格图中的某一格子，空间复杂度从 O(n^{2}) 降到了 O(n) 。

TLE 问题

为了解决 MLE 问题，我们竟阴差阳错地得到了一个宝贝单调不降序列。

目前，我们每次要提出一个 A_{i} 并与整个序列 B 做一轮比较。

容易发现：总有前几个数数值是相同的且等于 A_{i} ，我们暂时把这个“几”记作 xp 吧。

很容易明白，这是因为序列 B 单调不降。前 xp 个数都小于等于 A_{i} 。

可以考虑二分。这样的话，时间复杂度就会变为 O(n\log{n}) 了。

别忘了序列 A 也是单调不降的。

因为 A_{i}\le A_{i+1} 这使得 xp 也只增不减。

考虑双指针。因为两个指针只把两个序列扫一遍，因此时间复杂度变成 O(n) 了。

查找，输出答案

实在想不出别的算法了，就排序吧（痛失 O(n) 的时间复杂度）。

AC code：

#include <bits/stdc++.h>
using namespace std;

#define N (int)2e5+10
int n, xp = 1;

struct num {
    int t, m;
    long long c;
}A[N], B[N], AB_h[2*N];

//-----------------------------------------------------
/*      第一部分 
N 代表 n 的上限 
n 接收 网格图的边长
xp 是 辅助变量，用于查找各个数出现的次数

结构体 num 中：
    t 记录输入的原始数据。 
    m 类似指针，在预处理时指向比它大的数或自己。 
    c 用于记录此数 (t) 出现的次数。

序列A，序列B，分别储存输入的数。
在代码的最后用 AB_h 合并序列A，序列B以便求出答案。

温馨提示： 不开 long long 见祖宗。 
*/ 

bool cmp_one (num a,num b) {
    return a.t > b.t;
}

bool cmp_two (num a,num b) {
    if (a.c == b.c)
        return a.t > b.t;
    else return a.c > b.c;
}

//-----------------------------------------------------
/*      第二部分
两次排序 cmp 均对 num 结构体。 
第一次排序：把相同数 (t) 的放在一起，方便次数相加。 
第二次排序：按照题目要求排序，查找到答案。 
*/ 

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &A[i].t);
        A[i].m = i; A[i].c = 1;
        if (i >= 2 && A[i].t < A[A[i-1].m].t)
            A[i].m = A[i-1].m;
    }
    for (int i = 0; i < n; i ++) {
        scanf("%d", &B[i].t);
        B[i].m = i; B[i].c = 1;
        if (i >= 2 && B[i].t < B[B[i-1].m].t)
            B[i].m = B[i-1].m;
    }
    B[0].c = 0;

//-----------------------------------------------------
/*      第三部分-输入部分
输入序列A，序列B并初始化。同时对两者做预处理。 
特殊的东西必须特殊对待，直接把左上角的数的次数调为0
*/ 

    for (int i = 1; i < n; i ++) {
        while (A[A[i].m].t >= B[B[xp].m].t && xp < n){
            B[B[xp].m].c += i-1;
            xp ++;
        }
        A[A[i].m].c += xp-1;
    }
    while (xp < n) {
        B[B[xp].m].c += n-1;
        xp ++;
    }

//-----------------------------------------------------
/*      第四部分-处理部分1 
xp 作辅助变量，找到各个数的次数，累加到序列A，序列B中。
有个别的数据点使得 xp 不能扫到最后，因此再用 While 封个底
*/ 

    for (int i = 0; i < n; i ++) {
        AB_h[2*i+0].t = A[i].t; AB_h[2*i+0].c = A[i].c;
        AB_h[2*i+1].t = B[i].t; AB_h[2*i+1].c = B[i].c;
    }
    sort(AB_h, AB_h+2*n, cmp_one);
    for (int i = 2*n; i >= 0; i --) {
        if (AB_h[i].t == AB_h[i+1].t) {
            AB_h[i].c += AB_h[i+1].c;
            AB_h[i+1].t = AB_h[i+1].c = 0;
        }
    }

//-----------------------------------------------------
/*      第五部分-处理部分2
交错存储到AB_h中。
第一次排序后对相同数(t)的次数相加并把后者删除。 
*/ 

    sort(AB_h, AB_h+2*n, cmp_two);
    printf("%d %lld", AB_h[0].t, AB_h[0].c);

//-----------------------------------------------------
/*      第六部分-输出部分 
第二次排序 输出答案
*/ 

    return 0; //完结 
}

后记

时间复杂度为 O(n\log{n}) 。 空间复杂度为 O(n) 。

AC 记录。

运行得还算快，用时 280ms 。

What can I say ? I_AM_TLEer out !。