群论

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

A – 单调

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

题意简述

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

More
  • 2023年2月9日

牛顿迭代法

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

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

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

在多项式域上函数的推广

多项式域

(更多…)

More
  • 2022年6月24日

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

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

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

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

(更多…)

More
  • 2022年1月24日