NGC5457's Site

标签： 群论

  • MOCK NOIP 20231027 T2 – 缺金木 – 线段树的“双半群”模型

    题意简述

    给定长为 $n$ 的序列 $a$。要求支持以下操作：

    • 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部加上 $x$；
    • 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部乘以 $x$；
    • 给定 $l,r,x$，若这是第 $k$ 次操作，则保护 $a_i,l\leq i\leq r$ 直到第 $k+x$ 次操作（含），这期间操作 $1,2$ 对 $a_i$ 无效。若 $a_i$ 已经被保护到 $x’,x’>k+x$，则这一保护不会失效。
    • 给定 $l,r$，输出 $\sum_{i=l}^{r} a_i$，对 $10^9+7$ 取余。

    $n,m\leq 2\times 10^5$。

    半群、双半群模型——线段树到底能维护怎样的信息？——caijianhong 的博客园

    （更多…）

  • MOCK quasi-PTS 20230209 日志

    近一个月来第一次赛时通过一道题。真是可喜可贺。

    A – 单调

    一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。

    题意简述

    给定长为 $\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)$ 的序列 $\langle a_i\rangle,a_i\in\{1,2,3\}$。匹配尽可能多的子序列，每个子序列均为 $\langle 1,2,3\rangle$ 或 $\langle 3,2,1\rangle$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）

  • 牛顿迭代法求多项式域上函数的零点

    牛顿迭代法

    牛顿迭代法使用泰勒级数的前若干项求出函数零点的近似解。

    令 $x_0$ 为我们选定的一个接近函数 $f(x)$ 零点的横坐标。则我们进行若干次迭代。有
    $$
    x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}
    $$

    若 $x_0$ 选择得足够接近根 $\alpha$，迭代若干次就可以得到近似解。实际上，每进行一次迭代，解的精度变为原来的 $2$ 倍。

    在多项式域上函数的推广

    多项式域

    （更多…）

  • AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP

    昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。

    由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。

    今天查看题解，发现有几个重要的，从未考虑过的trick：

    1. 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
    2. 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。

    （更多…）