Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共85篇）

构造函数(二) 初始化列表

初始化列表为了给类成员变量赋值，可以再构造函数的函数体内对成员变量赋值，也可以采用初始化列表。如： #include <bits/stdc++.h> using namespace std; class A { private : int a, b; p...

c++

2019-07-19

0 568

构造函数(一) 构造函数及重载

什么是构造函数构造函数是初始化类对象的类成员函数。在c++中，当对象被创建时，自动调用构造函数，构造函数是该类的一个特殊成员的函数构造函数和一般的成员函数有什么不同构造函数的名称和类的名称完全相同构造函数没有返回类型(包括void) 创建对象的时候自动调用构造函数如果我们不写构造函数，编...

2019-07-19

0 580

树形DP求树的直径

## 思路：非常套路性的一个东西，记录一下，防止遗忘设$f[i]$表示以$i$为根，到其子树的叶节点的最大距离。考虑如何用子节点更新父节点，当前点到叶节点的最大距离=max{子节点到叶节点的距离+当前点到子节点的距离}。设$u$为当前节点，$v$为$u$的子节点，$dis(u,v)$是...

2019-07-19

0 941

树链剖分详解

预备知识：线段树，DFS序 DFS序 DFS序，字面意思，就是DFS到的顺序我们只需要在搜到节点的时候记录一下就可以了比如这样可能是一个树的DFS序那知道了DFS序又有什么用呢我们可以发现一颗子树在DFS序上是连续的一段 ...

2019-07-19

2 4384

HDU2476 String painter

题目 String painter给出两个字符串s1,s2。对于每次操作可以将 s1 串中的任意一个子段变成另一个字符。问最少需要多少步操作能将s1串变为s2串。解析太妙了这个题，mark一下。这个题先考虑怎么由空串转化s2，表示从空串到s2最少的次数，则有，若存在一个，使，则，为断点，和...

2019-07-19

1 633

树形DP求树的直径

思路：非常套路性的一个东西，记录一下，防止遗忘设\(f[i]\)表示以\(i\)为根，到其子树的叶节点的最大距离。考虑如何用子节点更新父节点，当前点到叶节点的最大距离=max{子节点到叶节点的距离+当前点到子节点的距离}。设\(u\)为当前节点，\(v\)为\(u\)的子节点，\(d...

DP 套路

2019-07-17

0 646

HDU2476 String painter(DP)

题目 String painter 给出两个字符串s1,s2。对于每次操作可以将 s1 串中的任意一个子段变成另一个字符。问最少需要多少步操作能将s1串变为s2串。解析太妙了这个题，mark一下。这个题先考虑怎么由空串转化s2， \(f[i][j]\)表示从空串到s2最少的次数，则有...

DP

2019-07-15

0 697

P1018 乘积最大(DP)

题目 P1018 乘积最大解析区间DP 设\(f[i][j]\)表示选\(i\)个数，插入\(j\)个乘号时的最大值设\(num[i][j]\)是\(s[i,j]\)里的数字转移方程就是\(f[i][k] = max(f[i][k], f[j][k - 1] * num[j + 1][...

DP

2019-07-13

0 435

感动

被自己感动了，md，努力学了一个月的文化课，无数次的打击，从头开始的语文、英语。终于，英语考了107.5，语文考了100。哭了。我登上attack大佬的blog发现复制我的评论一直持续到20页，果然人类的本质是复读机。被迫报了一个省选班，md，又得拾起省选了。还有14天，我还有好多东西没学...

2019-07-13

0 982

P1349 广义斐波那契数列(矩阵乘法)

题目 P1349 广义斐波那契数列解析把普通的矩阵乘法求斐波那契数列改一改，随便一推就出来了 \[\begin{bmatrix}f_2\\f_1 \end{bmatrix}\begin{bmatrix} p&q\\ 1&0\\ \end{bmatrix}^{n-2}=\be...

矩阵快速幂矩阵数学

2019-07-12

0 599