5 tham_

尚未进行身份认证

凡是新的事情在起头总是这样,起初热心的人很多,而不久就冷淡下去,撒手不做了。因为他已经明白,不经过一番苦工是做不成的,而只有想做的人,才忍得过这番痛苦。

等级
TA的排名 1w+

挑战程序设计竞赛 — 知识总结

准备篇1.5 运行时间概述编写的目的是面向ACM程序设计竞赛,不可避免的要涉及复杂度和运行时间的问题,本节给出了解决问题算法选择的依据。假设题目描述中给出的限制条件为n<=1000,针对O(n2)的算法将会执行大于106次。如果时间限制是1s,则有下述结论:上述结论表明,针对O(n2)的算法,n<=1000可以在时限内解决,但是如果n<=10000,则超时的可能性非常大,这就启示...

2018-07-08 17:04:47

NOIP2017 国庆郑州集训知识梳理汇总

第一天  基础算法及数学基本算法递推、递归、分治 二分、倍增 贪心递推指通过观察、归纳,发现较大规模问题和较小规模问题之间的关系,用一些数学公式表达出来在一些题解中,和“计数DP”是指同一个概念看例题例 1用 1 * 2 的骨牌,覆盖 2 * n 的棋盘的方案数?解:很经典的Fibonacci 数 O(n) 求

2017-10-09 09:08:55

从平面上最近的点对,谈谈分治算法

首先介绍一下分治(Divide-and-Conquer )算法:设计过程分为三个阶段–Divide: 整个问题划分为多个子问题–Conquer:求解各子问题(递归调用正设计的算法)–Combine:合并子问题的解, 形成原始问题的解如下图:举例说明题目大意给你n个点,求出其中点与点之间的最短距离。 算法

2017-09-04 16:20:54

莫队算法讲解

问题:有n个数组成一个序列,有m个形如询问L, R的询问,每次询问需要回答区间内至少出现2次的数有哪些。  朴素的解法需要读取O(nm)次数。如果数据范围小,可以用数组,时间复杂度为O(nm)。如果使用STL的Map来保存出现的次数,则需要O(nmlogn)的复杂度。有没有更快的方法呢?  注意到询问并没有强制在线,因此我们可以使用离线方法。注意到一点,如果我们有计算完[L, R]

2017-08-19 22:53:20

随机算法 —— 模拟退火

模拟退火例题:CodeVS: P1344 有 N ( P2 -> P3 -> ... -> PN 找出 |P1P2|+|P2P3|+...+|PN-1PN| 长度的最小值)这种问题被称为最优组合问题。传统的动态规划算法O(n22n)在n = 20的情况下空间、时间、精度都不能满足了。这时应该使用比较另类的算法。随机化算法在n比较小的最优化问题表现较好,我们尝试使用随机化算

2017-08-19 22:41:26

OI (信息 ) 竞赛中的对拍程序,造数据,对拍利器

作为一名OIer,比赛时,对拍是必须的 不对拍,有时可以悔恨终身首先,对拍的程序 一个是要交的程序 另一个可以是暴力、搜索等,可以比较慢,但是必须正确下面是C++版对拍程序(C++ & cmd) 注意:所有程序不用加文件输入输出#include#include#includeint main(){ long s,t; while(1){

2017-08-19 15:11:20

Codechef GRAPHCNT 支配树学习及tarjan算法求解

[Codechef GRAPHCNT]新年的有向图【题目描述】zlx同学在学习数论时,被虐了一脸,丧心病狂的他决定去报复社会。zlx在公园里埋下N颗地雷,用来炸飞在春节期间秀恩爱的情侣。这N颗地雷由M条有向边连接成为一个有向图,zlx则在1号地雷处引爆1号地雷可以到达的地雷。现在,为了更好的实施这个计划,zlx需要知道存在多少对地雷(x,y),使得存在一条1到x和一

2017-07-29 09:17:55

Emacs指北(做一个搬运工好累)

从一个简单的emacs入门教程说起:一个不知道怎么描述的emacs教程一个简单的介绍emacs[/ˈiːmæks/]是地球上的编辑器中最像操作系统,操作系统中最像编辑器的编辑器,按照elisp intro的说法,emacs 是一个可拓展计算环境(extensible computing environment),这一点,如果 学过elisp,可以深刻的体会到。

2017-07-18 17:13:17

firefox浏览器无法打开百度,但是能ping通百度的域名

