Cauphenuny's Blog

Review 考试时一直在肝论文，发现 2017 国集论文里面有决策单调性优化 dp 的内容，终于在考试最后 2 分钟调过样例。 结果因为没有滚数组导致 MLE，沦为暴力 20pts。 Solution T1 hike nnn 个点， qqq 个询问 两种询问，分别是合并两树和查询树中里给定点最远的点的距离 LCT 维护树的直径板子题 O(nlog⁡n)O(n\log n)O(nlogn)，可惜我不会，只好启发式合并暴力处理倍增数组。 考虑两颗树的直径端点 a,b,c,da,b,c,da,b,c,d ，则合并出的新树直径只有可能是这 4 个数中的 2...

二分图的结论和算法 防止忘记 匈牙利算法的过程是，枚举每一个左部点 uuu ，然后枚举该左部点连出的边，对于一个出点 vvv，如果它没有被先前的左部点匹配，那么直接将 uuu 匹配 vvv，否则尝试让 vvv 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 uuu 匹配 vvv，否则 uuu 失配。 二分图最大独立集等于总点数减去最大匹配

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∑R​f(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 的情况，代入式子即得...

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​...

防止过了几个月就忘了 单位复根 ω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}...

换根 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 的前缀和

区间 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)股票交易 巧妙的单调性优化 设 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)=max⁡1≤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′≤ASi​max​(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 单调队列优化区间 dp 设 f(i,j)f(i,j)f(i,j) 表示放到第 iii 个烟花，当前在 jjj 的位置，设可以在两次烟花之间的移动距离为 sss 可以发现 f(i,j)=min⁡j−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]区间 status 线段树维护单点最大值+队列 注意的一点：在下图时 12105 | while (res(1) == m && pos <= i) { | ...