一行超人

愉快爆零滚粗 要是时间是5h就好了

B.4003: [JLOI2015]城池攻占

想通了之后发现这个问题其实并不难。。。

暴力每个点往上爬复杂度是O（n*m）的。好像因为数据水的原因可以拿到50

我是从链上的情况得到启示的。

链上的话你怎么处理？肯定不能还是一个一个处理，那我们就考虑从最下面开始往上跳，维护一个当前骑士的集合。

每次到了一个点，首先把攻击力<=h[x]的骑士踢出这个集合，然后我们让所有的活着的骑士执行操作（加战斗力或者乘）.

当然让每个骑士执行操作还是O（n*m）的，但我们可以不给骑士执行，而给城池加。

乘的数>0保证了给一些数进行操作，取到最小值的还是那个数。

比如说要判断a*x+b<=c，只要x<=(c-b)/a，也就是说我们只要让x不变，不断操作我们的a，b即可。这样O（n+m）可以过掉那20%的数据。

返回原来的问题，我们发现不同子树的a，b是不一样的，那我们就不能更改a，b了。那我们只好对整个骑士集合改变了。

我们需要快速合并以及查询最小值，这个可并堆可以实现。但是让一个可并堆整体+或*一个数我不会。于是就放弃了。

转而考虑线段树，线段树进行区间修改是O（logn）的，所以如果每个子树的骑士正好是一段连续的区间我们就可以用线段树实现了。

这也十分简单，我们给所有的骑士重新按照dfs序编号即可！

什么？线段树合并怎么是O（nlogn）的？

戳前面的博文：线段树合并

但是。。。这样内存是O（nlogn）的，会被卡成暴力分。

于是我开始卡内存，比如线段树合并的时候会有节点成为废节点，那我们就回收一下。

然后就巧妙的过掉了官方数据。BZOJ上RE了

UPD：

其实可合并堆也是可以打标记的，而且写起来比线段树简洁多了！让你考试的时候不细想！

其实这题把线段树换成splay就不卡内存啦！而且不用重标号了，因为不是区间修改而是整体修改啦！

B.4004: [JLOI2015]装备购买

其实这是道水题。。。看见之后就像从小到大排序能加就加。

但是怎么判断能不能加呢？

我只在异或方程组的时候接触了线性基，所以认为线性基可能不能用于一般的解方程中。

于是就想直接暴力高斯消元把，大概有70分。可是开始写之后发现判断是否有解的高斯消元好麻烦啊，而且当时离考试结束只有1h了，就弃了这道题。

下来看了popoqqq的代码发现这题用线性基直接O（n^3）QAQ

以后不能局限于自己用过的东西，比如这次考试里面对于可合并堆打标记以及一般的高斯消元用线性基。要有创新！

不过线性基就是处理这些线性相关的比较顺手？

然后发现了精度问题 判断一个数是否非零，设的事1e-5的时候刚好AC，比这个小一点会不同程度的失分

这种精度问题该怎么确定eps啊？求神犇解答

A.4002: [JLOI2015]有意义的字符串

看了题目卧槽这什么鬼，怎么都要爆啊。。。

看了题解，哇塞好神啊 可是这种题真的有想出来的可能性吗？

觉得没什么意思，戳题解