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 滑稽树下你和我
不会
标签：std,ch,return,int,long,41,CSP,模拟,define From： https://www.cnblogs.com/Ishar-zdl/p/18453099