专题杂选

线段树专题

参考ACM大牛总结的线段树专辑

匈牙利算法+km算法

二分图最大匹配
二分图最大权完美匹配

简单数论

UVA 12716

题目要求

输入整数n（1≤n≤30000000）有多少对整数（a，b）满足：1≤b≤a≤n 且gcd(a，b)=a XOR b
例如n=7时 有4对：（3，2）（5，4）（6，4）（7，6）

容斥原理

HDU 4135

Problem Description

Input

DP专题八–石子合并

任取石子

有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费
最小（或最大）。

分析

当然这种情况是最简单的情况，合并的是任意两堆，直接贪心即可，每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。

DAG上的DP问题

嵌套矩形问题–NYOJ16

Problem Description
有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）
可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

Input

DP专题七–有关复杂集合

最优配对问题

题目要求

空间里有n个点P0P1···Pn，你的任务是把他们配成n/2对（n是偶数）使得每个点恰好在一个点对中
所有点对中两点的距离之和应尽量小

dp专题六–树形dp

HDU 1502–树的最大独立集

Problem Description

Input

dp专题五

最优矩阵链乘问题

题目要求

一个n×m阶矩阵和一个m×p阶矩阵连乘 运算量是nmp
有n个矩阵链乘 可以给矩阵加括号改变运算顺序 求最小的运算次数

贪心杂选

HDU 4296

Problem Description

Input

Machine Learning-2

第三周

分类问题

我们通常不用线性回归来解决分类问题
这是因为极端点往往对线性回归的拟合产生较大偏差
通常使用逻辑回归才解决分类问题
在分类问题中y通常取0/1代表两种不用的状态