自动搬运

查看原文

来自洛谷，原作者为

	ethan_zhou 博客：blog-e.top

搬运于2025-08-24 22:23:44，当前版本为作者最后更新于2020-08-19 21:07:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

(本题解在博客页面显示正常)

注：本题解详细讲解了各部分分的得法以及对于正解的启发

问题转化

理解题意之后我们不难发现，只要我们能算出是否有以 i 块墙壁开始，刷 M 块墙的合法请求，那么这就转化成了一个区间覆盖问题。

比如： 样例1中，x=1，y=0 是一个合法请求，那么 [0,M-1] 就是一个合法区间（即：一次请求就可以覆盖这个区间）

找出这些区间之后，就可以做一个简单的贪心了，贪心代码如下：

/* 
 * canpaint[i]表示有没有从第i块开始的合法区间
 * lastr表示目前匹配到的右端点
 * newl表示下一个合法区间的左端点
 */
int lastr=-1,newl=0,ans=0;
while(lastr<N-1){
	int mxl=-1;
	while(newl<=lastr+1 && newl<N){
		if(canpaint[newl])mxl=newl;
		newl++;
	}
	if(mxl==-1)return -1;
	lastr=mxl+M-1;
	ans++;
}

预处理

但是，我们做完了吗？并没有。这题的不好搞的地方在于 canpaint 数组的预处理。

28分

NM^2 的暴力，枚举每个 x 和 y，并暴力匹配，能得到第二组和第三组的分数，代码过于简单，略。

51分

写一个dp，令 f[i][j] 表示从第 j 个商家，第i块墙壁开始匹配，最多能刷几块墙，则其转移如下

$$f[i][j]=\left\{ \begin{aligned} &0&（第j个商家不能刷第i个墙）\\ &f[i+1][(j+1)mod M]&（第j个商家能刷第i个墙） \end{aligned} \right. $$

但是 NM 的空间显然是存不下的，所以你需要将i那一维滚动掉，最终的时间复杂的也是 NM。

注：这里必须使用滚动数组，而不能使用其他方法，否则将无法保证后效性，因为这里的转移模了 M。

63分

观察数据特点：f(k)<1，我们可以利用这点来优化我们的dp，即：在转移时只转移喜欢 C[i] 这个颜色的那个商家即可，这个思路也给正解打下了基础，但至于加了这个优化之后，滚动时怎么清零之前计算的结果，待会会说。

100分

再看整体的数据范围，发现 f(k) 还是很小，所以我用一个 vector 数组 like[i] 表示喜欢第 i 种颜色的商家编号，转移如下：

$$f[i][j]=f[i+1][(j+1)modM](j \in like[C[i]])$$

代码如下

for(int i=0;i<M;i++)
	for(int j=0;j<A[i];j++)
		like[B[i][j]].push_back(i);
for(int l=N-1;~l;l--){
	/*
	 * 每次使用like[l&1]这一行，就可以不用重新赋值
	 * 由于上次使用like[l&1]这一行是在l=l+2是
	 * 所以需要清除like[l&1][k]，当且仅当k在like[C[l+2]]中
	 */
	int tlsize=like[C[l+2]].size();
	for(int i=0;i<tlsize;i++)
		mxl[l&1][like[C[l+2]][i]]=0;
	//lsize表示喜欢当前墙壁颜色的公司数量
	int lsize=like[C[l]].size();
	for(int i=0;i<lsize;i++){
		//curc表示当前公司
		int curc=like[C[l]][i];
		mxl[l&1][curc]=mxl[!(l&1)][(curc+1)%M]+1;
		if(mxl[l&1][curc]>=M)canpaint[l]=1;
	}
}