关于 强连通分量 缩点 tarjan是什么 自行搜索，这里只是封了一个板子

Codeforces Round #490 (Div. 3) E题

题目一眼可得tarjan 也不是一次两次了 封了板子，最开始还想做个模板类，但仔细一想，时间复杂度导致点个数不会超int，所以如果点序号大于int先离散化再做

E题 AC CODE

板子如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/* construct: vertexsize
 *    auto tarjan = new Tarjan(vertex_size)
 *
 * addpath // 1<=from_vertex,to_vertex<= vertex_size
 *    tarjan.addpath(from_vertex,to_vertex)
 *
 * prepare an result array,and work
 *    int res[vertex_size+1];
 *    tarjan.work(res);
 *
 * return:
 *    res[vertex_id]  ===== after_tarjan_vertex_group_id
 */
class Tarjan{
  int *low;// lowest node
  int *dfn;// deep first node
  int *stk;// stack
  bool *instk;
  bool *visited;

  vector<int> * p; // one-way road
  int stki;
  int id;
  int n;
  // strongly connected components强联通分量
  void scc(int v) {
    low[v] = dfn[v] = ++id;
    stk[stki++] = v;
    instk[v] = true;
    visited[v] = true;
    for(auto w:p[v]){
      if(!visited[w]){
        scc(w);
        low[v] = min(low[v],low[w]);  //v或v的子树能够追溯到的最早的栈中节点的次序编号
      } else if(instk[w]){ //v->w后向边
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        u = stk[--stki];
        dfn[u] = v;  //缩点
        instk[u] = false;    //出栈解除标记
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ){
    n = SZ;
    low =  new int[n+1];
    stk =  new int[n+1];
    dfn =  new int[n+1];
    instk = new bool[n+1];
    visited = new bool[n+1];
    p = new vector<int>[n+1];
    rep(i,0,n+1){
        visited[i] = false;
    }
    id = 0;
    stki = 0;
  }
  ~Tarjan(){
    delete [] low;
    delete [] stk;
    delete [] dfn;
    delete [] instk;
    delete [] visited;
    delete [] p;
  }
  void work(int *ret){
    rep(i,1,n+1){
      if(!visited[i]){
        scc(i);
      }
    }
    rep(i,1,n+1)
      ret[i]=dfn[i];
  }
  void addpath(int i,int j){
    p[i].pb(j);
  }
};

基本上 使用分3个步骤就好

1. 根据size初始化

2. 给它加单向边.addpath(from,to)

3. 准备一个结果数组a，调用.work(a)

4. 得到的结果数组a[原来的点序号]=缩点后的点序号

5. emmm 需要加两个宏使用 #define rep(i,a,n) for (int i=a;i<n;i++) 和 #define pb push_back

增强复用+简化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define pb push_back

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  vector<vector<int> > p;
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1);
    stk = {};
    vector<int>(n+1);
    dfn = vector<int>(n+1);
    res = vector<int> (n+1);
    p = vector<vector<int> >(n+1);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
  void p2(int i,int j){
    p[i].pb(j);
  }
};

int main(){
  int n,m;
  // 点,有向边,
  cin>>n>>m;
  Tarjan tarjan(n);
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    tarjan.p2(u,v);
  }
  vector<int> num = tarjan.calc(); // scc 联通分量 标识
  rep(i,1,n+1){
    printf("%lld: %d\n",i,num[i]);
  }
  return 0;
}

/**
1->2->3->1
3->4->5

5 5
1 2
2 3
3 1
3 4
4 5
 */

简述操作

tarjan(u)

0. 深搜: 标记序号, 到达最小, u进栈
1. 子点v未访问(dfn[v] == 0), 递归tarjan(v), low[u] = min(low[u],low[v])
2. 子点v在栈中(result[v] == 0), low[u] = min(low[u],深搜序号[v])
3. 当low[u] == dfn[u]时, 逐个出栈直到遇到u, 这些出栈的都是属于u这个联通分量 result[i] = u

D

