题解 P3326 【[SDOI2015]立体图】

daifucong · 2018-10-14 19:27:19 · 题解

这是一道~~简单的~~模拟题。

据说可以将三维平面上的投影转化到二维平面上的问题做。

然而我太弱了，只会分类讨论。

我们发现只要处理每个小立方体的顶面，前面，右面的颜色就可以了。废话

令cnt[i][j]表示输入数据从上到下第i行，从左到右第j列的立方体个数。

对于顶面的颜色，我们对每束光线分类讨论：

对于方向竖直向下的光线，我们直接把光线加上去即可。
对于从左射来的光线，如果存在一个h>0，使得cnt[x][y-h]-cnt[x][y]\geqslant h，则这束光线不能照到位于(x,y)的最上面的小立方体的顶面的任何一部分。其它类似的光线同理。
对于从右下方向射来的光线：

如果存在一个h>0，使得cnt[x+h][y+h]-cnt[x][y]\geqslant h，则这束光线不能照到位于(x,y)的最上面的小立方体的顶面的任何一部分。

如果存在一个h>0，使得cnt[x+h][y+h-1]-cnt[x][y]\geqslant h，则这束光线不能照到位于(x,y)的最上面的小立方体的顶面的左边部分和下边部分。

如果存在一个h>0，使得cnt[x+h-1][y+h]-cnt[x][y]\geqslant h，则这束光线不能照到位于(x,y)的最上面的小立方体的顶面的右边部分和上边部分。

其它类似的光线同理。

对于右面的颜色，我们还是对每束光线分类讨论，但是只要讨论3束光线：

令这个小立方体的高度为Height。

对于从正右方向射来的光线，如果存在一个h>0，使得cnt[x][y+h]-Height\geqslant h，则这束光线不能找到这个立方体的右边。
对于从右下方向射来的光线：

如果存在一个h>0，使得cnt[x+h-1][y+h]-Height\geqslant h-1，则这个小立方体的整个右面不能被这束光照到。

如果存在一个h>0，使得cnt[x+h][y+h]-Height\geqslant h，则这个小立方体的整个右面不能被这束光照到。

如果存在一个h\geqslant 0，使得cnt[x+h+1][y+h+1]-Height\geqslant h，则这个小立方体右面的左边部分和下边部分不能被这束光照到。
对于从右上方向射来的光线，处理方法和从右下方向射来的光线类似。

对于前面的颜色，处理方法和右面的颜色类似。

至于输出的话其实就是这道题P1058。

上代码：

