题目 #10013. 「一本通 1.2 例 3」曲线 解析 首先这个题保证了所有的二次函数都是下凸的， \(F(x)=max\{s_i(x)\}i=1...n\)在每一个x上对应的最大的y，我们最后得到的还是一个凸函数  这个题比较特殊的一点是函数可能退化为一次，但退化为一次后的函数还是凸函数  代码 然后就可以愉快的三分了 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; const double EPS = 0.000000001; int t, n; double a[N], b[N],...

题目 bzoj2654: tree 解析 kruscal在做最小生成树时先按权值排序，权值小的先被选到，我们可以通过控制白色边的边权来控制白色边的数量。 我们可以通过二分答案来给白边加某一个值 同时注意两点  不要忘记减去给白边加的值 排序时白边优先  代码 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, num, need, ans, tot, sum, cnt; int fa[N], head[N], w[N]; struct node { int u, v, w, ...

题目 loj#10067 构造完全图 解析 和kruscal类似，我们要构造一个完全图，考虑往这颗最小生成树里加边 我们先把每一条边存下来， 把两个端点分别放在不同的集合内，记录每个集合的大小，然后做kruscal，集合之间两两构造完全图，即两两合并，直到合并成为一个集合。 因为本来就有一条边相连，又要满足这条边的边权是最小的，显然合并两个集合的代价是\((size[x]*size[y]-1)*(w[i]+1)\)，然后\(f[x]=y\)，最后再加上原来这棵树的总权值就好了 代码 #include <bits/stdc++.h> #define int long long usi...

友元 只有本类中的成员函数可以访问本类的私有成员，阻止其他访问，但在某些情况下。我们要访类的私有成员，如果把私有成员定义为共有的话，就破坏了类的隐藏性，这是我们就用到了友元。 友元(friend)机制可以允许类外的函数和其他类访问本类的私有成员。 友元在类中声明，以关键字firend开始，可以在类中任意位置声明。友元函数虽然定义在类内，但其并不是类成员，所以其不受public，protected，private的影响. 友元函数 将非成员函数声明为友元函数 友元函数是不在类中的函数，但是可以访问类内的所有成员的函数。 #include using namespace std; class A ...

继承定义 继承是使代码可以复用的重要手段，也是面向对象程序设计的核心思想之一。 继承就是不修改原有的类，直接利用原来的类的属性和方法并进行扩展。原来的类称为基类，继承的类称为派生类，他们的关系就像父子一样，所以又叫父类和子类。 一般格式如下： class 派生类名 : 继承类型 基类名 派生类成员可以访问基类的public成员和protected成员。 三种继承方式 继承类型有三种，共有继承(public)，私有继承(private)和保护继承(protected)。 共有继承： 共有继承的特点是基类成员在派生类中都保持原来的状态  基类中的public仍为public， 基类中的protec...

什么是this this是一个const指针，存的是当前对象的地址，指向当前对象，通过this指针可以访问类中的所有成员。 当前对象是指正在使用的对象，比如a.print()，a就是当前对象。 关于this1. 每个对象都有this指针，通过this来访问自己的地址。2. 每个成员函数都有一个指针形参（构造函数没有这个形参），名字固定，称为this指针，this是隐式的。3. 编译器在编译时会自动对成员函数进行处理，将对象地址作实参传递给成员函数的第一个形参this指针。4. this指针是编译器自己处理的形参，不能在成员函数的形参中添加this指针的参数定义。5. this只能在成员函数中使...

静态成员变量 不同的对象占用不同的内存，这就使不同对象的成员变量相互独立，互不影响。给定两个对象a和b，假设我们修改了a.a，b.a并不会受到影响。 如果我们想要在多个对象之间共享一个数据，这就用到了静态成员变量。  静态成员变量是一种特殊的成员变量，被static修饰。 只能被定义一次，储在全局常量区，不占用对象的储存空间这就意味静态成员不随对象的创建而分配内存，也不随对象的销毁而释放内存。 被同类的全体成员共享，单静态成员变量只有一个实例存在，与类定义了多少对象无关，  也就是说静态成员是与该类相关的，而不是与类的实例对象相关 静态成员变量不能在类中初始化，因为静态成员变量是被所有的对象所...

什么是拷贝构造函数 拷贝听起来真高级拷贝构造函数形如 class_name(const class_name &object_name) 拷贝构造函数是一种特殊的构造函数，只有一个参数，这个参数是本类中的一个对象，以引用的形式传参，一般用const修饰，使参数值不变。 如果没有定义拷贝构造函数，编译器会自动隐式生成一个拷贝构造函数，用来简单的复制类中每个成员变量。 一个简单的类对象拷贝 #include using namespace std; class A { private : int a, b; public : A(int x, int y) : a(x), b(y) {} ...

什么是析构函数 创建对对象时，系统会自动调用构造函数为我们进行初始化，同样，在销毁对象时也会自动调用一个函数为我们收尾，如释放内存等，这个函数是析构函数。 析构函数也是一种特殊的成员函数。 特点  析构函数的名称和类的名称相同，在前面加~ 析构函数没有返回值，无参数 析构函数只能在类中使用，且只有一个参数 不能继承和重载析构函数 析构函数不能显性调用  什么时候调用析构函数 1. 对象生命周期结束被销毁时 #include using namespace std; class A { public : A(){ printf("A()\n"); } ~A() { print...

初始化列表 为了给类成员变量赋值，可以再构造函数的函数体内对成员变量赋值，也可以采用初始化列表。如： #include <bits/stdc++.h> using namespace std; class A { private : int a, b; public : A(int x, int y) : a(x), b(y) {} /* 相当于 A(int x, int y) { a = x, b = y; } */ void print() { printf("%d %d\n", a, b); } }; int main() { A tmp(10, 20);...

什么是构造函数 构造函数是初始化类对象的类成员函数。在c++中，当对象被创建时，自动调用构造函数，构造函数是该类的一个特殊成员的函数 构造函数和一般的成员函数有什么不同  构造函数的名称和类的名称完全相同 构造函数没有返回类型(包括void) 创建对象的时候自动调用构造函数 如果我们不写构造函数，编译器会自动创建一个没有参数的构造函数，函数主体内什么也没有（默认构造函数） 函数体中不能有return语句  构造函数 默认构造函数 A类中编译器自动生成的构造函数如下 A(){} 没有参数的构造函数，不论是编译器自动生成的还是自己写的，都称为默认构造函数。 如果写了构造函数，编译器就不会自动生成默...

## 思路： 非常套路性的一个东西，记录一下，防止遗忘 设$f[i]$表示以$i$为根，到其子树的叶节点的最大距离。  考虑如何用子节点更新父节点， 当前点到叶节点的最大距离=max{子节点到叶节点的距离+当前点到子节点的距离}。  设$u$为当前节点，$v$为$u$的子节点，$dis(u,v)$是从$u->v$这条路径上的距离 得到转移方程： $$f[u]=max\{f[v]+dis(u,v)\}$$  如何维护以$u$为根的子树中的直径呢 以$u$为根子树的直径=max{u到叶节点的最大距离+子节点到叶节点的最大距离+$u$到叶节点的距离} 然后我们钦定一个节点为根，比如1 得到转移...

预备知识：线段树，DFS序   DFS序       DFS序，字面意思，就是DFS到的顺序   我们只需要在搜到节点的时候记录一下就可以了   比如这样可能是一个树的DFS序      那知道了DFS序又有什么用呢   我们可以发现一颗子树在DFS序上是连续的一段      那么它就有了一个区间的性质，每个节点对应一段区间，那么我们在进行一些操作像什么：将以某节点为根的子树节点都加上x时，就可以转化为在线段树内的区间加了       树链剖分       首先我们要清楚一些概念：   重儿子（节点）：子树结点数目最多的结点   轻儿子（节点）：除了重儿子以外的结点   重边：父亲结点和重儿子...

题目 String painter给出两个字符串s1,s2。对于每次操作可以将 s1 串中的任意一个子段变成另一个字符。问最少需要多少步操作能将s1串变为s2串。 解析 太妙了这个题，mark一下。 这个题先考虑怎么由空串转化s2， 表示从空串到s2最少的次数，则有，若存在一个，使，则， 为断点，和同时刷。 然后再考虑把s1刷成s2的代价设表示把刷成的次数当时，可以不刷，显然否则，在区间内找最小次数 代码 #include using namespace std; const int N = 1e3 + 10; int n, m; int f[N][N], sum[N]; char s[N],...