难过的是 D 题的 算法细节已经对了，然而还是超时

通过 学习红名大佬的代码，发现是我们共同的n平方的算法的常数不同，我的常数是map查找 hash的速度+stl的效率，而它通过离散化，真的就只有个位数常数，，，，然而仔细想想，离散化的化我也不是遇到一次两次了，感觉不该再栽倒在同一个地方。

拷贝 提取 并修改了 红名大佬代码中做离散化的部分。

1
2
3
4

sort(li.begin(), li.end());
li.resize(unique(li.begin(), li.end())-li.begin());
for(int i=0; i<n; i++)
  newv[i]=lower_bound(li.begin(), li.end(), sourcev[i])-li.begin();

解释一下内容，sourcev中存的原始数据

li是 vector，把原始数据放进去

然后 通过排序 和 去重

再对每一个 原始数据找到所离散化出的新结果

参考

大佬的代码

表格整理

图片主要来源于官方的讲义PDF以及Wikipedia

监督学习

线性回归

将输入数据，如图中的红点，求得一条直线表示数据中的线性关系，并且这条直线在概率期望上达到最佳(后面算法省略这句)。

梯度下降

找函数极值小值点，图中相同颜色线为等高线，越靠近中心高度越低，运用高数的梯度运算和梯度下降能够得到如图中蓝色x标记的逐步逼近的极值点。

Normal Equation

同样是解决线性回归问题，和梯度下降不同的是，运用矩阵运算，直接得到参数的表达式

Logistics 回归

分类算法，对一侧数据0，另一侧数据1的训练数据建立分类器，图中的点是 训练输入，线是得到的logistics函数

高斯切线法

高数知识，二次收敛，加速点的收敛，如图 通过计算切线与坐标轴的交点作为下一次的迭代起始值。

广义线性模型GLM

按照所提出的假设模型，能够直接得到所需要的 拟合函数，可以用来证明上面 的线性回归中最小二乘法是最优，以及Logistics 回归中的函数选取。

softmax 回归

分类到对互斥的k个类别,公式推导采用带入GLM

高斯判别分析GDA

对0分布满足高斯分布，1分布也满足高斯分布的分布进行线性分类。

朴素贝叶斯

整体与特征来判断整体的分类，如垃圾邮件根据出现的词汇进行分类，很暴力直接计算概率

拉普拉斯平滑

解决朴素贝叶斯中可能出现的0除以0的情况，分子+1，分母+可分的种类数k

最优线性分类器

如图能够找到将 数据分开，并且离分割线最近的点的距离值最大的分类器。

拉格朗日对偶、KKT

用于具体解决 最优线性分类器的支撑方法

核函数

将变量非线性变化映射到高维空间，减小计算量，表示量，配合其它算法使用能获得高维空间性质。

支持向量机SVM

将低维不可线性分割的 通过核函数映射到高维度，再在高维中进行最优线性分割

L1 Regularization

在有部分异常点时的分割,通过添加惩罚项解决如下图异常点导致变化过大的问题。

SMO

对于多个参数 每次选一个参数进行取极值点，SMO能在带等式与不等式的约束限定情况下，每次两个参数逐步逼近。

均方误差MSE

能够用于分析 过拟合 还是 欠拟合

错误分析

按步骤替代/隔离分析，逐个增加或逐个减少。按训练误差 方差，实验 误差方差分析。

VC维、hoeffding不定式

用于证明概率下训练集和误差的上下界存在性。

验证方式、模型选择

将部分的训练数据不用于训练而用于检验模型

感知器

感知器：转换后的值小于0输出-1，大于等于0输出

无监督学习

k-means

对无标记的点进行分类(寻找分类的中心)

高斯混合模型GMM

可以看作类似前面的高斯判别模型GDA，但是现在的输入数据是无标记的

EM算法

用于GMM等无标记的混合模型的分离，先假设隐含变量Z以及它的分布Q，和k-means的思想类似，E-step优化Q，M-step优化参数，重复直到收敛 [使用Jensen不等式],分离效果见上图

