jijijix-CSDN博客

原创《统计学习方法》隐马尔可夫模型学习过程 Baum-Welch算法中几个公式的证明

证明P182页 3.（1）中公式证明：首先明确上述公式中表示的是在参数下，生成的输出序列为，隐状态序列的第1个位置为，隐状态序列的第2到n个位置随便是什么都行的概率。所以表示成更清晰直观。因此，有证明P182页 3. (2) 中公式同3. (1)中给出的说明，其实表达的含义应该是，代表的是除了位置和位置之外的隐状态序列中其他位置的取值。因此，有...

2019-11-27 21:41:40 341

原创 pytorch学习笔记3 求导

注：本文是笔者结合自己阅读和使用pytorch的经验，又系统学习了一遍https://github.com/chenyuntc/pytorch-book的过程中，将自己认为有必要掌握和记住的知识整理成的学习笔记，并非系统的教程，主要目的是为了方便自己梳理、记忆知识，以及方便有相同需求的读者查阅某些知识。计算图对于，其计算图表示如下关于计算图，有以下两点：(1)计算图中有两种节点...

2019-10-10 00:32:40 513 1

原创 pytorch学习笔记2

注：本文是笔者结合自己阅读和使用pytorch的经验，又系统学习了一遍https://github.com/chenyuntc/pytorch-book的过程中，将自己认为有必要掌握和记住的知识整理成的学习笔记，并非系统的教程，主要目的是为了方便自己梳理、记忆知识，以及方便有相同需求的读者查阅某些知识。逐元素操作1、在pytorch中，不仅仅针对逐元素的操作，tensor的计算往往具有两种...

2019-10-08 11:09:43 671

原创 pytorch学习笔记1 Tensor的创建、变型与变维、索引、类型

注：本文是笔者结合自己阅读和使用pytorch的经验，又系统学习了一遍https://github.com/chenyuntc/pytorch-book的过程中，将自己认为有必要掌握和记住的知识整理成的学习笔记，并非系统的教程，主要目的是为了方便自己梳理、记忆知识，以及方便有相同需求的读者查阅某些知识。tensor的创建1、使用torch.Tensor创建根据参数不同，具体分为两种...

2019-09-14 20:49:43 1758

原创 Low Power (optional) UCAS算法课题目二分

DescriptionYou are building advanced chips for machines. Making the chips is easy, but the power supply turns out to be an issue since the available batteries have varied power outputs.Consider th...

2019-09-10 22:36:08 318

原创 cs224n学习笔记 4

1 一般的分类问题1.1 softmax classifier训练集的形式是，其中是inputs，是labels；在这里，我们做出一些约定，方便后面进行说明：我们认为是一个d维的向量，表示C个类别中的一类当训练结束，进入预测阶段的时候，我们希望我们的模型能够预测"输入为x，类别为y”这件事的概率，我们可以借助训练得到的参数直接进行计算，计算的式子为，其中参数W是一个C*d的矩阵，该矩阵...

2019-01-01 21:00:18 1404

原创 cs224n学习笔记3

1 Word2Vec模型的负采样方法上一节讲的word2vec的模型，是一个基于naive softmax的word2vec的基础模型，因为复杂度高等原因，在实际的word2vec中会基于其他的一些方法来实现，负采样（negative sampling）就是其中的一个1.1 negative sampling的目的上一节的笔记最后提到，如果使用naive softmax的，且使用随机梯...

2018-11-19 14:41:50 502 4

原创 cs224n学习笔记 2

1 Word Meaning需要掌握的主要是词的表示方法，大体来说，词的表示主要有下面两种：1.1 discrete representation用一个one-hot向量来表示一个词，比如现在有三个词apple，banana，orange分别对应向量的每个位置，那么[0,1,0]表示banana。这种表示被称作是一种本地表示（localist representation）当全...

2018-11-11 17:50:55 2801

原创 win10下java-version和javac-version版本不一致的问题

