POJ1741 Tree(点分治)

题目给一棵边带权树,问两点之间<=K的点对有多少个。思路题目很简单,但是思路很经典。首先确定点分治的基本框架,假设一定要经过一个根。下面还要用到容斥的思维。对于一个根,我们没法直接统计路径长度不超过k的路径条数,那需要一点技巧。处理出子树中所有的dis值放入B数组中,再对于当前A子树,加上其对于B所做的贡献,减去其对自身所做的贡献,就是它对其他子树所做的贡献。看似简单,其实在点分治问题中这是

- 阅读全文 -

洛谷P2014 选课(先序遍历优化树形背包)

题目在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少?思路各种课程之间的关系显然是树形结构,显然可以用背包求解

- 阅读全文 -

高斯消元初步

概述高斯消元是线性代数中的一个算法,可以用来为线性方程组求解。基本步骤构造原矩阵为三角形格式 $$ a[1][1] * x[1] + a[1][2] * x[2] + ... + a[1][n] * x[n] = y'[1]\\ 0 * x[1] + a[2][2] * x[2] + ... + a[2][n] * x[n] = y'[2]\\ 0 *

- 阅读全文 -

KMP的初步理解

概述KMP算法能够解决字符串匹配问题。即S串在P串中出现了多少次的问题,时间复杂度为$O(n+m)$设S处的指针为j,P处的指针为i,我们的目的是让P[i-j+1..i]与S[1..j]完全相等。那么如果使用传统的方法,一旦匹配失败,就需要把i往后移一位,再重新匹配,时间复杂度是$O(n*m)$的很不划算。尝试优化很显然,每一次匹配失败获得的信息在上面的朴素算法中没有得到很好的应用。举个例子:S=

- 阅读全文 -

Uva10870 Recurrences(矩阵快速幂)

题目考虑递推关系式$f(n)=a1*f(n-1)+a2*f(n-2)+....+ad*f(n-d)$,计算f(n)%m 【输入格式】 输入包含多组测试数据。每组数据第一行为三个整数d,n,m(1<=d<=15,1<=n<=2^31-1,1<=m<=46340)。第二行包含d个非负整数a1,a2.....ad。第三行为d个非负整数f(1),f(2).....

- 阅读全文 -