A 邻面合并

考虑状压矩形的覆盖情况，因为我们本来就知道这一层的样子，所以二进制就能很好的解决，这一位是 1 表示从这一位一直是矩形的覆盖，直到遇到原来的 0 或者另一个 1，然后直接暴力转移即可。
赛时没有考虑到原来的样子，写了三进制压缩，把矩形覆盖看成栅栏，0 表示这个位置没有栅栏，1 表示放了一个栅栏，2 表示放了两个栅栏，暴力转移，但是细节和 conner case 很多。

#include<bits/stdc++.h>
#define pii std::pair<int,int>
#define eb emplace_back
#define fo(i,s,t) for(int i=s;i<=t;++i)
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=105;
int n,m,f[N][6600],len;
std::vector<int> t[N];
bool a[N][N];
struct ZHU{
    int w[10];
}b[6600];
inline bool yu(int s,int id){
    for(int i=1;i<=m;++i){
        if(a[id][i]&&!b[s].w[i])return 0;
        if(b[s].w[i]==1){
            if(!a[id][i])return 0;
            int po=i+1;
            for(;po<=m;++po){
                if(!a[id][po])return 0;
                if(b[s].w[po]==2)return 0;
                if(b[s].w[po]==1)break;
            }
            if(po>m)return 0;
            i=po;
            continue;
        }
        if(b[s].w[i]==2){
            if(!a[id][i])return 0;
        }
    }
    return 1;
}
signed main(){
    freopen("merging.in","r",stdin);freopen("merging.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),m=read();
    len=std::pow(3,m);
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=read();
    for(int i=1;i<=6580;++i){
        int zc=i,id=1;
        while(zc){
            int mo=zc%3;b[i].w[id]=mo;
            id++,zc/=3;
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;t[0].emplace_back(0);
    for(int i=1;i<=n;++i){
        for(int s=0;s<=len-1;++s){
            if(!yu(s,i))continue;
            for(int x:t[i-1]){
                int res=f[i-1][x];
                for(int j=1;j<=m;++j){
                    if(b[s].w[j]==1){
                        int num=0;
                        for(int k=1;k<j;++k){
                            num+=b[x].w[k];
                        }
                        if(b[x].w[j]==1&&(num&1)==0){
                            bool pd=1;
                            j++;while(b[s].w[j]!=1){
                                if(b[x].w[j]!=0)pd=0;
                                j++;
                            }
                            if(pd){
                                if(b[x].w[j]!=1)res++;
                            }else{
                                res++;
                            }
                        }else{
                            j++;
                            while(b[s].w[j]!=1)j++;
                            res++;
                        }
                        continue;
                    }
                    if(b[s].w[j]==2){
                        if(b[x].w[j]!=2)res++;
                    }
                }
                f[i][s]=std::min(f[i][s],res);
            }
            if(f[i][s]<1000)t[i].emplace_back(s);
        }
    }
    int ans=1000;
    for(int s=0;s<=len-1;++s){
        ans=std::min(ans,f[n][s]);
    }
    std::cout<<ans<<'\n';
}

B 光线追踪

想到维护斜率，但是精度炸了，加上离散化，对于矩形的横线和竖线分别维护，线段树上区间修改，单点最值，注意斜率为 \(0\) 或没有斜率的时候。赛时没有想到离散化。

#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define int long long
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=4e5+10,inf=1e9;
int n,cnt,len;
struct VCT{
    int x,y;
    inline bool operator<(const VCT&a)const{return y*a.x<a.y*x;}
}a[N];
int top=0;
struct OP{int op,x0,y0,x1,y1;}o[N];
struct TREE{pii ans,tag;}th[N<<2],ts[N<<2];
inline pii pmax(pii a,pii b){
    if(a.second==b.second)return a.first<b.first?b:a;
    return a.second<b.second?a:b;
}
inline void pushdown(TREE *t,int p){
    auto it=t[p].tag;
    t[ls].ans=pmax(t[ls].ans,it);t[rs].ans=pmax(t[rs].ans,it);
    t[ls].tag=pmax(t[ls].tag,it);t[rs].tag=pmax(t[rs].tag,it);
    t[p].tag.first=0;
}
inline void build(int p,int l,int r){
    th[p].ans={0,inf};ts[p].ans={0,inf};
    th[p].tag={0,inf};ts[p].tag={0,inf};
    if(l==r)return ;
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
}
inline void change(TREE *t,int p,int l,int r,int L,int R,pii x){
    if(l>=L&&r<=R){
        t[p].ans=pmax(t[p].ans,x);t[p].tag=pmax(t[p].tag,x);
        return ;
    }
    if(t[p].tag.first)pushdown(t,p);
    int mid=l+r>>1;
    if(L<=mid)change(t,ls,l,mid,L,R,x);
    if(R>mid)change(t,rs,mid+1,r,L,R,x);
}
inline pii query(TREE *t,int p,int l,int r,int pos){
    if(l==r){return t[p].ans;}
    int mid=l+r>>1;
    if(t[p].tag.first)pushdown(t,p);
    if(pos<=mid)return query(t,ls,l,mid,pos);
    else return query(t,rs,mid+1,r,pos);
}
signed main(){
    freopen("raytracing.in","r",stdin);freopen("raytracing.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();for(int i=1;i<=n;++i){
        int op=read();
        if(op==1){
            int x0=read(),y0=read(),x1=read(),y1=read();
            a[++top]={x1,y0},a[++top]={x0,y0},a[++top]={x0,y1};
            o[i]={op,x0,y0,x1,y1};
        }else{
            int x=read(),y=read();
            a[++top]={x,y};o[i]={op,x,y,0,0};
        }
    }std::sort(a+1,a+top+1);len=top;
    build(1,1,len);
    for(int i=1;i<=n;++i){
        if(o[i].op==1){
            int l=std::lower_bound(a+1,a+len+1,VCT{o[i].x1,o[i].y0})-a,
            mid=std::lower_bound(a+1,a+len+1,VCT{o[i].x0,o[i].y0})-a,
            r=std::lower_bound(a+1,a+len+1,VCT{o[i].x0,o[i].y1})-a;
            change(th,1,1,len,l,mid,{i,o[i].y0});
            change(ts,1,1,len,mid,r,{i,o[i].x0});
        }else{
            int pos=std::lower_bound(a+1,a+len+1,VCT{o[i].x0,o[i].y0})-a;
            auto ith=query(th,1,1,len,pos),its=query(ts,1,1,len,pos);
            if(!o[i].x0){
                if(o[ith.first].y0==o[its.first].y0){std::cout<<std::max(ith.first,its.first)<<'\n';continue;}
                if(o[ith.first].y0<o[its.first].y0){std::cout<<ith.first<<'\n';continue;}
                std::cout<<its.first<<'\n';continue;
            }
            if(!o[i].y0){
                if(o[ith.first].x0==o[its.first].x0){std::cout<<std::max(ith.first,its.first)<<'\n';continue;}
                if(o[ith.first].x0<o[its.first].x0){std::cout<<ith.first<<'\n';continue;}
                std::cout<<its.first<<'\n';continue;
            }
            int LL=ith.second*o[i].x0;its.second*=o[i].y0;
            if(LL==its.second){std::cout<<std::max(ith.first,its.first)<<'\n';continue;}
            std::cout<<(LL<its.second?ith.first:its.first)<<'\n';
        }
    }
}

C 百鸽笼

不会

D 滑稽树下你和我

不会