#include<bits/stdc++.h>
using namespace std;
char base[20][20]={"",
"\0    +-------+",
"\0   /4\\1111\'/|",
"\0  /44.*\'22/1|",
"\0 /.3333\\2/1/|",
"\0+-------+1.2|",
"\0|\\11111/|\\:2|",
"\0|4\\111/2|4*2|",
"\0|44\\1/22|4:\\|",
"\0|444X222|4\'3+",
"\0|44/3\\22|/3/ ",
"\0|4/333\\2|3/  ",
"\0|/33333\\|/   ",
"\0+-------+    "};
const int baseh=13;
char ans[5001][5001];int cnt[101][101];int n,m;int ansh,answ;
char getcube[20][20];
inline void setit(int startx,int starty){for(int i=13,x=startx;i>=1;i--,x--) for(int j=1,y=starty;j<=13;j++,y++) if(getcube[i][j]!=' ') ans[x][y]=getcube[i][j];}
struct Col
{
    bool R,B,G;Col(){R=B=G=0;}Col(char c){R=B=G=0;if(c=='R')R=1;if(c=='B') B=1;if(c=='G')G=1;}
    inline char getcol()
    {
        if(R==0&&B==0&&G==0) return 'K';if(R==0&&B==0&&G==1) return 'G';
        if(R==0&&B==1&&G==0) return 'B';if(R==0&&B==1&&G==1) return 'C';
        if(R==1&&B==0&&G==0) return 'R';if(R==1&&B==0&&G==1) return 'Y';
        if(R==1&&B==1&&G==0) return 'P';if(R==1&&B==1&&G==1) return 'W';
        assert(0);return '\0';
    }
};
inline Col operator +(const Col &a,const Col &b){Col res;res.R=a.R||b.R;res.B=a.B||b.B;res.G=a.G||b.G;return res;}
inline void Add(Col &a,char c){a=a+Col(c);}
//个人认为这样定义可以方便处理颜色重叠的问题
char light[4][4];
struct Block
{
    Col Ul,Ur,Uf,Ub;
    Col Fu,Fd,Fl,Fr;
    Col Ru,Rd,Rf,Rb;
    inline void Getcube()
    {
        for(int i=1;i<=baseh;i++) for(int j=1;j<=baseh;j++)
        {
            getcube[i][j]=base[i][j];
            if(i>=6&&j<=9)
            {
                if(base[i][j]=='1') getcube[i][j]=Fu.getcol();
                if(base[i][j]=='2') getcube[i][j]=Fr.getcol();
                if(base[i][j]=='3') getcube[i][j]=Fd.getcol();
                if(base[i][j]=='4') getcube[i][j]=Fl.getcol();
            }
            if(i>=5&&j>9)
            {
                if(base[i][j]=='1') getcube[i][j]=Ru.getcol();
                if(base[i][j]=='2') getcube[i][j]=Rb.getcol();
                if(base[i][j]=='3') getcube[i][j]=Rd.getcol();
                if(base[i][j]=='4') getcube[i][j]=Rf.getcol();
            }
            if(i<5)
            {
                if(base[i][j]=='1') getcube[i][j]=Ub.getcol();
                if(base[i][j]=='2') getcube[i][j]=Ur.getcol();
                if(base[i][j]=='3') getcube[i][j]=Uf.getcol();
                if(base[i][j]=='4') getcube[i][j]=Ul.getcol();
            }
        }
        getcube[3][12]=Ru.getcol();
        getcube[4][11]=Ru.getcol();
    }//将这个立方体的实际输出放到getcube[][]字符数组中
}a[101][101][101];
inline void SolveUpColor()
{
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        int high=cnt[i][j];
        a[i][j][high].Ub=a[i][j][high].Uf=a[i][j][high].Ul=a[i][j][high].Ur=Col(light[2][2]);
        //light from up
        bool flag1=1,flag2=1;//flag1:left front,flag2:right back
        int curx=i-1,cury=j-1,curcnt=1;
        while(curx&&cury&&flag1){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=flag2=0;curx--;cury--;curcnt++;}
        curx=i;cury=j-1;curcnt=1;
        while(flag1&&curx&&cury){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;curx--;cury--;curcnt++;}
        curx=i-1;cury=j;curcnt=1;
        while(flag2&&curx&&cury){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag2=0;curx--;cury--;curcnt++;}
        if(flag1) Add(a[i][j][high].Ul,light[1][1]),Add(a[i][j][high].Uf,light[1][1]);
        if(flag2) Add(a[i][j][high].Ub,light[1][1]),Add(a[i][j][high].Ur,light[1][1]);
        //light from left back
        flag1=1;curx=i-1;cury=j;curcnt=1;
        while(flag1&&curx){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;curx--;curcnt++;}
        if(flag1)
        {
            Add(a[i][j][high].Ul,light[1][2]),Add(a[i][j][high].Uf,light[1][2]);
            Add(a[i][j][high].Ub,light[1][2]),Add(a[i][j][high].Ur,light[1][2]);
        }
        //light from back
        flag1=flag2=1;curx=i-1,cury=j+1;curcnt=1;//flag1:left back,flag2:right front
        while(flag1&&curx&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=flag2=0;curx--;cury++;curcnt++;}
        curx=i-1,cury=j;curcnt=1;
        while(flag1&&curx&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;curx--;cury++;curcnt++;}
        curx=i;cury=j+1;curcnt=1;
        while(flag2&&curx&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag2=0;curx--;cury++;curcnt++;}
        if(flag1) Add(a[i][j][high].Ul,light[1][3]),Add(a[i][j][high].Ub,light[1][3]);
        if(flag2) Add(a[i][j][high].Uf,light[1][3]),Add(a[i][j][high].Ur,light[1][3]);
        //light from right back
        flag1=1;curx=i;cury=j-1;curcnt=1;
        while(flag1&&cury){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;cury--;curcnt++;}
        if(flag1)
        {
            Add(a[i][j][high].Ul,light[2][1]),Add(a[i][j][high].Uf,light[2][1]);
            Add(a[i][j][high].Ub,light[2][1]),Add(a[i][j][high].Ur,light[2][1]);
        }
        //light from left
        flag1=1;curx=i;cury=j+1;curcnt=1;
        while(flag1&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;cury++;curcnt++;}
        if(flag1)
        {
            Add(a[i][j][high].Ul,light[2][3]),Add(a[i][j][high].Uf,light[2][3]);
            Add(a[i][j][high].Ub,light[2][3]),Add(a[i][j][high].Ur,light[2][3]);
        }
        //light from right
        flag1=flag2=1;curx=i+1;cury=j-1;curcnt=1;//flag1:left back,flag2:right front
        while(flag1&&curx<=n&&cury){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=flag2=0;curx++;cury--;curcnt++;}
        curx=i;cury=j-1;curcnt=1;
        while(flag1&&curx<=n&&cury){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;curx++;cury--;curcnt++;}
        curx=i+1;cury=j;curcnt=1;
        while(flag2&&curx<=n&&cury){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag2=0;curx++;cury--;curcnt++;}
        if(flag1) Add(a[i][j][high].Ul,light[3][1]),Add(a[i][j][high].Ub,light[3][1]);
        if(flag2) Add(a[i][j][high].Uf,light[3][1]),Add(a[i][j][high].Ur,light[3][1]);
        //light from left front
        flag1=1;curx=i+1;cury=j;curcnt=1;
        while(flag1&&curx<=n){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;curx++;curcnt++;}
        if(flag1)
        {
            Add(a[i][j][high].Ul,light[3][2]),Add(a[i][j][high].Uf,light[3][2]);
            Add(a[i][j][high].Ub,light[3][2]),Add(a[i][j][high].Ur,light[3][2]);
        }
        //light from front
        flag1=flag2=1;curx=i+1;cury=j+1;curcnt=1;//flag1:left front,flag2:right back
        while(flag1&&curx<=n&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=flag2=0;curx++;cury++;curcnt++;}
        curx=i+1;cury=j;curcnt=1;
        while(flag1&&curx<=n&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag1=0;curx++;cury++;curcnt++;}
        curx=i;cury=j+1;curcnt=1;
        while(flag2&&curx<=n&&cury<=m){if(cnt[curx][cury]-cnt[i][j]>=curcnt) flag2=0;curx++;cury++;curcnt++;}
        if(flag1) Add(a[i][j][high].Ul,light[3][3]),Add(a[i][j][high].Uf,light[3][3]);
        if(flag2) Add(a[i][j][high].Ur,light[3][3]),Add(a[i][j][high].Ub,light[3][3]);
        //light from right front
    }
}//处理顶面的颜色
inline void SolveRightColor()
{
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int high=1;high<=cnt[i][j];high++)
    {
        if(j<m&&cnt[i][j+1]>=cnt[i][j]) continue;
        int flag1,flag2;int curx,cury,curhigh;
        flag1=1;curx=i;cury=j+1;curhigh=high;
        while(flag1&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=0;cury++;curhigh++;}
        if(flag1)
        {
            Add(a[i][j][high].Rb,light[2][3]);Add(a[i][j][high].Rd,light[2][3]);
            Add(a[i][j][high].Rf,light[2][3]);Add(a[i][j][high].Ru,light[2][3]);
        }
        //light from right
        flag1=flag2=1;curx=i+1;cury=j+2;curhigh=high+1;//flag1:up back,flag2:front down
        while(flag1&&curx<=n&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx++;cury++;curhigh++;}
        curx=i+1;cury=j+1;curhigh=high+1;
        while(flag1&&curx<=n&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx++;cury++;curhigh++;}
        curx=i+1;cury=j+1;curhigh=high;
        while(flag2&&curx<=n&&cury<=m){if(cnt[curx][cury]>=curhigh) flag2=0;curx++;cury++;curhigh++;}
        if(flag1) Add(a[i][j][high].Ru,light[3][3]),Add(a[i][j][high].Rb,light[3][3]);
        if(flag2) Add(a[i][j][high].Rf,light[3][3]),Add(a[i][j][high].Rd,light[3][3]);
        //light from right front
        flag1=flag2=1;curx=i-1;cury=j+2;curhigh=high+1;//flag1:up front,flag2:down back
        while(flag1&&curx&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx--;cury++;curhigh++;}
        curx=i-1;cury=j+1;curhigh=high+1;
        while(flag1&&curx&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx--;cury++;curhigh++;}
        curx=i-1;cury=j+1;curhigh=high;
        while(flag2&&curx&&cury<=m){if(cnt[curx][cury]>=curhigh) flag2=0;curx--;cury++;curhigh++;}
        if(flag1) Add(a[i][j][high].Ru,light[1][3]),Add(a[i][j][high].Rf,light[1][3]);
        if(flag2) Add(a[i][j][high].Rd,light[1][3]),Add(a[i][j][high].Rb,light[1][3]);
        //light from right back
    }
}//处理右面的颜色
inline void SolveFrontColor(){
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int high=1;high<=cnt[i][j];high++)
    {
        if(i<n&&cnt[i+1][j]>=cnt[i][j]) continue;
        int flag1,flag2,curx,cury,curhigh;
        flag1=1;curx=i+2;cury=j;curhigh=high+1;
        while(flag1&&curx<=n){if(cnt[curx][cury]>=curhigh) flag1=0;curx++;curhigh++;}
        if(flag1)
        {
            Add(a[i][j][high].Fd,light[3][2]);Add(a[i][j][high].Fl,light[3][2]);
            Add(a[i][j][high].Fr,light[3][2]);Add(a[i][j][high].Fu,light[3][2]);
        }
        //light from front
        flag1=flag2=1;curx=i+1;cury=j+1;curhigh=high+1;//flag1:left up,flag2:right down
        while(flag1&&curx<=n&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx++;cury++;curhigh++;}
        curx=i+2;cury=j+1;curhigh=high+1;
        while(flag1&&curx<=n&&cury<=m){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx++;cury++;curhigh++;}
        curx=i+1;cury=j+1;curhigh=high;
        while(flag2&&curx<=n&&cury<=m){if(cnt[curx][cury]>=curhigh) flag2=0;curx++;cury++;curhigh++;}
        if(flag1) Add(a[i][j][high].Fl,light[3][3]),Add(a[i][j][high].Fu,light[3][3]);
        if(flag2) Add(a[i][j][high].Fr,light[3][3]),Add(a[i][j][high].Fd,light[3][3]);
        //light from right front
        flag1=flag2=1;curx=i+1;cury=j-1;curhigh=high+1;//flag1:right up,flag2:left down
        while(flag1&&curx<=n&&cury){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx++;cury--;curhigh++;}
        curx=i+2;cury=j-1;curhigh=high+1;
        while(flag1&&curx<=n&&cury){if(cnt[curx][cury]>=curhigh) flag1=flag2=0;curx++;cury--;curhigh++;}
        curx=i+1;cury=j-1;curhigh=high;
        while(flag2&&curx<=n&&cury){if(cnt[curx][cury]>=curhigh) flag2=0;curx++;cury--;curhigh++;}
        if(flag1) Add(a[i][j][high].Fr,light[3][1]),Add(a[i][j][high].Fu,light[3][1]);
        if(flag2) Add(a[i][j][high].Fl,light[3][1]),Add(a[i][j][high].Fd,light[3][1]);
        //light from left front
    }
}//处理前面的颜色
inline void print()
{
    ansh=0;answ=1+m*8+n*4;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ansh=max(ansh,1+4*(n-i+1)+8*cnt[i][j]);
    for(int i=1;i<=ansh;i++) for(int j=1;j<=answ;j++) ans[i][j]=' ';
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=cnt[i][j];k++)
    {
        int getx=ansh-4*(n-i)-8*(k-1),gety=1+(j-1)*8+(n-i)*4;
        a[i][j][k].Getcube();
        setit(getx,gety);
    }
    for(int i=1;i<=ansh;i++)
    {
        for(int j=1;j<=answ;j++) putchar(ans[i][j]);
        putchar('\n');
    }
}//输出不解释了
inline void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&cnt[i][j]);
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) cin>>light[i][j];
}
int main()
{
    init();
    SolveUpColor();
    SolveRightColor();
    SolveFrontColor();
    print();
    return 0;
}

本题在省选当中出现，还是比较可做的，毕竟省选有5个小时。

~~反正ZJOI考场上遇到这题我就头铁刚~~