detect

《深度强化学习》reading notes detect0530@gmail.com 价值学习 Optimal Bellman Equation On-Policy and Off-policy 按照交互中的策略与最终的策略是否一致，可以分为两类：On-Policy和Off-Policy。 SARSA Algorithm 可以说和Q学习基本类似，但是SARSA是On-Policy，而Q学习是Off-Policy。因为在每一次选择action时都是基于当前的策略函数π\piπ来选择的(而不是Q学习中ϵ−greedy\epsilon-greedyϵ−greedy抽样和最优action选择)。 同时引入多步TD的做法，指应用πnow\pi_{now}πnow​连续交互m次，然后再用梯度优化，因为真实数据由一步变成了多步，更稳定效果更好。 训练流程中走n步，对前n-m步都可以用来更新梯度，最后sigma求和梯度即可。 由此看来多步TD是比较抽象化的做法，当步数确定为极端情况时，实际上有之前讨论过的含义： 补充一点上图中提到的相关概念： 由此可见，多步TD算法如果步数 ...

浅析Alpha-Go detect0530@gmail.com 训练&执行步骤 先找很多对局素材，进行监督学习，然后分别训练policy和value network。 最后再依据policy和value函数进行蒙特卡洛树搜索。 Policy Network 通过191948的tensor表示状态，然后用convolutional layer提取特征，最后用softmax输出每个动作的概率。(361个动作) 一开始先用人的对局用来学习初步的策略网络。 用behavior cloning的方法（imitation learning 与reinforcement learning区别在于有无reword），让policy network去模仿人的对局。 其实就是一个交叉熵作为loss function的多分类问题。 Behavior cloning缺点是效果不好，没见过的话，不知道怎么走。 所以我们需要用reinforcement learning来改进behavior cloning训练出的policy network。 Train Policy network ...

DRL: Actor-Critic Method detect0530@gmail.com 基本概念 Discounted Return UtU_tUt​ 这个东西是一个随机变量，随机性由两部分构成，第一是Policy function给定状态s后选择的action。第二是State transition function给定状态s和action a后转移到下一个状态s’的概率。 Action-value Function Q(s,a) 给定状态s和action a，这个函数返回的是在这个状态下采取这个action的期望回报。注意这个回报和策略函数π\piπ有关，因为策略函数决定了在这个状态下采取哪个action。 Optimal Action-value Function Q∗(s,a)Q^*(s,a)Q∗(s,a) 选择一个在当前状态和动作下最优的策略函数π\piπ,让期望回报最大。 State-value Function Vπ(s)V_{\pi}(s)Vπ​(s) Vπ(st)V_{\pi}(s_t)Vπ​(st​)是对一个状态的评价，这个评价是基于决策函数π\ ...

网络流的基本概念 网络流问题都是建立在类似上图的有向图之上，有向图的边的权值代表容量。其中A代表源点，C代表汇点，一般考察的问题情景就是从A中流出流量，经过这些有向边，最终汇集到C中。像这样的具有源点和汇点，并且每条边的权值均为正数的有向图就被称作是容量网络，图中的这些边被称作是弧，弧的权值被称作弧的容量，它代表着能够通过这条弧的最大流量。而经过弧上的实际流量被称作弧的流量，所有这些弧的流量所组成的集合就是所谓的网络流。 直观上不难发现符合实际情况的网络流的特点，或者说是限制条件。首先每条弧上的流量不能超过其容量，还有对于除了源点和汇点以外的每个点来说，流入它的流量之和必须与从它流出的流量之和相等，即平衡条件。那么满足这两个条件的网络流就被称作是可行流，可行流的流量定义为从源点所流出的所有流量之和。在所有的可行流中，流量最大的那个被称作是最大流。 对于一串顶点序列(U,U1,U2,U3,…,V)(U,U1,U2,U3,…,V)(U,U1,U2,U3,…,V)，如果满足U是源点，V是汇点，并且序列中每相邻两个顶点之间均存在一条弧，那么就称这个顶点序列为一条链，注意这里并不要求这条弧的方 ...

其实打代码的感觉有点像网络流，重点是推导，剩下就是个板子。 知识点及推导 总结一下算法流程 先推出一般形式 dp[i]=dp[j]+xxxx 展开移项 定义只有i的为b（这样求出b就相当于求dp[i]） 定义只有j的为y（是定点） 对于有i,j的为j项为x，i项为a 现在（x,y）(i之前的)就定下来了 现在维护一个凸包 若q[h]和q[h+1]的斜率比当前a小了，那q[h]就没用了 还有对于队尾的判断，如果q[i]和q[tail]的斜率比q[tail]和q[tail-1]小，那么对于tail也没用武之地了 最后对于状态i的最优策略点j就是q[h]了，O1跟新即可 Updated 2020/09/13 感觉之前写的太片面和肤浅了，这里补一发关于依据单调性的不同做法。 - x,kx,kx,k都是单调的，那么可以方便的直接维护凸包，同时因为凸包斜率单#调，所以决策也有单调性。可以在总复杂度O(n)O(n)O(n)下解决问题 - 只有xxx单调，依然可以建出凸包，但是决策不满足单调性，可以在凸包上二分最佳位置。时间复杂度：O(nlogn)O(nlogn)O(nlogn) ...

