P7914Solutionlink先考虑Subtask\(4\)。设\(dp_i\)表示长度为\(i\)的方案数，按题目定义转移:AB,ASB：\(\displaystyledp_n\getsdp_n+\sum_{i=1}^{n-1}\sum_{j=0}^kdp_i\timesdp_{n-i-j}\)(A)：\(\displaystyledp_n\getsdp_n+dp_{n-2}\)(SA),(AS)：\(\displa......

P7913Solutionlink先考虑有\(n\)个廊桥的分配。假设廊桥编号为\(1\simn\)，我们用两个堆\(h1,h2\)分别存当前空闲的廊桥编号和正在使用廊桥的飞机的离开时间。对于国内和国外的飞机分别做一次以下操作：先按到达时间排序，从左到右扫，到第\(i\)架飞机的到达、离开时间为\(l_......

P5384Solutionlink弱化这题空间\(\mathcalO(n\logn)\)会MLE。考虑怎么搞到\(\mathcalO(n)\)。首先求k级祖先用树剖空间是\(\mathcalO(n)\)的。然后看看我们建线段树的过程，我们发现每次查询都是在对应深度的线段树里查，那么考虑把询问离线，把节点、询问对应到深度......

P4845Solutionlink考虑树形dp，对于每个\(u\)直接钦定它的三种可能状态：有灯，没灯但是被其他灯照亮，没灯也没被照亮。这样钦定会导致一些需要被照亮的点在当前子树中还未被照亮，需要依靠子树外的灯来照亮。称这种点为闲置点。状态内只需要记录闲置点中最深的到子树根的距离，以及......

P4632Solutionlink对时间扫描线，就变成支持单点加入删除一个颜色点，求所有颜色距离某个点的距离最大值。考虑二分答案，现在就是要检验\([x-mid,x+mid]\)内是否有\(1\simk\)颜色的点各至少一个。数颜色可以考虑维护\(pre_i\)表示上一个与该点同色的位置。然后区间\([l,r]......

P4555Solutionlink双回文串的左右两半部分显然是互相独立的。于是考虑求出\(lm_i\)表示以\(i\)结尾的最长回文子串长度，\(rm_i\)表示以\(i\)开头的最长回文子串长度，最后扫一遍所有的分隔符求\(lm+rm\)的最大值即可。考虑如何求\(lm,rm\)。先用manacher拉出\(p\)，......

Link。首先我们假设在看本文章的所有人除了@左乐都已经使用点分树A掉了震波。然后我们要怎么简单修改A掉这个消息传递呢。震波是维护距离\(\leqk\)的点，这里只需要维护\(=k\)的，显然我们可以改掉维护前缀和的那个数据结构（比如树状数组），直接用普通数组/vector。跳......

P4137Solutionlink考虑建主席树：权值线段树的叶子维护这个权值最后出现的下标，push_up的时候取\(\min\)。这样一个区间的\(\min\)小于\(k\)意味着有一个权值最后出现的下标小于\(k\)，也就是说\(k\)后面没有出现这个权值。也就是说mex就在这个区间内。这样询问的时候......

P3990Solutionlink一次只能跳一步的情况下：\(dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}+dp_{i-1,j+1}\)接下来考虑能跳奇数步：你发现跳\(3\)步相当于先跳一个奇数\(1\)再跳一个\(2\)，跳\(5\)步相当于先跳一个奇数\(3\)再跳一个\(2\)也就是说能够一步跳到\((i,j)\)的一定能......

P3773Solutionlink\[\binomnm\bmod2=\binom{n\bmod2}{m\bmod2}\binom{n/2}{m/2}\bmod2\]我们要让\(\binomnm\bmod2\)不为\(0\)，也就是让右式的两项均不为\(0\)。考虑\(\binom{n\bmod2}{m\bmod2}\)：\(n\bmod2\)和\(m\bmod2\)的取值要么是\(0\)要么是\(1\)......