自动搬运

查看原文

来自洛谷，原作者为

	Assembly_line 我在无数个黄昏中寻找了十年，今夜，世界的星空将因我们而改变。

搬运于2025-08-24 23:07:59，当前版本为作者最后更新于2025-01-10 08:10:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

等了一周还没等到题解/qd。

做法来自官方题解。俄语翻译真的难以理解。

首先二分答案，判断前 $k$ 个批次能否全部满足要求。

将问题转为二分图匹配，左部点为每个机器人，右部点为每个位置（每个格子对应着 $q$ 个右部点），若机器人可以走到对应点则连边。

直接建出二分图显然会爆炸，考虑使用 hall 定理 进行判定。

根据 hall 定理，要对每一个子集进行判定，这样显然不可接受。考虑子集中存在移动能力为 $d$ 的一个机器人，那么移动能力 $\le d$ 的机器人都一定要被选进来，因为此时邻域大小 $|N(S)|$ 不变，而 $|S|$ 的大小增加，因此得到了一个更紧的限制。

于是将每个基地的机器人按照移动能力进行排序，枚举每个基地移动能力的最大值 $c_i$，统计每个基地移动能力 $\le c_i$ 的机器人个数总和 $s$，同时统计每个基地所对应的矩形的并的面积 $S$，若 $s\le S$ 则这个子集满足要求。

统计矩形面积并可以用容斥做到 $O(2^s)$。不完整批次的机器人个数可以用第 $k$ 批的机器人数量减去 $\max(s-S)$ 得到。

时间 $O\big(\big(\dfrac{2t}{s}\big)^s\log n\big)$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int w,h,s,q;
int ax[5],ay[5];
int n;
int b[103],d[103];
ll a[103];
//b:foundation
//a:number of bots
//d:distance
ll f[5];
int cnt[5],g[5];
struct node{
	ll x;int dis;
}p[5][103];
bool cmp(node x,node y){return x.dis<y.dis;}
struct rec{
	int ax,ay,bx,by;
}c[5],I;
rec merge(rec x,rec y)
{
	if(x.ax==-1||y.ax==-1)return I;
	if(x.ax==0)return y;
	if(y.ax==0)return x;
	rec c;
	c.ax=max(x.ax,y.ax);
	c.bx=min(x.bx,y.bx);
	c.ay=max(x.ay,y.ay);
	c.by=min(x.by,y.by);
	if(c.ax>c.bx||c.ay>c.by)c.ax=-1;
	return c;
}
ll sqm(rec x)
{
	if(x.ax<=0)return 0;
	return 1ll*(x.bx-x.ax+1)*(x.by-x.ay+1);
}
ll sq;
void calc(int x,int now,rec w)
{
	if(x>s)
	{
		if(now%2==0)sq-=sqm(w);
		else sq+=sqm(w);
		return;
	}
	calc(x+1,now,w);
	calc(x+1,now+1,merge(w,c[x]));
}
int flag;
ll res;
void dfs(int x)
{
	if(x>s)
	{
		for(int i=1;i<=s;i++)
		{
			if(g[i]==-1)c[i]=I;
			else
			{
				c[i].ax=max(1,ax[i]-g[i]);
				c[i].bx=min(w,ax[i]+g[i]);
				c[i].ay=max(1,ay[i]-g[i]);
				c[i].by=min(h,ay[i]+g[i]);
			}
		}
		sq=0;calc(1,0,(rec){0,0,0,0});
		ll ss=0;
		for(int i=1;i<=s;i++)ss+=f[i];
		if(sq*q<ss)flag=0,res=max(res,ss-sq*q);
		return;
	}
	f[x]=0;
	for(int i=0;i<=cnt[x];i++)
	{
		g[x]=p[x][i].dis;
		dfs(x+1);
		f[x]+=p[x][i+1].x;
	}
}
bool check(int x)
{
	flag=1;res=0;
	for(int i=1;i<=s;i++)cnt[i]=0,p[i][0].dis=-1;
	for(int i=1;i<=x;i++)
	{
		++cnt[b[i]];
		p[b[i]][cnt[b[i]]]=(node){a[i],d[i]};
	}
	for(int i=1;i<=s;i++)sort(p[i]+1,p[i]+cnt[i]+1,cmp);
	dfs(1);
	return flag;
}
int main()
{
	scanf("%d %d %d %d",&w,&h,&s,&q);
	for(int i=1;i<=s;i++)scanf("%d %d",&ax[i],&ay[i]);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d %lld %d",&b[i],&a[i],&d[i]);
	I.ax=-1;int ans=0;
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	check(ans+1);
	printf("%d %lld\n",ans,a[ans+1]-res);
	return 0;
}