CSPS模拟 93

    恰饭的时候lsc说我颓颓废废是要ak的前兆

    所以我rp掉光了=。=

    T1

      思维一片混乱

    T2

      只会n^3

      发现决策单调性,但没想全

      只知道$determin(l,r)>=determin(l,r-1)$,不知道$determin(l,r)<=determin(l+1,r)$

      然后只优化了下界,T50..

      颓了题解,深感决策单调性之神奇

      优化了一下上界,结果直接又加了50..

      多想想OAO决策单调性是有两种的

      复杂度很好证。

    T3

      分治消元。

      分的是元,也是方程。

      如果只分元,消哪个方程任意的话,

      就会「数据删除」

      至于为什么会「数据删除」

      我认为他的具体原因在于「数据删除」

      综上,消第i个元时必须使用第i个方程。

      于是只要再「数据删除」一下,这题就可以通过。

      注意,当消完[l,mid]区间递归[mid+1,r]之后,[mid+1,r]的一切操作不可与[l,mid]有关。

      只有结尾回带的时候才会遍历整个矩阵。

原文地址:https://www.cnblogs.com/yxsplayxs/p/11762915.html