BZOJ2707:「SDOI2012」走迷宫 – 题解

主要思路

这题细节真他妈多。

首先,看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了,比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候,从 queue 拿出顶点后先高斯消元一波,把环内的、SCC 之间的(也就是之前求出的 \(dp[u]\))一起放到方程组里进行消元即可。细节看代码吧,真的呕了。

继续阅读BZOJ2707:「SDOI2012」走迷宫 – 题解

P4577:[FJOI2018]领导集团问题 – 题解

树上 LIS 的套路之一

因为是从 yyb 博客上抓的题,所以知道可以用线段树做。大概想了想,初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的,输入高度时就先塞到每个点的动态开点线段树里,然后就可以把儿子的进行合并。合并儿子的时候,维护至少为 \(x\) 时能得到的最长子序列长度,所以我们可以用差分的方式来做一做(当然也可以做标记永久化的区间加):从 \(w_u\) 的位置开始加上一个一,然后把上一次的 \(1\) 给删掉。

继续阅读P4577:[FJOI2018]领导集团问题 – 题解

BZOJ4709:「JSOI2011」柠檬 – 题解

主要思路

首先发现两端并不会影响,所以可以直接做分段的线性 DP。正常思考暴力,发现每次都需要枚举颜色,非常麻烦。但是我们可以发现一个特别好的性质:每一次区间的颜色都取决于这个区间的最后一个元素,因为意识到选其他颜色时,我们大可把这个区间的右端点进行调整,使得下一个区间不会更劣。

继续阅读BZOJ4709:「JSOI2011」柠檬 – 题解

AtCoder Regular Contest 101F:Robots and Exits – 题解

主要思路

好题好题。

我们发现每一个点向左、向右走都是有极限的,算出得到 \((x_i, y_i)\),其中 \(x\) 代表左边、\(y\) 代表右边。那么,把这个东西放到散点图上,发现我们本质不同的操作是一个单调不降的折线图:因为如果我们把 \(x\) 作为这个路径的「最长向左移动距离」、\(y\) 作为这个路径的「最长向右移动距离」,那么这个折线经过某个点的 \(x\) 帧或是 \(y\) 帧都将导致这个东西 GG,所以我们计算这样的折线图就可以计算对应方案了。

我们可以直接用树状数组来进行转移即可。

继续阅读AtCoder Regular Contest 101F:Robots and Exits – 题解

Codeforces 933E:A Preponderant Reunion – 题解

主要思路

想了半天都不知道怎么刻画状态,后面发现可以转成一个泛化问题,就比较好理解了。

考虑不严格地减去最小值、而是任意值,并达到题目要求的结果。这个问题肯定不会更优,而最优解可以直接作为本题最优解。

继续阅读Codeforces 933E:A Preponderant Reunion – 题解