防止过了几个月就忘了

单位复根 $\omega_n=e^{\frac{2\pi i}{n}}=\cos\left(\dfrac{2\pi}{n}\right)+i\cdot \sin\left(\dfrac{2\pi}{n}\right)$

性质

$$\begin{aligned} \omega_n^n&=1\\ \omega_n^k&=\omega_{2n}^{2k}\\ \omega_{2n}^{k+n}&=-\omega_{2n}^k\\ \end{aligned}$$

换根 dp 模板题

设 $f(x,d)$ 表示在 x 的子树中，与 x 距离为 d 的点值之和。
设 $g(x,d)$ 表示与 x 相距 d 的点之和

$$g(x,d)=f(x,d)+g(fa,d-1)-f(x,d-2)$$

答案为 g 的前缀和

区间 dp ，注意枚举端点 i，j，k 的顺序，模拟一下就好了，如果使用了未更新的状态，就是错的

sorry for that i don’t have a chinese input method

Functions:

g(x, l, r) means we have the largest cow which can eat pos(x) , and it can only affect pies in [l, r]

P2569 (SCOI2010)股票交易

巧妙的单调性优化

设 $f(t,x)$ 表示第 $t$ 天，手持 $x$ 只股票时的最大利润，显然有几种转移方式

1. 在第 $t$ 天什么也不做

   $$f(t,x)=f(t-1,x)$$

2. 在第 $t$ 天买进股票，刚好买 $x$ 只

   $$f(t,x)=-xAP_i$$

3. 在第 $t$ 天买进股票

   $$f(t,x)=\max\limits_{1\le x'\le AS_i}(f(t-w-1,x-x') - x'AP_i)$$

   为什么是 $t-w-1$ 呢，假设实际上上一次操作是在第 $t'$ 天，那么就相当于从第 $t'$ 天到第 $t-w-1$ 天什么也不做，这种情况在上面已经考虑过了，所以答案 $f(t-w-1,x-x')$ 不会比 $f(t',x-x')$ 小。

4. 在第 $t$ 天卖出股票

   $$f(t,x)=\max\limits_{1\le x'\le BS_i}\left(f(t-w-1,x+x')+x'BP_i\right)$$

CF372C Watching Fireworks is Fun

单调队列优化区间 dp

设 $f(i,j)$ 表示放到第 $i$ 个烟花，当前在 $j$ 的位置，设可以在两次烟花之间的移动距离为 $s$ 可以发现

$$f(i,j)=\min\limits_{j-s\le k\le j +s}(f(i,k))+b_i-\vert a_i-j\vert$$

P1712 [NOI2016]区间
status

线段树维护单点最大值+队列

这两天考的都是 USACO 的题

USACO 2019 December Contest, Platinum

pieaters

区间 dp ，注意枚举端点 i，j，k 的顺序，模拟一下就好了，如果使用了未更新的状态，就是错的

改题去了，等会填坑

这两天考了学长出的一套省选模拟题。（似乎是 Matthew99 /se

Day 1

A

建出 SAM 后就是在 parent tree 上找 LCA。

HNOI2021 模拟赛记录。