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

这是博主自用的自定义css，改变了字体大小，代码高亮等方面，让文章有更好的阅读效果。 CSS代码 #home{ width: 85%; } pre { /*控制代码不换行*/ white-space: pre; word-wrap: normal; } .cnblogs-markdown .hljs { display: block; overflow-x: auto; padding: 0.5em; background: #23241f !important; color: #FFF; white-space: pre; word-break: normal; } .hljs, .hljs...

题目 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？ 思路 各种课程之间的关系显然是树形结构，显然可以用背包求解。 我们用\(dp[x][j]\)表示在当前子树中选择了j门课所能获得的最大学分，之后每个点就都可以由它的子节点转移了。 #include<bits/stdc++.h> #defin...

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

题目 考虑递推关系式\(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).....f(d)。这些数字均不超过2^31-1。输入结束的标志是d=n=m=0. 【输出格式】 对于每组数据，输出f(n)%m 思路 前置知识是矩阵乘法和矩阵快速幂。 矩阵相乘最重要的方法是一般矩阵乘积。它只...

目录   Cmd Markdown 公式指导手册 一、公式使用参考  1．如何插入公式 2．如何输入上下标 3．如何输入括号和分隔符 4．如何输入分数 5．如何输入开方 6．如何输入省略号 7．如何输入矢量 8．如何输入积分 9．如何输入极限运算 10．如何输入累加、累乘运算 11．如何输入希腊字母 12．如何输入其它特殊字符  (1)．关系运算符 (2)．集合运算符 (3)．对数运算符 (4)．三角运算符 (5)．微积分运算符 (6)．逻辑运算符 (7)．戴帽符号 (8)．连线符号 (9)．箭头符号  13．如何进行字体转换 14．大括号和行标的使用 15．其它命令  (1)．定义新的符号 ...

题目 题面 大意是给你一个图，要你构建出一棵最短路树，再询问经过k个点的最长路径长度以及最长路径条数。 思路 点分治。 点分治的思路是这样的： 对于一个点\(x\)而言，对答案有影响的路径要么经过点\(x\)要么不经过，利用这点进行分治。 点分治首先要找出一个重心。重心是指以该点为根所有的子树中sz最大的最小。 然后，对于每一棵子树进行处理，统计答案（点分治题目不同的地方就在这，其它都是板子） 之后再递归进重心的子树中处理。 对于一个根来说，如果统计答案的复杂度是\(O(n)\)，那么总的复杂度就是\(O(nlogn)\). 代码 #include<bits/stdc++.h> #...

题目 在森林中见过会动的树，在沙漠中见过会动的仙人掌过后，魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了 LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味；小猴在枝头悠来荡去,好不自在；各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果；鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境” SHY觉得LJJ还是太naive，一天，SHY带着自己心爱的图找到LJJ，对LJJ说：“既然你已经见识过动态树，动态仙人掌了，那么今天就来见识一下动态图吧” LJJ“要支持什么操作？” SHY：“ 1.新建一个节点，权值为x。 2.连接两个节点。 3.一个节点...

题目 给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节点的颜色为c[i]。 如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。 定义depth[i]为i节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。 思路 本质与HDU3333Turing Tree是一样的，方法是可持久化线段树合并。 每个点开一个线段树，...