EOJ3364 吉吉木坐地铁
图+bfs
每个车站作为一个节点，记录编号，以及与之直接相连的两个站点。
结果是几个独立的环。
将每个环染色，以便判断是否可达（属于不同环的站点必然不可达），同时记录每个环的长度。
若两站点可达，任选一个方向记录两点距离，与走另一方向距离比较（环长-已记录的距离），选小的。
代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include<iostream>#include<queue>#include<vector>#include<algorithm>#include<cstring>using namespace std;const int maxn = 1e5 + 5;int color[maxn];int len_col ...
EOJ3633 双人旋转赛车
贪心
每次将一局的分数存入优先队列中，作为xjd的胜场分数。
进行假设，若xjd的分数大于oxx，说明有减少的余地，尝试从xjd的胜场中找出分数最小的，并减去，将其变为oxx的胜场。直到无法再减少。
代码：
123456789101112131415161718192021222324252627282930313233343536373839404142#include<iostream>#include<queue>#include<algorithm>using namespace std;typedef long long ll;const int maxn = 1e6+5;ll arr[maxn];ll n,k;ll ans;priority_queue<ll,vector<ll>, greater<ll> >win;int main() { cin >> n >> k; for (ll i = 1; i <= n; i++) { cin >> ...
kd树
K-近邻法
距离度量标准：欧式距离或更一般的 LpL_pLp 距离。
k 值的选择：k 值小时，k 近邻模型更复杂；k 值大时，模型更简单（当 k=N 时，最简单）；用交叉验证法取得最合适的 k 值。
分类决策原则：多数表决。
构造kd树
kd树用于搜索与规定点空间距离最小的点。
kd树与线段树类似，线段树存某一区间，kd树存某一k维空间。
构造kd树的方法也是从一整个空间开始，递归往下分配空间。
每个节点存其所在维度，父子节点，以便之后搜索。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<iostream>#include<algorithm>#include<vector>using namespace std;const int k = 2; //k维度const int maxn = 100; //最大节点数int cmp_dim; //排序时的维度vector&l ...
validation
Cross Validation
什么是Cross Validation？
假设目前已有的数据集全集为D，从中选出一部分作为交叉验证集。
其余集作为训练集，将已有的模型A1A_1A1在训练集上训练，在验证集上得到Error1Error_1Error1，再轮换选出另一部分作为验证集，重复。得到E(A1)‾\overline{E(A_1)}E(A1)，对模型A2A_2A2同样操作，得到E(A2)‾\overline{E(A_2)}E(A2)，最终选出E‾\overline{E}E最小的模型A，在全集上训练，得到最终的矩 g 。
为什么需要Cross Validation？
我们已经有了很多的机器学习模型，linear regression，PLA，Pocket，Logistic，同时每种模型又有各种超参数，是否加regularization，learning-rate，Logistic的维数，从中如何选择合适的模型成了重点，因此需要一种评判优劣的标准，如果都在全集上训练，测试，可能无法做到泛化。而留出一部分未被污染的数据作为测试，更客观。
如何使用Cross Va ...
决策树
特征选择
信息增益
1.1 熵
随机变量 X ，其分布概率为 P(X=xi)=pi,i=1,2,⋯ ,nP(X=x_i)=p_i , i=1,2,\cdots,nP(X=xi)=pi,i=1,2,⋯,n
熵定义为 :
$$H(X)=-\sum_{i=1}^np_i\log {p_i}$$
若pi=0p_i=0pi=0 ，则定义 0log0=00\log 0=00log0=0
1.2 条件熵
随机变量 Y 在 X 条件下的熵。
定义为：X 给定的条件下，Y 的条件概率分布的熵对 X 的数学期望。
H(Y∣X)=∑i=1npiH(Y∣X=xi)H(Y|X)=\sum_{i=1}^n p_iH(Y|X=x_i)H(Y∣X)=∑i=1npiH(Y∣X=xi)
1.3 信息增益
已知特征 X 而使 Y 的不确定性减少的程度。
g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A)g(D,A)=H(D)−H(D∣A)
DDD 表示输入空间，AAA表示特征。
ID3算法
2.1 算法
(1) 若 D 中所有实例属于同 ...
空间中一点到超平面的距离推导
空间中一点x0x_0x0到超平面wx+b=0wx+b=0wx+b=0的距离推导。
www为超平面的法向量，b为截距。
作x0x1⃗\vec{x_0x_1}x0x1垂直于平面，则x0x1⃗\vec{x_0x_1}x0x1平行于w⃗\vec{w}w.
则有x1x_1x1在平面上，即 w⋅x1+b=0w\cdot x_1+b=0w⋅x1+b=0
则 ∣w⃗⋅x0x1⃗∣=∣∣w⃗∣∣⋅∣∣x0x1⃗∣∣=∣∣w⃗∣∣⋅h|\vec{w}\cdot \vec{x_0x_1}|=||\vec{w}||\cdot ||\vec{x_0x_1}||=||\vec{w}||\cdot h∣w⋅x0x1∣=∣∣w∣∣⋅∣∣x0x1∣∣=∣∣w∣∣⋅h
又 w⃗⋅x0x1⃗=w⋅(x1−x0)=w⋅x1−w⋅x0=−w⋅x0+(−b)=−w⋅x0−b\vec{w}\cdot \vec{x_0x_1}=w\cdot(x_1-x_0)=w\cdot x_1-w\cdot x_0=-w\cdot x_0+(-b)=-w\cdot x_0-bw⋅x0x1=w⋅(x1−x0) ...
贝叶斯估计
贝叶斯公式
P(Bi∣A)=P(Bi)P(A∣Bi)∑j=1nP(Bj)P(A∣Bj)P(B_i|A)=\frac{P(B_i)P(A|B_i)}{\sum_{j=1}^n P(B_j)P(A|B_j)}P(Bi∣A)=∑j=1nP(Bj)P(A∣Bj)P(Bi)P(A∣Bi)
或P(B∣A)=P(A∣B)P(B)P(A)P(B|A)=\frac{P(A|B)P(B)}{P(A)}P(B∣A)=P(A)P(A∣B)P(B)
P(B∣A)P(B|A)P(B∣A)：发生A的条件下发生B的概率。
先验概率越小，误判可能性越大。
似然性：由结果推出规律的可能性。
1）先验——根据若干年的统计（经验）或者气候（常识），某地方下雨的概率；
2）似然——下雨（果）的时候有乌云（因/证据/观察的数据）的概率，即已经有了果，对证据发生的可能性描述；
3）后验——根据天上有乌云（原因或者证据/观察数据），下雨（结果）的概率；
后验 ~ 先验*似然 ： 存在下雨的可能（先验），下雨之前会有乌云（似然）~ 通过现在有乌云推断下雨概率（后验）；
条件概率——在条件A的基础上，发生B的概率。
条件 ...
