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的概率。
条件 ...