P6441 [COCI2011-2012#6] PASTELE 题解

b6e0_ · 2021-07-08 18:37:51 · 题解

这题因为值域很小，所以可以三维前缀和（容斥）做。将一支蜡笔看作三维空间中的一个点 (R_i,G_i,B_i)。二分答案，设二分到了 M，枚举这三维区间的左端点 i,j,k，那么对点 (x,y,z) 的限制就是 x\in[i,i+M],y\in[j,j+M],z\in[k,k+M]，用三维前缀和 \mathcal O(1) 求出在这个空间内的点数，判断够不够即可。

对于构造方案，在判断时记下是哪个区间中的点数不小于这个答案，构造时扫描 n 个点判断是否在这个区间即可。

三维前缀和的预处理公式是:

使用三维前缀和表示第一维在 [i_1,i_2]，第二维在 [j_1,j_2]，第三维在 [k_1,k_2] 的点数为：

设 R_i,G_i,B_i 的值域为 m，时间复杂度 \mathcal O(m^3\log m)。代码：

#include<bits/stdc++.h>
using namepace std;
int m,a[260][260][260],s[260][260][260],R[100010],G[100010],B[100010],ansi,ansj,ansk;
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x;
}
void write(int x)
{
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
inline bool check(int M)
{
    for(int i=1;i+M<257;i++)//之所以i,j,k<=256-M是因为假如i超过了，那么点数明显小于为256-M的情况（区间更小）
        for(int j=1;j+M<257;j++)
            for(int k=1;k+M<257;k++)
                if(s[i+M][j+M][k+M]-s[i-1][j+M][k+M]-s[i+M][j-1][k+M]-s[i+M][j+M][k-1]+s[i+M][j-1][k-1]+s[i-1][j+M][k-1]+s[i-1][j-1][k+M]-s[i-1][j-1][k-1]>=m)
                {
                    ansi=i;
                    ansj=j;
                    ansk=k;//记录下可行的区间
                    return true;
                }
    return false;
}
int main()
{
    int n=read(),i,j,k,L=-1,r=255,M;
    m=read();
    for(i=1;i<=n;i++)
    {
        R[i]=read();
        G[i]=read();
        B[i]=read();
        a[R[i]+1][G[i]+1][B[i]+1]++;//这里把坐标+1是避免下标越界
    }
    for(i=1;i<257;i++)
        for(j=1;j<257;j++)
            for(k=1;k<257;k++)
                s[i][j][k]=s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]-s[i-1][j-1][k]-s[i-1][j][k-1]-s[i][j-1][k-1]+s[i-1][j-1][k-1]+a[i][j][k];
    while(L+1<r)
    {
        M=(L+r)>>1;
        if(check(M))
            r=M;
        else
            L=M;
    }
    ansi--;
    ansj--;
    ansk--;
    write(r);
    putchar('\n');
    for(i=1;i<=n;i++)
        if(m&&ansi<=R[i]&&R[i]<=ansi+r&&ansj<=G[i]&&G[i]<=ansj+r&&ansk<=B[i]&&B[i]<=ansk+r)
        {
            write(R[i]);
            putchar(' ');
            write(G[i]);
            putchar(' ');
            write(B[i]);
            putchar('\n');
            m--;
        }
    return 0;
}