FFT是一种可以在O(n∗logn)O(n*log_n)O(n∗logn​)的优秀时间复杂度里，求出两个多项式乘积的优秀算法。 首先，我们如何表示一个（n−1）（n-1）（n−1）次多项式？ 用每一项的系数来表示 用n个点的坐标来表示 所以算两个多项式乘积时，如果暴力计算系数，是O(n2)O(n^2)O(n2)的。 但是如果我们有这两个已知多项式的点的表达式，那么我们只需要O(n)O(n)O(n)的时间就可以得到带求多项式的点表达式。 不幸的是，为了得到两个多项式的n个点坐标，在横坐标随记下我们仍需要O(n2)O(n^2)O(n2)的时间来完成。 所以有没有什么办法可以优化找点的过程了。 以为名叫傅里叶的牛人发现了复数可以完美解决这个问题。 具体来说，我们再复数坐标戏中引入单位元（类比三角函数），因为复数有个性质，两复数乘积的几何意义是模长相乘，辐角相加。 因为我们取得点在单位圆上，于是同一个复数的nnn次乘积在几何意义上表现为辐角的成倍增长。 前方高能，我们开始搞事情了。 设带求多项式为F(x) 我们按照多项式次数的就分成两节。 即F(x)=FL(x2)+x∗FR(x2） ...

（p.s: code是真的短） 从头开始的详细版见WiKi 主要的难点都在后缀边和点的划分上。 重新声明一下定义: 我们按照这个字串在原串中每一个出现的最后一位的位置集合为一个点，即一个点里可以包含多个字串，我们钦定每个点中最长的字串长度为lenilen_ileni​。 后缀边 按照点的集合定义，后缀边其实是把这些点按照集合包含关系连了起来（只会连所有包含关系中len最小的那个点），即成一棵树。 然后就好办了啊 建立SAM算法流程简析 首先建立前缀的节点，集合只有前缀本身 从上一个前缀节点开始向上搜索看有没有点有新加入字符的正向连边。（注意正向连边图是一个DAG） 分三种情况： 若全没有，则该字符没出现过，fa->root即可 找到存在p，设q为p的该字符的对应点， 若 len[p]+1==len[q]len[p]+1==len[q]len[p]+1==len[q] ，因为p是原来串的最长可以跟字符s的点，原串与新串差1，如果len也差1，那么q必定是包含新串最长的点。 现在没发再特判了，需要新建立一个点来解决问题。 这个点继承q点后面 ...

之前写过一篇按权值的fhq，可以解决查询前驱后继，第k大等操作。 不过如果我们把fhq的特性转移到数列上，即类比线段树储存sum，标记之内，那么又是一个新毒瘤数据结构了。 补：（一些对FHQ的理解） 一共只有n个节点，不像线段树有2n个左右，因为fhq节点的左右儿子都是直接的节点（而线段树需要辅助节点），同时如果是对序数fhq，中序遍历就是当前数组，而对权值fhq，中序遍历是从小到大的顺序。 split的时候，两个取址的参数是分别两个分裂子树的root，注意，他们是完全分割的两个东西，并没有直接联系，第一层分裂完后，下一个该归到同一个分裂fhq的作为它的左右儿子。 一些注意事项： FHQ的正确性基于满足中序遍历和堆性质的树的形态是固定的。 pushdown操作如果要改变子树形态或者siz大小，需要小从把标记推完后，再进行操作。 毒瘤板题传送门 我们知道线段树可以实现区间和，区间更改，最大子段和等操作，但此题还要求加入一串数、删除一串数、翻转一串数的操作。 现在思考一下如何用fhq解决以上问题。 fhq本身由插入顺序决定相对位置(因为其本身是一棵二叉搜索树 ...

板题大赏。 板题1 凸包 我们先选最左下的一个点，它一定在凸包上。 于是将其他的点按照与左下点的极角排序，用单调队列维护外凸即可。（因为凸包的外边按照顺序一定是极角依次增大） （p.s 对于此题，在一条线上的点不会影响最后答案，可以不用在极角的基础上按照长度排序） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;int n,m;const int M=1e5+5;const double eps=1e-9;inline int sig(double x){ if(fabs(x)<eps) return 0; else return x>0?1:-1;}struct point{ double x,y; point(double _x=0.0,double _y=0.0){ x=_x,y=_y; & ...

莫比乌斯反演 形式 1 （卷积法证 如果有 F(x)=∑d∣xf(d)F(x)=\sum\limits_{d|x}f(d) F(x)=d∣x∑​f(d) 有如下反演： f(x)=∑d∣xμ(d)f(xd)f(x)=\sum\limits_{d|x}\mu(d)f(\frac{x}{d}) f(x)=d∣x∑​μ(d)f(dx​) 证明如下（用狄利克雷卷积易证）： F=f∗1F=f*1 F=f∗1 F∗μ=f∗1∗uF*\mu=f*{1*u} F∗μ=f∗1∗u F∗μ=f∗EF*\mu=f*E F∗μ=f∗E f=F∗μf=F*\mu f=F∗μ 证毕。 形式2 （带入法证 莫比乌斯反演第二种形式 F(n)=∑n∣df(d)−−>>f(n)=∑n∣dμ(dn)F(d)F(n)=\sum_{n|d}f(d)-->>f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d) F(n)=n∣d∑​f(d)−−>>f(n)=n∣d∑​μ(nd​)F(d) 证明如下： 将F(d)F(d)F(d)带入右边式子，并设k=dnk=\frac{d} ...