因子分析

对训练集量少，维数大，分类的类别少的分布进行分类，思想是建立隐含低维度变量z，通过矩阵转化投影到高维，再加上高斯扰动误差

主成分分析PCA

对于高维空间的数据，找到其前k个相互正交的关键维度的向量，可用线性代数奇异值分解SVD进行快速计算。可以用于降维度，作为其它算法的预处理步骤，或找到关系的主要方面。

独立成分分析ICA

对于多维度，相互独立的非高斯分布成分，找到每个成分的轴，并将所有轴转换为正交轴。可用于特征提取，特征分离，如音频分离，计算人脸识别面部特征向量，对脑电波数据分离预处理去除眨眼和心跳信号。

马尔科夫模型

马尔科夫决策过程 MDP

能够学习带有状态，和基于状态动作的一类事情，学出一个策略集，如自动驾驶，需要设置奖励函数，概率函数等参数函数。策略迭代和值迭代

离散化连续状态的MDP

也就是字面意思离散化，在2维下工作一般不错，高维度后无论是维数灾难还是离散化难度，以及模型最终产物都难以普遍满意

MDP中的模型模拟器

用于概率状态未知时，用实验+拟合得到模型，从而代替概率函数的位置

线性二次型调节控制LQR

解决状态依赖于前一个状态前一个动作以及时间的策略选择，在有限时间内用动规(倒着递推)，多次实验线性拟合基于时间的。对于非线性函数仅能取较近的输入值，用近似的切线做近似的线性处理。通过加强奖励函数，初始值(时间T)矩阵，等限定。得出结论，动作与状态的线性相关，且计算过程中可以省去无关迭代

kalman滤波

将观测值转化为概率上的真实值

LQG

LQG=LQR+kalman滤波

微分动规DDP

根据当前决策选定轨迹，做LQR，更新决策，重复。从函数上理解是函数逐步靠近，即使是一个不那么好的模拟器

pegasus策略搜索

处理非线性模型函数的情况。选取随机序列并重复使用于模型训练，在模型选择时选取非线性的模型(如logistics 函数)，用极大似然去找该模型下的最优策略。

课程相关链接

网易Stanford机器学习

官方网站

Github整理

部分课件

练习

笔记和练习

说明

该课程能学到什么？

基于统计模型，概率公式的不同学习方法，不涉及神经网络。

本文档不按照课的分化记录，而按照内容的分化记录。

省去具体实现，毕竟已经有足够的他人整理的资料，以及我也在pad上手写过了，没有这个重复工作的必要了。不过我会尽量把知识点依赖写清，如果心情不错的话，再提供一个相关的优秀的讲解链接。这里还是以框架和思想为主。其中部分公式省略了取值限制，具体原公式请参照讲义

依赖知识

• 高等数学

  • 积分
  • 微分
  • 偏导数，梯度
  • 拉格朗日乘子法、KKT条件(拉格朗日对偶)
  • 牛顿切线

• 线性代数

  • 矩阵 乘法 转置 逆 秩 迹
  • SVD

• 概率统计

  • 贝叶斯
  • 高斯分布 多纬高斯分布
  • 0-1分布 泊松分布 等等常见分布
  • 极大似然估计

• 算法

  • 动态规划

内容

监督学习

• 提供样例(输入，输出(类别))数据进行训练，从而学习出一个分类器/学成一个带有功能的程序。

方法

辅助方法/定义

证明

无监督学习

• 无样例(输入，输出)样本进行学习，直接根据未分类数据的分布特征，对数据进行分类/建立带有功能的程序。

方法

辅助方法/定义

强化学习RL/马尔科夫模型MDP

上面的都是分类模型，强化学习要强行分类也可以说是无监督分类，或者半监督分类。

解释

马尔科夫决策过程 变形/问题

Debug 19

一句话能回答的知识点 TODO

梯度下降和梯度上升有什么区别？3

画三维图形，求它的梯度，从图像上看，梯度是指向上方的。所以梯度下降用减法，实际是逼近极小值，而梯度上升用加法，逼近极大值。

