Pira-CSDN博客

原创 ACM各种模版整理

RT：ACM各种模版整理，欢迎大家查错，围观，吐槽，已经尽量写得好看了= =https://github.com/PiraHzq/acm_templates顺便说一句github挺不错的！！！

2013-09-04 11:00:35 3848

转载国家集训队论文分类整理

转自：http://www.cnblogs.com/AbandonZHANG/archive/2012/07/21/2601889.html国家集训队论文分类整理距离ACM/ICPC的时间越来越少了，选择性地看一些集训队论文是很有必要的。（在此给已经看过所有论文的神牛跪了= =）所以，我在此整理了一下，供大家参考。组合数学计数与统计

2013-06-12 14:24:52 15319

原创后缀数组da+dc3

以前一看到字符串的题目就有些畏惧，感觉无从下手，只会个KMP和AC自动机，很多情况下都是力不从心，所以打算学各种高端的算法，来解决这类问题，后缀数组应该是性价比教高的吧，至少很简单，容易理解，算法实现是另一回事，毕竟ACM比赛是可以带模版的，所以它也就显得简单实用了，下面一起看看这个实用的数据结构吧！首先给定一些定义：字符串S，s[ i ]表示第i个字符，s[ i , j

2013-05-29 21:14:47 4710 1

转载 ACM计算几何题目推荐（第二期）

之前写过一篇《POJ计算几何入门题目推荐》。本来是随意写写，想不到这篇文章成为了我 blog浏览量第二高的文章，还被许多ACMer转载到其他地方。最近估计ACM赛季又到了，不少热心的ACMER加我Q，询问我那篇文章的事情，希望我再给出一些题目。本人已经退役了，本来不想再写一些关于ACM的东西了，以免因为自己水平有限，思想落后，误导他人。不过后来想到这个空间晾着也比较尴尬，让各位找新文章的

2012-09-26 16:30:41 3694 6

转载计算几何题

计算几何其实也谈不上推荐，只是自己做过的题目而已，甚至有的题目尚未AC，让在挣扎中。之所以推荐计算几何题，是因为，本人感觉ACM各种算法中计算几何算是比较实际的算法，在很多领域有着重要的用途（例如本人的专业，GIS）。以后若有机会，我会补充、完善这个列表。计算几何题的特点与做题要领：1.大部分不会很难，少部分题目思路很巧妙2.做计算几何题目，模板很重要，模板必须高度可靠。3.

2012-07-30 18:12:08 1844 6

原创我的DP训练情结（starting...）

整理原因：由于高中参加Noip时，主要做的题目都是些DP，搜索，还有一堆杂题，自从开始ACM生涯之后，发现不会的算法太多，于是专攻算法，然后就悲剧的发现，做题能力大大降低，我想没有练习这些DP，搜索还是不行的，从现在开始从新加强DP与搜索。。。从头开始，因为忘得太透彻了= =，纯属酱油，供雷同者参考。。。目的：供自己全面复习，给后来者作为参照内容：不具体讨论

2011-09-28 20:26:48 8013 21

原创我的跳舞链 Dancing Links 模板

第一个模板——精确覆盖问题题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3038为什么选择这题呢，因为它既可以当作数独模板又能当成DLX模板，不是一举两得吗^ ^#includeusing namespace std;const int N=16;const int mm=N*N*N*4+N*N

2011-09-22 12:48:25 2042

转载强连通分量与双连通分量

本文转自：http://blog.stqdd.com/?p=209对于有向连通图，如果任意两点之间都能到达，则称为强连通图。如果对于有向图的一个子图是强连通的，则称为强连通子图；极大的强连通子图称为强连通分量。一个有向图可以有多个强连通分量，一个点也算是强连通分量。强连通分量的术语是strongly connnected components,简称SCC 对于无

2011-09-08 17:51:56 1705 1

转载有向图强连通分量的Tarjan算法

本文转自BYvoid[有向图强连通分量]在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3

2011-09-05 20:53:39 824

转载图的割点、桥与双连通分支

本文转自BYVoid大牛，先膜拜再说，转载以后深入研究。。。[点连通度与边连通度]在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点

2011-09-05 20:50:16 840

原创我的最小树形图模板(已更新)

这个写法复杂度为O(ElogE+V*V)，关键耗时在排序上，当边权范围相对小的时候，用基数排序优化，做到O(V*V)*常数，这个效率非常可观，基本上如果满足边权要求就用这个模板了，希望有人帮我优化下普通情况下的排序。。。之后再给出普通版的模板，先贴这个基数排序优化的代码（

2011-09-05 14:21:28 2360

转载 ACM训练方案

初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法

2011-09-04 14:48:40 2116 2

转载最小树型图的求解与实现

转自：http://www.zlinkin.com/?p=63　　图论是ACM竞赛中比较重要的组成部分，其模型广泛存在于现实生活之中。因其表述形象生动，思维方式抽象而不离具体，因此深受各类喜欢使劲YY的Acmer的喜爱。这篇文章引述图论中有关有向图最小生成树的部分，具体介

2011-09-03 19:33:26 2301

转载最小树形图

==========================分割线之下摘自Sasuke_SCUT的blog======================================最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所

2011-09-03 19:31:42 976

转载网络流之--混合图的欧拉回路

基础知识欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。无向图中存在欧拉回路的条件：每个点的度数均为偶数。有向图中存在欧拉回路的条件：每个点的入度=出度。欧

2011-09-02 15:57:57 1114

转载一些图论、网络流入门题总结、汇总

最短路问题此类问题类型不多，变形较少POJ 2449 Remmarguts' Date(中等)http://acm.pku.edu.cn/JudgeOnline/problem?id=2449题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很多相关：http://acm.pku.edu.cn/JudgeOnline/showcontest?cont

2011-08-31 18:37:33 1581 3

转载网络流题目集锦

橙色的链接表示A掉了，转向我的题解。。。转载自分享最终编辑 acmcs最大流 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance POJ 1459 Power Network POJ 2112 Optimal Milki

2011-08-31 18:36:39 1059

原创我的模板最大流（Dinic & Isap）+最小费用最大流（SPFAFlow）==有更改

今天刻意用poj 3469 http://poj.org/problem?id=3469测了下模板，Isap并不像想象中那么快，难道是我写搓了，而且在网络流与线性规划中的最后一题，isap完败给Dinic了,我的Isap啊~~~不知道那些几百毫秒出解的是用什么算法。。。难道是。。。 dinic总体上挺不错的，递归版的Isap基本上与Dinic没差别，而非递归版在某些情况反而不如递归版，于是

2011-08-10 15:16:52 4535 7

原创囧——线性规划与网络流24题之网络流入门经典

搞了好久终于搞定线性规划与网络流24题，不过机器人路径至今无解，第22题感觉是数据错了~~~我的代码，数据和题目题解是BYVoid那弄到的：http://download.csdn.net/source/3499468

2011-08-06 17:10:00 1487

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以 MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。 常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小 的评测。<br

2011-04-21 20:55:00 1006

原创在gitcafe下用hexo建的新博客

看到别人用hexo建的静态博客，感觉还不错，也就跟着建了一个，似乎有跟风的嫌疑，主题也是用别人的，太懒了，有兴趣的时候再慢慢改变它吧，所以这个博客也许就冻结在这一刻了，又或许某天新博客蹦了，我还会回来？虽然感觉没人会想起我，不过我还是放出链接http://blog.dorastory.com/

2014-03-15 09:52:56 3142

原创退役了

银牌收尾，没有太多的意外，不过死在自己认为最擅长的数据结构上，有点残酷T_T大一的几个目标一个个都没实现，只有坚持到大四退役这个目标实现了。。。眼下工作没着落，也不想读研，不知道何去何从了。。。。。。

2013-12-09 09:20:10 4335 29

转载成为IT精英，我奋斗了7年

这些日子我一直在写一个实时操作系统内核，已有小成了，等写完我会全部公开，希望能够为国内IT的发展尽自己一份微薄的力量。最近看到很多学生朋友和我当年一样没有方向，所以把我的经历写出来与大家共勉，希望能给刚如行的朋友们一点点帮助。一转眼我在IT行业学习工作已经七年多了，这期间我做过网页，写过MIS、数据库，应用程序，做过通信软件、硬件驱动、协议栈，到现在做操作系统内核和IC相关开发，这中间走了很多

2013-09-16 13:23:51 5157 5

原创 ZOJ 3016 Cut（离散化+最小生成树）

地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3016题意：给你n条线段，这些线段都平行于坐标轴，没有线段重叠，但是有交点，切割每条线段有一个值，现在这些线段形成一些封闭的区间，问怎样切割使得所有点之间有通路，且花费最小分析：这题抛掉线段的外壳，很容易发现每个格子是一个点，外面的平面是一个点，点之间的边正好是

2013-07-14 09:34:52 2260

原创 ZOJ 3018 Population(二维线段树？矩形树？)

地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3018题意：在平面内最多又32768个点，现在有两种操作，1：在一些点上加上一个数n，2：询问一个矩形区域内的点的数的和分析：这题一看像线段树，想离线搞，发现不好处理，也许可以，不过我是做不来了，后来自己YY了下二维的线段树，从来没写过= =，一开始发现空间会爆

2013-07-14 09:18:30 2715 1

原创我在Ubuntu13.04下用的一些软件配置

这些东西都没什么技巧，大部分都是从网上找到的，不过方便以后配置吧配置更新源首先，当然得配置好更新源，没有这个会出很多问题，这里选用搜狐的，不知道为什么，我们学校用校内的源速度不行= =deb http://mirrors.sohu.com/ubuntu/ raring main restricted universe multiversedeb http://mirrors.s

2013-06-28 11:48:18 2964

原创 ZOJ 2962 Stack By Stack（递归）

题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2962题意：给你n个栈，每个栈给定大小为Ci，现在进行这样的操作：情况1,当没有栈是满的情况，将第一个栈装入1~C1的数，也就是装满；情况2,有一个栈i已经装满，那么将栈i的内容逐个弹出，装到下一个栈i+1中，直到栈i+1满了，或者栈i空了，注意如果栈i+1

2013-06-24 15:19:46 2265

原创 zoj 3540 Adding New Machine(map+离散化)

地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4495题意：给你w*h个格子，并且一些矩形块占用着一些格子，问剩下的空间，能装下1*m的矩形的方案数分析：我们可以枚举一个下标，然后维护另一个下标构成的线段，由于题目的特殊性，线段不会重叠，所以变得简单了许多，对于每次添加一条线段l~r，它的左边第一条线段的右边界是

2013-06-15 16:01:05 2217

原创 poj 3415 Common Substrings(长度大于k的相同子串对数xian 后缀数组+单调桟统计)

地址：http://poj.org/problem?id=3415题意：给你两个字符串，还有一个数字K，要求这两个字符串长度大于等于K的相同子串对数，具体看题目分析：这题求相同子串，自然就会让人想到后缀数组之类的解法，不过后缀数组只能求出最长的公共子串，还有一些公共前缀的信息，没办法完成统计子串对数，我想了半天都没想出办法，然后看了一眼讨论，有人说是单调性。。。我就继续往这方面思考了，仔细

2013-06-05 14:06:29 2846 4

原创 hdu 4303 Hourai Jeweled(树型DP+统计答案)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4303题意：给你一颗树，每个节点有权值，每条边有颜色，问所有满足相邻边颜色不同的路径的权值之和分析：一开始看成求权值最大的路径，所以就是水题了，不过加个统计就得略想一下子，f[ i ]表示i的所有子节点的连到i 路径和，这里有个限制就是i到子节点的颜色与i到父节点的颜色不同，g[ i ]记录相应的边

2013-05-31 09:22:54 2695 1

原创 spoj 220 Relevant Phrases of Annihilation(n个串的最长公共重复2次子串)

地址：http://www.spoj.com/problems/PHRASES/题意：给你n个串，求最长的公共重复子串分析：跟两个串的最长的公共重复子串差不多，也是将所有串合成一个串，构造后缀数组，然后二分子串长度，在满足条件的区间里，求出n的串的下标的上下界的差值大于等于当前长度，所有串都满足说明存在解，否则无解。。。代码：/** head files*/#include #

2013-05-30 17:15:13 2555

原创 poj 1743 Musical Theme(最长不重叠重复子串后缀数组+二分)

题目：http://poj.org/problem?id=1743题意：给你一个序列，求序列里长度至少为5的最长不重叠重复子串，这里的重复包括每个元素加减相同的值分析：对于区间加减可以通过将相邻的元素的差组成新的序列，答案就变成求至少长度4的最长不重叠重复子串，并且至少间隔1的距离，然后就可以用后缀数组来做了，然后二分子串的长度L，找到height数组大于等于这个长度L的区间，求区间对应原

2013-05-30 16:12:04 2466

原创 poj 3294 Life Forms(后缀数组+二分)

题目：http://poj.org/problem?id=3294题意：给你n给字符串，求在一半以上的串里重复出现的最长子串分析：将所有字符串合成一个串，字符串自己用不同的字符标记间隔，然后构造新字符串的后缀数组，很容易发现，相同子串一定在后缀数组里相邻，只要判断一个区间里的子串里是否包括了超过一半的不同串，我们只要二分子串的长度，就能得到一些区间，height数组大小都大于等于该长度，这

2013-05-30 13:28:14 2294

原创 POJ 3261 Milk Patterns(后缀数组)

题目：http://poj.org/problem?id=3261题意：给你一个序列，求序列里重复出现至少K次的最长子串分析：这题如果学过后缀数组的话，那就是模版题了，直接构造一个后缀数组，然后枚举i，询问[ i, i+k-1 ] 的最长公共前缀就行，i表示排在第i位的后缀代码：/** head files*/#include #include #include #incl

2013-05-30 10:33:06 2282

原创 vijos 1069 新年趣事之红包(区间DP)

题目：https://vijos.org/p/1069题意：给你一个凸包，问遍历所有点一遍的最短路径分析：由于图形是一个凸包，所以肯定是选一个点，然后从两端不断拓展出去，假设已经拓展[i , i+len ]这几个点，且f[ i ][ len ][0]为遍历这些点，且终点为i的最短路，f[ i ] [len] [1]为遍历这些点，且终点为i+len的最短路，那么有

2013-05-18 20:43:56 2428

原创 hdu 4546 优先队列数列组合和第m小

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4546题意：给你n个数，问这n个数的组合的和，第m小是多少分析：很明显的，要给初始序列排序（我写的时候居然忘记排序了，看来下次得把步骤写下来= =），然后发挥想像力，你会发现这其中有一定规律，我们可以假设有这样的元素，struct data{ int start, i;}

2013-05-18 09:23:03 3117 6

原创 Manacher算法——求最长回文子串

Manacher算法是用来求解一个给定字符串的最长回文子串，回文就是将字符串翻转后，与原来一样。这个算法通过添加字符，巧妙的将回文长度为偶数的情况转化成奇数，简化了问题的步骤，并且利用回文的性质，将去除了冗余的比较，从而将复查度降到O(len)，能够求出以每个字符为中心的最长回文，从而求出最长的回文子串。现在，简述一下算法的过程：在相邻的两个字符之间（包括首尾）添加特殊字符（也就是

2013-05-16 15:50:53 2158

原创 vijos 1014 旅行商简化版（多路DP）

地址：https://vijos.org/p/1014题意：旅行商问题，不过要求只能单向走，就是有n个地方，要求从西往东，到最东面的地方，在从东往西返回，经过每个点一次，求最短路径分析：由于有了方向的限制，这题不再是NP难题，我们可以假设有两个人一起从西往东走，走过的点不能重复，这样就有f[ i ][ j ]表示第一个人走到i，第二个人走到j 的最短路径，要求i最后，预处理f[ 0 ]

2013-05-07 10:17:08 2415

原创 vijos 1002 过河（一类压缩长度的DP）

地址：https://vijos.org/p/1002题意：一条直线上有m个点，青蛙一次能跳的长度为s~t，每个点的坐标范围1~10^9，1分析：这题一下子就能想到简单的DP，f[ i ] =min{ f[ j +k ] }+w (s<=k<=t, w为i坐标是否有石子），这样的复杂度是O(L*t)的，主要时间都在L上，由于石头数m比较少，我们应该会发现，实际上有许多石头相隔很远，这之间

2013-05-06 14:42:50 1541

原创 SDL学习笔记五（音乐播放）

一直想写个播放器之类的东西，但是缺少音频文件的解码知识，又懒得去学习，毕竟急着写个像样的软件，而且自己写解码器需要太多时间，并且不能保证可以处理大部分情况，难免会有bug，幸好SDL再次提供了拓展库SDL_mixer，它本身自带的支持格式太少，不过拓展库已经支持大部分的格式，现在来看看这些简单且常用的函数吧！int Mix OpenAudio(int frequency, Uint16 for

2013-04-29 19:49:37 2775

JSP网页播放器 （调用WMP）

线性规划与网络流24题

空空如也

JSP网页播放器（调用WMP）