机房Ubuntu14.04,突然发现firefox打不开百度了,但却能打开其他网站。猜想1:首先想到的是不是我的网络有问题实验1:ping www.baidu.comxs@PC:~$ ping www.baidu.com正常返回数据,且延时很小。由于浏览器能够访问bing,于是我又ping  www.bing.comxs@PC:~$ ping  www.bi

2017-07-09 21:45:33

二分图及其匹配算法——最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配

§1图论点、边集和二分图的相关概念和性质§2二分图最大匹配求解匈牙利算法、Hopcroft-Karp算法§3二分图最小覆盖集和最大独立集的构造§4二分图最小路径覆盖求解§5二分图带权最优匹配求解Kuhn-Munkers算法§6小结每章节都详细地讲解了问题介绍,算法原理和分析,算法流程,算法实现四部分内容,力求彻底解决问题。 

2017-06-05 22:41:47

学习一项技能要花多少时间?

转载自: Rei(Ruby-China 创始人)   http://chloerei.com/2013/12/12/how-long-does-it-take-to-learn-a-skill/前不久,一个技术 party 上有人问我:“我学习 Rails 已经2个月了,但还是对整个开发流程缺乏清晰的了解,我应该怎么学呢?”这不是个别现象,在 ruby-china.org 上也经常有人发帖,说

2017-05-21 14:02:04

无向图的割点、桥与双连通分量

概念对于无向图G,删除顶点v 和其相连的边后G所包含的连通分量增多,则称v为关节点 (articulation point) 或割点 (cut point)。同理,删除边e 和其相连的顶点后图包含的连通分量增多,则e 是割边 (cut edge) 或桥 (bridge)。割点形式化的定义:A 是割点当且仅当存在两个点u,v 使得u 到v 的每条路径都会经过A (去掉A 后,

2017-05-16 21:15:46

hihocoder#1369 : 网络流算法的一些小结

一道最大流模板水题,借这道题来学习一下最大流的几个算法。分别用Edmond-Karp,Dinic ,SAP来实现最大流算法。从运行结过来看明显SAP+当前弧优化+gap优化速度最快。 hihocoder #1369 : 网络流一·Ford-Fulkerson算法原题网址:http://hihocoder.com/problemset/problem/13

2017-04-11 20:47:19

树链剖分 — 轻重边路径剖分

“在一棵树上进行路径的修改、求极值、求和”乍一看只要线段树就能轻松解决,实际上,仅凭线段树是不能搞定它的。我们需要用到一种貌似高级的复杂算法——树链剖分。树链,就是树上的路径。剖分,就是把路径分类为重链和轻链。    记siz[v]表示以v为根的子树的节点数,dep[v]表示v的深度(根深度为1),top[v]表示v所在的重链的顶端节点,fa[v]表示v的父亲,son[v]表示与v

2017-04-01 16:58:41

分治、CDQ分治小结

分治、CDQ分治小结 A Summary for Divide and Conquer0. Anouncement本文部分图片以及部分内容来自互联网,内容过多就不一一注明出处了,冒犯之处还请海涵。 Some of the pictures and the content of the text come from the Internet. Due to plenty of

2017-03-30 22:24:06

Segment Tree 线段树小结

线段树小结 A Summary for Segment Tree0. Anouncement本文部分图片以及部分内容来自互联网,内容过多就不一一注明出处了,冒犯之处还请海涵。 Some of the pictures and the content of the text come from the Internet. Due to plenty of the conten

2017-03-30 22:06:51

多项式, FTT, NTT小结

FFT、NTT小结https://www.zybuluo.com/TaoSama/note/171617

2017-03-30 22:05:04

transform函数转换字符串string的大小写

首先看一下transform函数的用户手册:template OutputIterator transform ( InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperator op );template < class Input

2016-04-20 15:45:24

Hiho 数论一·Miller-Rabin质数测试,大素数判断

题目1 : 数论一·Miller-Rabin质数测试时间限制:10000ms单点时限:1000ms内存限制:256MB描述小Hi和小Ho最近突然对密码学产生了兴趣,其中有个叫RSA的公钥密码算法。RSA算法的计算过程中,需要找一些很大的质数。小Ho:要如何来找出足够大的质数呢?小Hi:我倒是有一个想法,我们可以

2016-04-18 21:37:06

二分图的最大匹配、完美匹配和匈牙利算法

这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm);不讲带权二分图的最佳匹配。二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为

2016-04-18 11:58:26

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!