Home

Keep It Simple

点分治 在开始树上点分治前,复习下树的直径,树的重点,以及深度,分治小知识。 树的直径 两遍$dfs()$,第一次求出直径的一个端点,第二次求出以该端点为根的最长路,即为直径。 #...

发布 0 条评论

#Description A knight jumps around an infinite chessboard. The chessboard is an unexplored territory. In the spirit of explorers, whoever stands on a square for the first time claims the ownership of this square. The ...

发布 0 条评论

尺取法顾名思义是用尺子一段一段测量。测量物件长度通常是一端对其,看另一端的刻度得出答案; 借挑战上的话 尺取法通常是数组保存一对下标,即所选取的区间的左右端点,然后根据实际问题不断推进区间,在这其中可以根据已有经验保持...

发布 0 条评论

Time limit : 2sec / Memory limit : 256MB You are given a string $S$ consisting of and 1. Find the maximum integer $K$ not greater than $|S|$ such that we can turn all the characters of $S$ into by repeat...

发布 0 条评论

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Alice is interesting in computation geometry problem recently. She found a interesting problem and solved it easily. Now she will g...

发布 0 条评论

这段时间做了区间DP在此总结下 1.POJ 1651 Multiplication Puzzle 题意描述: 给出序列$a$,求出最小得分—— 取出的数左边的数右边的数 (不能取两边),实质为矩阵链乘变形,设$dp[i][j]$为取光$(i,j)$之间的元素所得的最小值, $k$为区...

发布 0 条评论

题意:给出一棵有边权的树,两个人从st出发,需要经过树上所有的点,问最少代价。 数据范围:点数$n<=1e5$ trick: 思考这样的问题想要途径所有的点那么必然不可避免的需要走回头路,如何选一条路使得在这个路上我们只需要走一遍,...

发布 0 条评论

快速傅里叶变换模板题 题意:给出一副点数无穷大但只能是合数的扑克牌,四种花色$S,H,C,D$组合成一个数;给出区间$i∈[L,R]$问组成i的方案数有多少? 把每种花色看成多项式~$ inf$,幂次为合数的系数为$1$,否则为零,先$dft$四种花色编...

发布 0 条评论

题意:给出一棵树,$n≤5e4 $, $ \left(q≤5e4 \right)$次询问,每次询问三元组$ \left(u,v,k \right) $,返回从$ u $,到$v$ 上序号$ \left(from \ 0 \right)$为$ k$的倍数的点权连续异或。 ...

发布 0 条评论

全文为算法导论的笔记作为备忘 $Fast \ Fourier \ Transform$($ FFT$)解决的问题是 $\displaystyle A(x)=\sum_{j=0}^{n-1}a_jx^j ,\ B(x)=\sum_{j=0}^{n-1}b_jx^j$($ n$为多项式项数记$ degree(A)=k$) 任何一个大于一个多项式次数...

发布 0 条评论