拉格朗日插值法

给定`n`个点`(x_i,y_i)`来确定一个多项式并将`k`代入求值

对于这个问题我们可以用高斯消元法以`\mathcal{O}(n^3)`的时间复杂度进行求解

但是有一种`\mathcal{O}(n^2)`的方法,名为拉格朗日插值法

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{i \ne j}{\frac{x-x_j}{x_i-x_j}} $$

这东西就跟FFT一样烦,DP转移式推着推着发现需要用到拉格朗日插值法


「Codeforces 739B」Alyona and a tree - 倍增 + 差分

给定一棵节点数为`n`的树

这棵树的根节点为`1`

这棵树有点权`val_i`和边权`dis_i`

定义`dist(u,v)`为从`u`到`v`的简单路径上的边权和

顶点`u`控制顶点`v`,当且仅当`v`在`u`的子树中且`dist(u,v) \le val_v`

求每个顶点`u`能控制几个顶点

`1 \le n \le 2 \times 10^5`


「Luogu P1306」斐波那契公约数 - 数论 + 矩阵加速

给定正整数 `n` 和 `m`

Fibonacci数列第 `n` 项和第 `m` 项的最大公因数

`n,m \le 10^9`


2018 学车校赛 游记

Day -1

第一次参加 ACM 赛制的比赛

有点小激动

复习了下数据结构

Day 0

起床看到窗外白雪飘飘

看来是杭州这个冬天的初雪

在家吃完午饭打车到了学车

到校门口后另外两位队友还没来

在保安室等了 15 min 顺便想了下刚学的算法

冻死了

队友来了后一起去签到处签到

然后直接进机房准备了

学车机房都是 Linux Ubuntu

忘了看配置

自带 vscode 还是很舒服的

坐下来后发现机房里很多人不会直接用 g++ 编译

坐下来后发现左边的对面就是 Samsara-Karma 巨佬

暗暗地膜了一下

在离结束几个小时的时候 Samsara-Karma 他们队就 AK 离场了

真是太巨了

(由于这篇 blog 是后来补的,时间比较久远,笔者已经记不太清做题的细节了,此处省略,挺可惜的)

还有半个小时就要结束了

题目看来看去没有突破口

外面环境比较恶劣 想着早点回家

便提前离场了

归途上跟两位队友打了雪仗

最后一起在 Dilemma 家吃了外卖

甚是开心

「CQOI 2007」余数求和 - 除法分块

给定正整数`n`和`k`

求 `ans = \sum_{i = 1}^n k%i`

要求 `\mathcal{O}(\sqrt{k})` 时间复杂度


分块

分块,一种优美的暴力

分块在时间上跟线段树差不多快,空间上优于线段树

分块还可以解决许多线段树不能解决的问题

而且因为分块是一种线性结构,所以分块算法更易理解

不仅如此,分块甚至可以在许多题目当中骗到可观的分数,是我等蒟蒻最喜爱的暴力算法之一


hello, world

hello, world

蒟蒻TosakUCW的博客算是勉强上线了

之前就有过这样的想法,但是因为懒一直没有做

后来搞了个windowsIIS搭的博客 (Hamakaze学长的主意)

顺便花了2个晚上的时间自学了htmlcss

并自己写了一个雏形出来

后来又花了一个晚上用html+css写了兼容移动端低分辨率下的布局

然后接着维护博客剩下的内容,然后因为各种动态页面,就猝死了 (还是因为懒)

所以就改成了现在这样Hexo Icarus+GitHub Pages

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×