前言

T1 状压挂了 \(10pts\)，貌似做法是假的，但是一下午也没调出来哪儿假了，但是错误率很低，几百组能有一组错的。

T2 赛时数据锅了赛后重测了，赛时想到线段树但是没能具体实现，最后无奈写暴力。

T3、T4 没看。

T1 邻面合并

\(m\le 8\) 所以考虑状压表示每一行哪些地方被覆盖，对与相邻两行的状态进行合并转移即可。

#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=110,M=310;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,mx,ans=0x3f3f3f3f,f[N][M],g[M][M]; vector<int>e[N];
int calc(int s,int t)
{
	if(g[s][t]!=-1) return g[s][t]; int res=0;
	for(int i=0,now=0;i<=m;i++) if(!((t>>i)&1))
	{
		if(now>=i) {now=i+1; continue;}
		if((s>>i)&1) res++;
		else if(now&&((s>>(now-1))&1)) res++;
		else for(int j=now;j<=i-1;j++) if(!((s>>j)&1)) {res++; break;}
		now=i+1;
	}
	return g[s][t]=res;
}
signed main()
{
	freopen("merging.in","r",stdin),freopen("merging.out","w",stdout);
	read(n,m),mx=(1<<m)-1;
	for(int i=1,sta;i<=n;i++)
	{
		sta=0; for(int j=1,x;j<=m;j++) read(x),sta|=x<<(j-1);
		for(int j=0;j<=mx;j++) if((j|sta)==sta) e[i].push_back(j);
	}
	memset(f,0x3f,sizeof(f)),memset(g,-1,sizeof(g));
	for(int s:e[1]) f[1][s]=calc(0,s)+calc(0,e[1].back()^s);
	for(int i=2;i<=n;i++) for(int s:e[i]) for(int t:e[i-1]) 
		f[i][s]=min(f[i][s],f[i-1][t]+calc(t,s)+calc(e[i-1].back()^t,e[i].back()^s));
	for(int s:e[n]) ans=min(ans,f[n][s]);
	write(ans);
}

T2 光线追踪

• 部分分 \(30pts\)：直接暴力。

• 正解：

  以角度为下标开线段树，对于每个矩形对应一段连续的角度区间，所以是区间修改最小值；每次查询对应一个角度，单点查询最小值。

  由于最小值不好处理不放开两棵线段树，一个存横坐标一个存纵坐标，最后根据斜率比较这两个哪一个先碰到即可。

  对于实现的细节，可以使用离散化处理，由于是单点查区间修，所以不用 pushup 但是需要 pushdown。

  点击查看代码

  #include<bits/stdc++.h>
  #define ll long long 
  #define endl '\n'
  #define sort stable_sort
  using namespace std;
  const int N=1e5+10; const double eps=1e-8;
  template<typename Tp> inline void read(Tp&x)
  {
      x=0;register bool z=true;
      register char c=getchar_unlocked();
      for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
      for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
      x=(z?x:~x+1);
  }
  template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
  template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
  template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
  template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
  int n,m;
  struct aa {int op,x1,y1,x2,y2;}e[N];
  struct bb 
  {
      int x,y;
      bool operator < (const bb &a) const {return 1ll*y*a.x<1ll*a.y*x;}
      bool operator == (const bb &a) const {return 1ll*y*a.x==1ll*a.y*x;}
  }b[N<<2];
  struct cc
  {
      int val=1e9,id=0;
      bool operator < (const cc &a) const {return val==a.val?id>a.id:val<a.val;}
  };
  struct tree
  {
      #define ls (p<<1)
      #define rs (p<<1|1)
      #define mid (l+r>>1)
      cc val[N<<4],add[N<<4];
      void spread(int p)
      {
          if(add[p]<val[ls]) val[ls]=add[ls]=add[p];
          if(add[p]<val[rs]) val[rs]=add[rs]=add[p];
          add[p]=(cc){(int)1e9,0};
      }
      void change(int p,int l,int r,int vl,int vr,cc d)
      {
          if(vl<=l&&vr>=r) 
          {
              if(d<val[p]) val[p]=add[p]=d;
              return ;
          }
          if(add[p].id) spread(p);
          if(vl<=mid) change(ls,l,mid,vl,vr,d);
          if(vr>mid) change(rs,mid+1,r,vl,vr,d);
      }
      cc ask(int p,int l,int r,int x)
      {
          if(l==r) return val[p];
          if(add[p].id) spread(p);
          return x<=mid?ask(ls,l,mid,x):ask(rs,mid+1,r,x);
      }
  }t1,t2;
  signed main()
  {
      freopen("raytracing.in","r",stdin);
      freopen("raytracing.out","w",stdout);
      read(n);
      for(int i=1,op,x1,y1,x2,y2;i<=n;i++)
      {
          read(op,x1,y1); 
          if(op&1) read(x2,y2),b[++m]=(bb){x1,y2},b[++m]={x2,y1};
          e[i]=(aa){op,x1,y1,x2,y2},b[++m]=(bb){x1,y1};
      }
      sort(b+1,b+1+m),m=unique(b+1,b+1+m)-(b+1);
      for(int i=1,op,x1,y1,x2,y2;i<=n;i++)
      {
          op=e[i].op,x1=e[i].x1,y1=e[i].y1,x2=e[i].x2,y2=e[i].y2;
          if(op&1)
          {
              int s1=lower_bound(b+1,b+1+m,(bb){x2,y1})-b,
                  s2=lower_bound(b+1,b+1+m,(bb){x1,y1})-b,
                  s3=lower_bound(b+1,b+1+m,(bb){x1,y2})-b;
              if(y1) t1.change(1,1,m,s1,s2,(cc){y1,i});
              if(x1) t2.change(1,1,m,s2,s3,(cc){x1,i});
          }
          else
          {
              int s=lower_bound(b+1,b+1+m,(bb){x1,y1})-b;
              cc ans1=t1.ask(1,1,m,s),ans2=t2.ask(1,1,m,s);
              if(!ans1.id) write(ans2.id);
              else if(!ans2.id) write(ans1.id);
              else
              {
                  double k=1.0*y1/x1;
                  write((1.0*ans1.val-1.0*ans2.val*k<-eps||(abs(1.0*ans1.val-1.0*ans2.val*k)<=eps&&ans1.id>ans2.id))?ans1.id:ans2.id);
              }
              puts("");
          }
      }
  }
  

T3 百鸽笼

还没打。

T4 滑稽树下你和我

还没打。