注：本题解详细讲解了各部分分的得法以及对于正解的启发
问题转化
理解题意之后我们不难发现，只要我们能算出是否有以 i 块墙壁开始，刷 M 块墙的合法请求，那么这就转化成了一个区间覆盖问题。
比如：
样例1中，x=1，y=0 是一个合法请求，那么 [0,M-1] 就是一个合法区间（即：一次请求就可以覆盖这个区间）
找出这些区间之后，就可以做一个简单的贪心了，贪心代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/*
* 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]])
$$代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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;
}
}
|