P9737 [COCI2022-2023#2] Lampice 题解

· · 题解

→更好的阅读体验

题目大意

题目链接：P9737 Lampice

给定一个坐标系（仅使用 (0,0) 至 (n,m) 的部分），输入 k 个整数点对 (x_1,y_1),(x_2,y_2)。

要求在坐标轴上找到矩形（顶点坐标均为自然数），使每个点对的两个点均在矩形内或均在矩形外，最终输出满足条件的矩形个数。

题解

下面将讨论各个 subtask 中的可行解法（subtask 颜色表示个人认为的难度）：

\text{\textcolor{#7de749}{Subtask 1 (28 pts)}}

特殊条件：

对于每种颜色的灯，x_1=y_1=0。

解法：

我们发现，如果我们将 (0,0) 加入矩形，则必须将所有点全部加入矩形内。由此可以进行分类讨论：

①将 (0,0) 加入矩形：为将所有点全部加入矩形内，通过打擂获取最大的 x,y 值 \max(x_2),\max(y_2)。

则 x 共有 (n+1-\max(x_2)) 种可能，y 共有 (m+1-\max(y_2)) 种可能。

易得，该种情况下共有 (n+1-\max(x_2))\cdot(m+1-\max(y_2)) 个矩形。

②不将 (0,0) 加入矩形：那么它不能包含任何其他点，因此我们的目标是找到没有任何点的矩形个数。

先遍历矩形的下行 j ，那么对于每一列，我们可以计算并存下该列的最大高度（也就是从第 j 行开始，在不碰到点的情况下向上可以走多远）。

再遍历列 i ，可以通过找到比第 i 高度小的最左/最右行 来计算矩形数量 这里就不多赘述了。

→时间复杂度最终为 O(nm^2 + k) （懒得写程序了（）。

\text{\textcolor{#fe4f64}{Subtask 2 (12 pts)}}

特殊条件：

### 解法： 直接暴力扫每一种可能的矩形并判断是否合法。 →时间复杂度最终为 $O(k(nm)^2)$。 ## $\text{\textcolor{#a64ed3}{Subtask 3 (36+12 pts)}}

特殊条件：

### 解法： 此时我们可以借助**随机化**。 [→什么是uniform_int_distribution](https://blog.csdn.net/Alfa_/article/details/125215799) （省流：均匀分布的随机数）。 给每一个颜色赋予一个唯一的值（设这个值在 $ 0 \sim 2 ^ {60} - 1 $ 之间），那么当我们判断矩形的合法性时，则可以将矩形内所有点所对应的值全部进行**异或操作**。 那么显然，当矩形合法时，内部的 xor 结果应为零，不合法则不为零。 那么此时我们可以列举每个矩形，并用该种方法检查合法性。 我们可以进行“前缀 xor 和”的预处理以更快的计算每个矩形的 xor 和。 →时间复杂度最终为 $O((nm)^2+k)$。 ## $\text{\textcolor{#a64ed3}{Subtask 4 (110 pts)}}

特殊条件：

无特殊条件。

解法：

进一步优化 sub#3 的算法：

遍历矩形左端的列 l 和右端的列 r，再使用数组 v[i] 储存第 i 行中第 l 列到第 r 列所有值的 xor 和。

此时问题就转化为了：找到 xor 和 = 0 且 长度至少为 2 的 v[] 的子数组的数量。

tips：“长度至少为 2”这一条件可以后期处理（删去长度为 1 的情况数）。

→时间复杂度最终为 O(n^2 \cdot m \log m)。

代码实现

//solution of P9737 [COCI2022-2023#2] Lampice

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

#define MAXN 3010
#define int long long

mt19937 rng(random_device{}());

int m,n,k;
int a[MAXN][MAXN];

int solve(vector<int> v){
    sort(v.begin(),v.end());
    int cnt=1,ans=0;
    for(int i=1;i<(int)v.size();++i){
        if (v[i]!=v[i-1]) cnt=0;
        ans+=cnt;
        ++cnt;
    }
    return ans;
}

signed main(){
    //解绑快读 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //生成均匀分布的随机数 （见sub#3题解） 
    uniform_int_distribution<int> dis(0,(1ll<<60)-1);

    cin>>n>>m>>k;
    ++n,++m;//这里将所有坐标+1易于后期操作 

    for(int i=1;i<=k;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        ++x1,++y1,++x2,++y2;//同理
        int u=dis(rng);
        a[x1][y1]^=u;//给点赋予随机值 
        a[x2][y2]^=u;
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            a[i+1][j+1]^=a[i][j]^a[i+1][j]^a[i][j+1];//预处理 

    int ans=0;
    for(int l=0;l<n;l++)
        for(int r=l+2;r<=n;r++){//遍历矩形左右坐标 
            vector<int> v(m+1);
            for(int i=0;i<=m;i++){
                v[i]=a[l][i]^a[r][i];
            }
            ans+=solve(v);
            for(int i=0;i<m;i++){//删去长度为1的子数组 （不要忘记了哦！！！） 
                ans-=(v[i]^v[i+1])==0;
            }
        }

    cout<<ans<<endl;

    return 0;
}