欠拟合与过拟合分别是什么？4

欠拟合：模型复杂度不够 训练数据少，未能真正获取主要内在关系，训练数据和测试数据得分都低。过拟合，模型过于复杂，训练数据方差小得分高，但是测试数据偏差大 方差大

判别学习法 和 生成学习方法 的区别？5

判别学习法直接对P(y|x)进行建模；生成学习方法对P(x|y) 和 p(y)进行建模 然后，y = 贝叶斯公式转换后最大的y 例如 隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA。

GDA与Logistics模型比较？5

GDA按照概率转化的曲线和sigmoid,很相似。GDA更强的假设，对于正确的训练集，GDA效率更高 更好，但对于不正确的模型，logistic的健壮性robust更好

其它知识点 细节 TODO

LGM

对偶问题

KKT条件

核函数定义 证明 应用 具体核(高斯核)

SVM

EM

EM:Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897.

其它TODO

添加配图

李航的《统计学习方法》刚翻了个开头，这本书先讲的泛的再具体的顺序不同，不过瞄了目录，似乎有新内容还是换了个名字？不懂2333，目前计划是先不看它，去看CSP，之后再看_(:з」∠)_。

老师建议把 证明过程盖住 自己再证明

2讲矩阵梯度公式

题目

题目大意

输入 k pa pb

最初空字符串，每次增加一个字符 a 或者 b, 当子串ab的个数>=k就停止,求停止时 子串ab的个数的期望。

子串的不需要连续 比如aab 是有两个ab子串

产生a的概率为 pa/(pa+pb), 产生b的概率为 pb/(pa+pb)

期望 计算过程中 不使用小数，而是用 逆模

所有值模1000 000 007

数据范围

1<=pa pb<=1 000 000

1<=k<=1 000

解答

官方题解

意思是用dp[i][j] 表示前缀 中 有i个a ，j个ab子串的子串个数的期望值

用的是从长的推短的 反过来，首先如果 j>=k 那么 dp[i][j] = j

递推表达式 dp[i][j] = (pa * dp[i+1][j] + pb * dp[i][i+j])/(pa+pb)

也就是 根据最后一个字符来进行分化

所以最后的结果就是dp[0][0] = dp[1][0]

其中一些问题

虽然j>=k已经解决了 但是 i还是可以无限大，根据递推表达式 和 级数 的办法 可以求得dp[k][j] here

不用小数用逆模运算 wiki的最后一条

实现

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair

int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}
long long minn(long long v1,long long v2){return v1<v2?v1:v2;}
long long maxx(long long v1,long long v2){return v1>v2?v1:v2;}

//https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
//https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
// [a p]       1
// [1 0] --->  ret(x1)
// [0 1]       x2
ll mul_inv(ll a,ll b=MOD ){
  ll matrix[3][2]={{a,b},{1,0},{0,1}};
  int itr = 0;
  while(matrix[0][itr^1] != 1){
    ll t = matrix[0][itr]/matrix[0][1^itr] ;
    rep(i,0,3)
      matrix[i][itr] -= t * matrix[i][1^itr];
    itr^=1;
  }
  return (matrix[1][itr^1] % b + b )%b;
}
int k;
// http://codeforces.com/blog/entry/56713
ll dp[1010][1010] = {0};
ll getdp(int i,int j){
  return j >= k? j : dp[i][j];
}
int main(){
  ll a,b;
  cin>>k>>a>>b;
  //http://codeforces.com/blog/entry/56713?#comment-404349
  rep(i,0,k)
    dp[k][i] = (i + k + a * mul_inv(b)) % MOD;
  int i,j;
  for(i=k-1;i>=1;i--)
    for(j=k-1;j>=0;j--){
      dp[i][j] = (a*getdp(i+1,j) + b * getdp(i,i+j))%MOD;
      dp[i][j] = (dp[i][j] * mul_inv(a+b))%MOD;
    }
  cout<<getdp(1,0)<<endl;
  return 0;
}