20210218 模拟赛总结
Index Review 考的不错,主要是第一题做出来了,分数可观, 140pts。 但是后面两题的暴力分也没有打满,这是做的不够的一点。 Solution pk 定义 f(n,k)=(n−k+1)!∑i=0k−1(n−ki)(kj−i−1)f(n,k)=(n-k+1)!\sum_{i=0}^{k-1}\dbinom{n-k}{i}\dbinom{k}{j-i-1}f(n,k)=(n−k+1)!∑i=0k−1(in−k)(j−i−1k) ,求 ∑i=LRf(i+s,i)\sum\limits_{i=L}^{R}f(i+s,i)i=L∑Rf(i+s,i) 经过打表可以发现 f(n,n)=nf(n,n)=nf(n,n)=n 和 f(n,k)=f(n,k+1)⋅kf(n,k)=f(n,k+1)\cdot kf(n,k)=f(n,k+1)⋅k 化简得 f(n,k)=n!(k−1)!f(n,k)=\dfrac{n!}{(k-1)!}f(n,k)=(k−1)!n! type=1 首先考虑 type=1 的情况,代入式子即得...
20210217 模拟赛总结
Index Review T1 难度较低,写了正解,T2、T3写了暴力,不知道 T2 为什么没有分,120pts. 要注意看题,差点就把 T1 看错了,导致误判难度。还有要注意题目中的数据范围,比如 T2 k≤5k\le5k≤5 就是一个很好的入手条件。 Solution T1 god 在平面直角坐标系中,在 x 负半轴有一些位置,编号 111 ~ nnn ,正半轴有 mmm 个点 (si,0)(s_i,0)(si,0) 。每个点有一个移动向量 (xi,yi)(x_i,y_i)(xi,yi) 每一秒按此向量移动 (0≤xi,yi≤1050\le x_i,y_i\le 10^50≤xi,yi≤105) ,每个点的价值为它到编号为 [li,ri][l_i,r_i][li,ri] 区间内位置的曼哈顿距离和,qqq 个询问,每个询问给定 ttt ,求 yyy 时刻每个点价值的最小值。 设点 i 对时间的价值函数为 valival_ivali 由于点只会往右上方跑,所以 valival_ivali...
FFT 笔记
防止过了几个月就忘了 单位复根 ωn=e2πin=cos(2πn)+i⋅sin(2πn)\omega_n=e^{\frac{2\pi i}{n}}=\cos\left(\dfrac{2\pi}{n}\right)+i\cdot \sin\left(\dfrac{2\pi}{n}\right)ωn=en2πi=cos(n2π)+i⋅sin(n2π) 性质 ωnn=1ωnk=ω2n2kω2nk+n=−ω2nk\begin{aligned} \omega_n^n&=1\\ \omega_n^k&=\omega_{2n}^{2k}\\ \omega_{2n}^{k+n}&=-\omega_{2n}^k\\ \end{aligned} ωnnωnkω2nk+n=1=ω2n2k=−ω2nk 位逆序置换: R(x)=⌊R(⌊x2⌋)2⌋+(x mod 2)×len2R(x)=\left\lfloor \frac{R\left(\left\lfloor \frac{x}{2} \right\rfloor\right)}{2}...
P2986 (USACO10MAR) Great Cow Gathering G
换根 dp 模板题 设 f(x,d)f(x,d)f(x,d) 表示在 x 的子树中,与 x 距离为 d 的点值之和。 设 g(x,d)g(x,d)g(x,d) 表示与 x 相距 d 的点之和 g(x,d)=f(x,d)+g(fa,d−1)−f(x,d−2)g(x,d)=f(x,d)+g(fa,d-1)-f(x,d-2) g(x,d)=f(x,d)+g(fa,d−1)−f(x,d−2) 答案为 g 的前缀和
P5851 (USACO19DEC) Greedy Pie Eaters P
区间 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] f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r] So we have the things below: 12345678910111213foreach cow_i foreach x in range[l_i, r_i] g(x, l_i, r_i) = w_i;foreach k in [1 -> n] foreach i in [k -> 1], j in [k...
P2569 (SCOI2010)股票交易
P2569 (SCOI2010)股票交易 巧妙的单调性优化 设 f(t,x)f(t,x)f(t,x) 表示第 ttt 天,手持 xxx 只股票时的最大利润,显然有几种转移方式 在第 ttt 天什么也不做 f(t,x)=f(t−1,x)f(t,x)=f(t-1,x) f(t,x)=f(t−1,x) 在第 ttt 天买进股票,刚好买 xxx 只 f(t,x)=−xAPif(t,x)=-xAP_i f(t,x)=−xAPi 在第 ttt 天买进股票 f(t,x)=max1≤x′≤ASi(f(t−w−1,x−x′)−x′APi)f(t,x)=\max\limits_{1\le x'\le AS_i}(f(t-w-1,x-x') - x'AP_i) f(t,x)=1≤x′≤ASimax(f(t−w−1,x−x′)−x′APi) 为什么是 t−w−1t-w-1t−w−1 呢,假设实际上上一次操作是在第 t′t't′ 天,那么就相当于从第 t′t't′ 天到第 t−w−1t-w-1t−w−1...
CF372C Watching Fireworks is Fun
CF372C Watching Fireworks is Fun 单调队列优化区间 dp 设 f(i,j)f(i,j)f(i,j) 表示放到第 iii 个烟花,当前在 jjj 的位置,设可以在两次烟花之间的移动距离为 sss 可以发现 f(i,j)=minj−s≤k≤j+s(f(i,k))+bi−∣ai−j∣f(i,j)=\min\limits_{j-s\le k\le j +s}(f(i,k))+b_i-\vert a_i-j\vert f(i,j)=j−s≤k≤j+smin(f(i,k))+bi−∣ai−j∣ 用单调队列维护,加滚动数组,时间复杂度 O(nm)O(nm)O(nm) ,空间复杂度 O(n)O(n)O(n)
P1712 (NOI2016) 区间
P1712 [NOI2016]区间 status 线段树维护单点最大值+队列 注意的一点:在下图时 12105 | while (res(1) == m && pos <= i) { | ...
20210206~07 考试总结
这两天考的都是 USACO 的题 USACO 2019 December Contest, Platinum pieaters 区间 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] f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r] So we have the things below: 12345678910111213foreach cow_i foreach x in range[l_i, r_i] g(x, l_i, r_i) =...
20210129 考试总结
改题去了,等会填坑