当同一个系统里装了两个不同版本jdk的时候，如果想要切换当前使用的jdk版本，如果单纯更改环境变量里的值，在cmd中查看java -version和javac -version的时候，可能会发现二者的版本号不一致，这时编译等环节就无法正常进行。网上大部分解决的思路都和这篇博客（http://blog.csdn.net/u012061196/article/details/53241

2018-01-20 19:05:14 8479 5

原创 codeforces 825E Minimum Label 拓扑排序+逆向思维贪心

题目描述：给定n个点，m条边(2 （1）对1到n的编号是一个1到n的排列（2）如果存在一条边由点u指向点v，那么要求给u的编号小于给v的编号（3）将为1——n的编号写成一排，这个排列的字典序最小现在要求输出这个编号的排列思路：很容易产生一种想法，就是对这张图进行拓扑排序，拓扑排序的时候每次从入度为0的点当中选出一个编号最小的，然后为他赋当前的最小编号，然后继续进

2017-11-07 18:57:13 294

原创 Uvalive3353 Optimal Bus Route Design 带权二分图匹配

题目描述：给出一个有向带权图，现在要求在图中找出若干个环，使得每个点恰好在一个环里，且所有环的距离之和最小，如果不能使每个点恰好在一个环里，输出"N"。思路：将每个点u拆成u和u'两个点，如果从u到v有一条权值为dist的边，那么就从u向v'连一条权值为dist的边，明显可以看出，现在的这个图是一个二分图。下面就是这个问题的关键——在这个二分图中，每一个完美匹配对应了原图中的一

2017-07-24 11:34:17 403

原创 hdu5955Guessing the Dice Roll AC自动机+高斯消元

题目描述：有n个人，每个人有一个长为L的由1~6组成的数串，现在扔一个骰子，依次记录扔出的数字，如果当前扔出的最后L个数字与某个人的数串匹配，那么这个人就算获胜，现在问每个人获胜的概率是多少。思路：比较典型的AC自动机的应用，AC自动机处理后字典树中每个节点表示一个当前串的状态，这种应用的基础题如DNA Sequence一题：http://blog.csdn.net/jijijix

2017-07-18 15:07:17 981

原创 Uva10655 Contemplation! Algebra矩阵快速幂

题目描述：已知a + b = p , ab = q , 求a^n + b^n的值，a和b有可能是虚数；思路：设S(n) = a^n + b^n，则S(n) = a ^ n + b ^ n = (a + b)^(a^(n - 1) + b^(n - 1)) - a* b^(n - 1) - a ^(n - 1) * b = p * S(n - 1) - ab * (a^(n - 2) +

2017-07-14 19:46:51 315

原创 bzoj1070 修车最小费用流

1070: [SCOI2007]修车Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 5655 Solved: 2383[Submit][Status][Discuss]Description　　同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同

2017-05-22 17:40:40 282

原创 bzoj1022 小约翰的游戏 anti-SG游戏

1022: [SHOI2008]小约翰的游戏John Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2679 Solved: 1706[Submit][Status][Discuss]Description　　小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有n堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以

2017-05-21 17:07:42 346

原创 bzoj1053 反素数数论 + dp

1053: [HAOI2007]反素数antTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 3252 Solved: 1879[Submit][Status][Discuss]Description　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0

2017-05-20 17:34:24 356

原创 bzoj1021 循环的债务 dp + 暴力

1021: [SHOI2008]Debt 循环的债务Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 957 Solved: 503[Submit][Status][Discuss]Description　　Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过

2017-05-20 11:15:52 582

原创 bzoj1027 合金 Floyd求最小环 + 计算几何

1027: [JSOI2007]合金Time Limit: 4 Sec Memory Limit: 162 MBSubmit: 3891 Solved: 1143[Submit][Status][Discuss]Description　　某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后

2017-05-07 17:58:43 381

原创 bzoj1016 最小生成树计数

1016: [JSOI2008]最小生成树计数Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5739 Solved: 2335[Submit][Status][Discuss]Description　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两

2017-04-27 17:55:17 400

原创 bzoj 1005: [HNOI2008]明明的烦恼组合数学 + purfer序列

题目描述：给出n（0 推荐一篇写的特别清楚的purfer序列讲解的博客：http://www.cnblogs.com/zhj5chengfeng/p/3278557.html我再来概述一下这道题的思想，这道题其实主要利用了问题转化的思想，既然要求生成树，就是要求purfer序列的个数，而求purfer序列个数相对较为简单。通过这道题，要记住关于purfer序列的知识主

2017-04-24 16:37:31 479

原创 bzoj1014 火星人prefix 字符串hash + 区间splay树

1014: [JSOI2008]火星人prefixTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 7256 Solved: 2326[Submit][Status][Discuss]Description　　火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们

2017-04-23 17:03:08 492

原创 bzoj1500 修改数列区间splay树讲解

仅以此篇blog记录下区间splay树需要说明的几个方面，以供日后二次学习时使用1、splay树的旋转要知道普通splay树一字型和之字型旋转是怎么实现的2、区间splay树的含义：区间splay树，就是用splay树来维护一个数列及其相关信息。首先要搞清楚这棵树是怎么组织的：splay树作为平衡树的一种，满足左小右大的性质，那么这里的“

2017-04-23 16:52:29 472

原创 codeforces 771D Bear ans Company 动态规划

E. Bear and Companytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputBear Limak prepares problems for a programming com

2017-03-28 17:12:10 1194

原创 codeforces round 404 div2 D Anton and School - 2 组合数学

D. Anton and School - 2time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAs you probably know, Anton goes to school. O

2017-03-26 15:40:39 281

原创 codeforces 407C Curious Array 数学

题目描述：给出一个有n(0 ，输出经过m次修改操作之后的a数组。思路：首先从性质的角度观察这个问题，有两个可能有用的性质： ①k比较小，说不定可以从这里做文章②组合数具有常见的性质C(n , m) = C(n , m - 1) + C(n - 1 , m - 1) 这两个性质不足以启发思路，所以我们再从整体把握问题，如何才能不用每次都把区间内的

2017-03-20 19:03:50 568

原创 codeforces round 309 div1 Nudist Beach 二分+搜索

题目描述：给出一个有n(1 相邻的我方据点数 / 相邻的敌方据点最小的那个值最大，要求输出应该占领的据点编号思路：二分这个比值的最小值，关键在于怎么判断是否能通过一定的占领方式满足这个比值。枚举每个非堡垒点，如果这个点的当前比值小于二分出的值，就放弃这个据点，同时更新与这个点关联的其他

2017-03-18 11:26:55 457

原创 UVA11426 GCD - Extreme (II) 欧拉函数应用

题目描述：给定n(1 +gcd(2 , 3) + gcd(2 , 4) + ... + gcd(2 , n)

2017-03-16 21:14:21 329

原创 LA4287 Proving Equivalences 强连通分量

题目描述：给出n(1 思路：首先tarjan求强连通分量，将已经是同一个强连通分量的部分缩成一个点，图中剩余的部分构成了一个DAG图，为了使一张DAG图变成一个强联通分量，假设缩点后的图中入度为0的节点有a个，出度为0的节点有b个，那么max(a , b)就是答案，怎么证明？强连通分量当中一定不会出现入度为0或出度为0的点，同理，在没有重边和自环的情况下，如果通过加边消灭图中所有入

2017-03-16 20:38:03 310

原创 LA 3523 Knights of the Round Table 边双连通分量+二分图判定

收获：1、面对在图中分离出一个圈的问题时，要想到用无向图的边双连通分量2、当强调这个圈满足边数的奇偶条件时，要想到和二分图有关#pragma warning(disable:4786)#pragma comment(linker, "/stk:102400000,102400000")#include#include#include#include#include#inc

2017-03-14 17:10:42 312

原创 2017 CCPC Final B Wash

WashTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 64000/64000 K (Java/Others)Total Submission(s): 258 Accepted Submission(s): 61Problem DescriptionMr.Panda is about to engag

2017-03-04 17:46:59 1103

原创 codeforces round 396 div2 E Mahmoud and a xor trip 按位操作+dp子树内外

d every city with greater index as a finish. They want to know the total distance between all pairs of cities.InputThe first line contains integer n (1 ≤ n ≤ 105) — the number of cities in Mahmo

2017-03-02 20:12:59 367

原创 codeforces round 377 div2 F Tourist Reform tarjan求边双连通分量

F. Tourist Reformtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputBerland is a tourist country! At least, it can beco

2017-02-28 22:36:56 465

原创树链剖分模板 Query on a Tree

把kuangbin老师的树链剖分的模板细节改成了自己习惯的写法，mark一下供日后回顾 ①数组：tfdnpfs 变量：pos ②void init() ：pos son ③dfs1(int u , int pre , int d) 求出deep、fa、num、son ④getpos(int u , int sp) 求出top、

2017-02-27 20:39:18 270

原创 hdu5632 Rikka with Array 数位dp

Rikka with ArrayTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 301 Accepted Submission(s): 119Problem DescriptionAs we know, Rik

2017-02-27 19:26:49 330

原创 codeforces round 400 E The Holmes Children 数学欧拉函数

E. The Holmes Childrentime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe Holmes children are fighting over who amon

2017-02-25 16:00:09 420

原创 codeforces round 400 D The Door Problem 2-SAT

/* 题目描述：有n道门，m个开关，每道门由m个开关中的两个控制，若门的状态是0(关)，那么改变控制这道门的一个开关之后，门的状态就变为1(开)，若门的状态是1(开)，那么改变控制这道门的一个开关之后，门的状态就变为0(关)。现已知n道门的初始状态，以及m个开关分别控制哪些门，问能不能通过按下某些开关，使得全部门的状态都变为1。

2017-02-25 10:48:26 830 4

原创 codeforces 533B Work Group 树型DP

/* 题目描述：给出一棵树，树的每个节点代表一个人，每个人有一个工作的效率e[i]，现从树中选出一些人组成一个工作组，工作组的要求是工作组当中的每个人的下属的数量为偶数。现在问e[i]总和最大的工作组的工作效率总和是多少。思路：dp1[u][0]表示在u的直接或间接下属中找到偶数个工作组，然后由u来领导他们时，这个工作

2017-02-18 14:38:00 651

原创 POJ1625 Censored! AC自动机+dp+高精度

/* 题目描述：给出一个有n个字符的字符集，再给出p(0 <= p <= 10)个模式串，问长度为m的字符当中有多少个不含有任一模式串作为子串。思路：AC自动机的套路，字典树上的每一个节点表示一种状态，设dp[j][i]表示j节点状态，长度为i的串中满足条件的有多少个，则有dp[j][i] = Σdp[k][i

2017-02-17 20:06:12 389

原创 POJ2778 DNA Sequence AC自动机+矩阵快速幂

题目描述：给出m(m 这道题目深层次地利用了AC自动机，但是并没有用到AC自动机中的find(query)函数，而是用到了BFS序建立失败指针走向，以及为字典树中的空节点加上侧向边的BFS函数（或者有的叫getFail函数），所以，在继续读之前，确保已经非常清楚AC自动机为字典树加上侧向边是怎么回事。看下面的例子，模式串的集合为{ATC ， T}，那么建完

2017-02-17 15:32:39 729 1

原创 ZOJ3329 One Person Game 概率dp

/* 题目描述：有三个骰子，每个上面的数值分别是1~K1 , 1 ~K2 , 1 ~K3，有一个计数器，其初始值为0，现在抛三枚骰子，如果当前计数器的值加上这三枚骰子的点数和大于n，那么游戏结束，否则将计数器的值加上点数和后游戏继续，但是，如果掷出的三枚骰子的值为a,b,c时，计数器的值清零，先问游戏中投掷骰子的期望是多少？思路：设dp[

2017-02-15 09:25:56 235

空空如也

空空如也