Memphis's Blog

JC大爷搬了一堆好题到BZOJ上，一些题目比较水而一些题目比较不可做QAQ。

JC大爷好像还没放题解？那我就先把这些天刷掉的一些可做的PA题解写出来吧。。Blog不更总有一种罪恶感

part.1

[PA2014]Bohater：好像很明显是贪心把？我们把能补血的怪能打都打掉，然后按照回血量从大到小排序打就可以了。按照回血量排序需要仔细斟酌下，一开始我贪心错了QAQ。

[PA2014]Ciagi：吓退，留坑。

[PA2014]Druzyny：留坑。

[PA2014]Fiolki：首先能想到可持久化并查集，也就是按秩合并不路径压缩，应该是可以做的但是没必要而且复杂度是[tex]O(nlogn)[/tex]。我们可以留两个并查集，一个用来按秩合并，一个用来路径压缩，路径压缩来取得最高祖先，另外一个用来保留过程，由于我们时间有先后顺序，所以不妨按秩合并成一个二叉树，每次合并加进来一个点。最后我们的工作就是在按秩合并的树上寻找LCA计算答案，所以就是tarjanLCA，但是由于有先后关系。。所以在每个节点上还是要排一次，所以最坏复杂度依然是[tex]O(nlogn)[/tex]，但期望复杂度到不了。（其实按秩合并的并查集说的不对。。到最后其实就是一个二叉树了。。深度没有保证）

[PA2014]Iloczyn：不多说了，fib数列增长奇快，40项左右就可以了。

[PA2014]Kuglarz：好题，感觉好神QAQ。其实是最小生成树。。。因为奇偶是满足加减性质的，我们可以把一条边[tex](i,j)[/tex]当作前缀和相减[tex]p_j-p_{i-1}[/tex]，然后我们发现只要相邻两个点之间联通，就一定可以知道后一个点是否有球，所以就是最小生成树了。

[PA2014]Lustra：把w1,w2,h1,h2看作矩形坐标，显然只有面积最大的厂家才有可能成为满足条件的厂家，拿最大的判一下就好了，注意trick，第一次我WA了，换CF估计就fst了，o(︶︿︶)o 唉。

[PA2014]Muzeum：留坑。

[PA2014]Pakowanie：BZOJ终于好了，Stillwell验证爆搜是可过的，然后剪枝搞了搞就变成rk1了233333，后来发现状压也行。。不过状压不能剪枝对吧w

[PA2014]Parking：按照从左往右（从右往左同理）摆放顺序的话那么最右是最后一个放的，没有任何障碍，那我们就倒推，用树状数组维护前缀最值就可以了。

[PA2014]Plemiona：单调栈+扫描线。。把矩形都按x轴右端点排个序，插矩形的时候判交，那就是y轴上询问区间max，判了以后扩大该插入矩形并删除与其相交的矩形，删除的时候在其之前未相交的矩形就“露出来了”，所以就要用到单调栈，实现起来其实就是挂链表。。然后还有奇怪的情况会导致删单调栈中间的值，大概自己画几张图就知道是怎么回事了。。