【题解】[APIO2020]T1粉刷墙壁

第一次参加apio

Posted by ethan-zhou on August 18, 2020

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

问题转化

理解题意之后我们不难发现,只要我们能算出是否有以 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;
	}
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接