- 博客(281)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 用EM算法求解高斯混合模型
本文从高斯混合模型出发，引出EM算法，最后回归到利用EM算法求解高斯混合模型。理论部分力求详尽不留证明疑点，所以略显冗长。实验部分给出了生成高斯混合分布样本和利用EM算法求解高斯混合模型的matlab代码。
2017-04-28 15:54:36
7890
6
原创 输出字典序最小的最小割集
USACO 5.4Telecowmunication/*ID: gyarena2PROG: telecowLANG: C++*/char *Task = "telecow";#include <cstdio>#include <cstdlib>#include <string>#include <algorithm>#include <utility>#include <cstri
2016-11-10 10:21:44
606
原创 Dilworth定理与有向无圈图的链覆盖
Dilworth定理的应用条件为偏序集，定理转化为图论语言就是偏序集哈斯图的最长反链等于其最小链点覆盖数。 对于有的问题可以通过贪心分解链求最小链点覆盖或直接求其最大反链长度，从而得出解，例如：俩个全序集的笛卡尔积构成的偏序关系。 例题： http://poj.org/problem?id=1065 http://poj.org/problem?id=1548 http://poj.org
2016-11-08 12:00:08
1188
原创 最小树形图
Problem DescriptionGiven a weighted digraph GG，a specific vertex v0v_0. Find an arborescence TT with root v0v_0 and minimize the weight sum of arcs of TT.Algorithmhttps://en.wikipedia.org/wiki/Edmonds
2016-07-23 12:35:14
542
原创 单点度限制最小生成树存代码
Problem DescriptionGiven a weighted graph GG，a specific vertex v0v_0 and an integer KK, find a spanning tree TT with restriction deg(v0v_0)=KK (we don’t care about other vertices’ degrees) and minimize
2016-07-19 16:37:01
379
原创 2-SAT存模板
例题：http://acm.hdu.edu.cn/showproblem.php?pid=3622O(|V||E|)方法#include <cstdio>#include <cstdlib>#include <algorithm>#include <utility>#include <cstring>#include <map>#include <climits>#include <
2016-07-04 14:25:40
319
原创 Normalized Cuts and Image Segmentation
Abstract Model image segmentation problem by normalized cuts, then solve the relaxed normalized cuts problem using spectral clustering. NotationsGG: G=(V,E)G=(V,E) be an undirected graph with vertex
2016-06-28 16:53:29
2991
原创 Unsupervised Nearest Neighbors Clustering With Application to Hyperspectral Images
A dynamic niching clustering algorithm based on individual-connectedness and its application to color image segmentationAbstract KSEM, a stochastic extension of the kkNN density-based clustering (KNNC
2016-06-26 12:32:50
453
原创 A dynamic niching clustering algorithm based on individual-connectedness and its application to colo
A dynamic niching clustering algorithm based on individual-connectedness and its application to color image segmentationAbstract Automatically evolve the optimal number of clusters as well as the clus
2016-06-05 11:03:16
533
原创 hihoCoder#1090
题目地址：题目大意：在一条单行路(只允许向着同一方向走)上有n辆车，第i辆车以不超过L[i]的速度从位置X[i]走到位置Y[i](X[i] 分析：方便起见我们假设数据已经按照X[i]从小到大的顺序排好序(编号从0到n-1，如无特殊说明我们直接以i表示第i辆车)，且车辆行驶方向为从左向右。仔细思考，可以发现下面两条性质：性质一，左边的车对右边的车没有影响，也即
2015-10-01 13:38:40
1232
原创 非负权无向图的全局最小割
O(n^3)的StoerWagner算法论文：http://wenku.baidu.com/view/072209d5360cba1aa811da51
2015-06-03 15:42:49
1155
原创 关于B-K tree与k-d tree一些自己想法
以前用B-K tree做过一个题，最近学习k-d tree，感觉这两个树有某些相似，这个俩种树都是寻找距目标点临近最近的点(B-K tree针对给定距离k以内，k-d tree针对给定最近的k个点)。其中B-K tree只要求数据点之间定义可度量的距离，支持求距给定点距离k以内的数据点。相对于暴力法来说，是常数级别的提高，但有时会很有效（比如数据点之间距离范围很大，但阀值k很小），一个应用就是
2015-05-10 19:19:41
2339
原创 K-Means的简单实现
#include #include #include #include #include using namespace std;const int MAXN(100010);const int MAXK(100010);const int MAXC(5);templateinline bool checkmax(T &a, const T &b){ return
2015-05-07 19:38:22
641
原创 一道有意思最短路
http://codeforces.com/contest/29/problem/E俩个动点的最短路问题，要求俩个点同时移动且不能同时到达在同一点，俩个点要一直移动不能停留等待，求同时到达各自目标点的最短路径。定义状态空间[a][b][c]（1#include #include #include #include #include #include #include #i
2015-05-04 11:59:02
619
原创 增加最少的边使有向图变为强连通图
http://codeforces.com/contest/22/problem/E标题党。。。此题是这个问题的简化版本，每个点出度至多为一。先强连通缩点，每个点出度至多为一可以保证从任一个入度为0的点出发只能到达一个出度为0的点 。按标号从第一个入度为0的点a开始，找到其对应的出度为0的点(缩后)a'，再找到第二个入度为0的点b，连边a'->b，...，直到最后一个出度为0的点z‘，连边
2015-04-30 16:14:11
3305
原创 一道不错的dp题
http://codeforces.com/contest/18/problem/E状态很容易设计，但如果直接求解的话复杂度很高，需要技巧优化决策步骤。#include #include #include #include #include #include #include using namespace std;typedef long long LL;t
2015-04-29 16:12:44
569
原创 带修改的区间第k大
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1112提高代码能力。。。方法一：线段树套平衡树，时间：O(m*lgn*lgn*lgn)，空间：O(n*lgn)。#include #include #include #include #include using namespace std;c
2015-04-18 18:07:14
2624
原创 关于串的循环移动与最小覆盖几个问题
以下对于串的加法即连接操作，数乘n表示复制n次，|S|表示串S长度，先yy几个名词分子串：如果串S = k×S'(其中k>=1)，则称S'为S的一个分子串。原子串：所有S'中长度最小的称为S的原子串，记为S*。覆盖串：如果串|S''| ×S''(其中k>=1)的前缀，则称S''为S的一个覆盖串。最小覆盖串：所有S''中长度最小的称为S的最小覆盖串，记为S^。例1：S=“abca
2015-01-04 21:25:46
659
原创 所有边权均不相同的无向图最小生成树是唯一的证明
用反证法，假设G存在俩个不同的最小生成树①.设G的俩个不同的最小生成树T1 T2，设这俩颗生成树的并集为子图G1，G1为连通图且T1 T2显然为G1的最小生成树，将G1中两颗生成树的公共边删去，得到子图G2。G2由一个或多个连通分量组成，其中至少有一个连通分量的最小生成树不唯一（否则若所有连通分量的最小生成树唯一，则将删掉的公共边加上，则T1等于T2，这与假设相矛盾）。②.对其中一个最小生
2014-12-29 22:10:39
25565
5
转载 读书
春宜读诗，冬宜读史。 黄昏宜读情书，清晨宜读外语。 月下宜读西厢，半夜宜读聊斋。 读教材宜考前，读晚报宜浴后。 读唐诗宜坐，读宋词宜卧。 百年后有价之书宜藏，两三年寿命之书宜借，明星传记宜在书店站着翻，朋友送书宜收 不宜看，自己赶职称之书宜扔不宜送。 读论语宜曲阜音，读孟子宜滕州调，读老庄宜河南腔。 林中宜读王维，舟中宜读曾祺。 读陆游宜舞剑，读黄裳宜听戏。
2014-05-21 13:18:05
960
3
原创 Reincarnation hdu4622 hash解法
http://acm.hdu.edu.cn/showproblem.php?pid=4622这题的ha
2014-04-05 10:38:19
1479
1
原创 Shut the Box HDU4212
http://acm.hdu.edu.cn/showproblem.php?pid=4212论文写烦了，水了一道很水的一道状压DP，状态很稀疏用map搞下，预处理很关键。#include #include #include #include #include #include #include #include #include #include #incl
2014-04-02 22:52:35
814
原创 关于筛法
以前总以为超过500万数据线性筛法要比nlogn筛法跑的快，用5亿以内数据测试了下，加了优化的nlogn筛法总是要比线性筛法快的，对于用位压省内存来说，nlogn的筛法优势尤其明显，以后统一用如下筛法了。int prim[MAXN/10], npr;bool isnp[MAXN+1];void init(){ npr = 0; prim[npr++] = 2; isn
2014-03-31 23:11:21
845
转载 SQL Server游标的使用【转】
游标是邪恶的！ 在关系数据库中，我们对于查询的思考是面向集合的。而游标打破了这一规则，游标使得我们思考方式变为逐行进行.对于类C的开发人员来着，这样的思考方式会更加舒服。 正常面向集合的思维方式是: 而对于游标来说: 这也是为什么游标是邪恶的，它会使开发人员变懒，懒得去想用面向
2014-03-21 23:16:44
534
转载 access 在指定的 DSN 中，驱动程序和应用程序之间的体系结构不匹配
本机是win7 64位操作系统，做数据库实例时需要创建Access数据库的ODBC数据源，但是打开ODBC数据源后发现添加里面没有配置access的连接，如下图：还会弹出以下问题框： 解决方法：打开目录：“C:\Windows\SysWOW64”，双击该目录下的“odbcad32.exe”文件（以前打开的是C:\Windows\system3
2014-03-21 10:26:30
14411
1
转载 CString,string,char
CString 头文件#include string 头文件#include CString 转char *CString cstr;char *p = (LPSTR)(LPCTSTR)cstr;string 转 CStringCString.format(”%s”, string.c_str());char 转 CStringCString
2014-03-14 11:51:24
577
原创 数论笔记
以下如无特殊说明，都默认在整数集中,^为幂符号，|为整除符号，%为取模符号，!| 表示不能整除1. 费马数是形如2^(2^n)+1(n >= 0)的数,表位Fn,任意俩个费马数是互质的。 证明:首先，对任意的Fn 都有 Fn%2 = 1，所以对于任意的不为1的d，使得 d|Fn 都有d>2;当n>m时，可以证明 Fm|2^(2^n)-1; ①设Tk = 2^(2^k)-
2014-01-14 15:57:15
1718
原创 Marlon's String zoj3587
后缀数组或扩展kmpSA做法#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #
2014-01-09 21:26:50
633
原创 关于维护AC自动机fail树的三道题目
由易到难e-Government CF 163Ehttp://blog.csdn.net/gyarenas/article/details/9315319GRE Words hdu 4117 http://acm.hdu.edu.cn/showproblem.php?pid=4117这题本来的做法是ac自动机优化dp，然而hdu加入了新的数据，估计构造了一些
2014-01-06 18:51:30
2751
原创 HDU4821
HASH后就是一个简单的线性统计了#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include
2014-01-04 11:47:30
2107
1
转载 素数一小坨
素数基础篇 之 素数的判断 - czyuan原创源链接:http://hi.baidu.com/vfxupdpaipbcpuq/item/34976fc954dae62eee466512素数：只有两个正因数（1和自己）的自然数。素数，作为数论中最基础的理论之一，又是许多著名定理的根源。几个可以无视的性质：1. 1不是素数2. 除了2以为所
2013-12-31 21:10:58
1320
原创 Number Transformation CF 251C
http://codeforces.com/contest/251/problem/C关键就是注意到从i*lcm(1,2 ...K)转移到(i-1)*lcm(1, 2...K)的代价等于lcm(1, 2...K)转移到0的代价，而且由于第一种操作只能减小1而第二种操作不可能越过过i*lcm(1, 2...K)的(可以用反证法证明)，所以转移的过程必然会经过所有的i*lcm(1, 2,
2013-12-30 20:09:05
682
原创 Hard Life poj3155
最大密度子图，论文题目。 这题构造出来的g(k) = max{∑E-k∑V},g(k)是一个下界为0的单调递减函数，即存在x1, g(x1) = 0,对于所有x > x1, g(x)≡0。按照论文上的证明方法的话我们只要发现一个g(k) = 0,就可以认为是最优解了，但是此题要二分到函数值为0的左端点才可以，为什么是这样呢?其实我们不难发现对于所有的x > x1, 我们采取的最优决
2013-12-11 21:30:39
793
原创 steiner tree的几道题目
hdu 4085http://acm.hdu.edu.cn/showproblem.php?pid=4085注意森林情况转移时要注意保证每个子森林的房间数等于避难所数#include #include #include #include #include #include #include #include #include #include #include
2013-12-09 16:34:14
834
原创 Good Substrings
http://codeforces.com/contest/316/problem/G3SAM上DP在某岛的博客上看到的，要义就是一个串的子串必然是该串某个后缀的前缀，所以从表示该状态的子串节点往后走必然会走到那个串的尾节点。#include #include #include #include #include #include #include
2013-12-01 12:06:14
728
原创 相似子串 bzoj3230
http://www.lydsy.com/JudgeOnline/problem.php?id=3230后缀数组#include #include #include #include #include #include #include #include #include #include #include #include #include
2013-11-28 20:43:02
797
原创 Substitution Cipher spojSCYPHER
http://www.spoj.com/problems/SCYPHER/拓扑排序，要求是全序集#include #include #include #include #include #include #include #include #include #include #include #include #include #include
2013-11-24 14:57:14
841
原创 无向图中国邮路(小数据版)
http://ac.jobdu.com/problem.php?pid=1430#include #include #include #include #include #include #include #include #include #include #include #include #include #include #inclu
2013-11-23 21:14:38
1171
原创 AC's String HDU3973
http://acm.hdu.edu.cn/showproblem.php?pid=3973线段树维护HASH#include #include #include #include #include #include #include #include #include #include #include #include #include #inclu
2013-11-20 10:11:50
877
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人