由于个人原因，该博客停止更新。后续相关文章更新传送门：http://blog.csdn.net/whereisherofrom英雄哪里出来2017-12-26 13:24发表评论 ...继续阅读 (13)

摘要: 一、套接字 1、什么是套接字（socket） 2、创建套接字 1) 协议族（Protocol Family） ... 阅读全文英雄哪里出来2017-12-20 20:36发表评论 ...继续阅读 (15)

     摘要: 目录一、深度优先搜索      1、DFS      2、基于DFS的记忆化搜索         3、基于DFS的剪枝            1) 可行性剪枝        &nb...  阅读全文英雄哪里出来2015-10-09 22:28发表评论 ...继续阅读 (44)

150 Mr. Beetle II枚举151 Construct a triangle解析几何152 Making round贪心153 Playing With Matches博弈 + 规律154 Factorial初等数论155 Cartesian TreeRMQ156 Strange Graph欧拉回路157 Patience模拟打表158 Commuter Train二分枚举159 Self-Replicating Numbers深度优先搜索150 Mr. Beetle II枚举题意：给定两个二维坐标上的点(x1, y1)、(x2, y2)，坐标范围为[-106, 106]。求从一个点(x1, y1)到(x2, y2)的直线路径上经过的第N个方格的左下角坐标，无解输出no solution。图1题解：首先，如果两个点的x坐标相同或者y坐标相同，则直接无解；否则将(x1, y1)和(x2, y2)一起做相应的平移，使得(x1, y1)和(0, 0)重合，方便计算。如果x1 < x2，枚举x坐标属于(x1, x2]，对于每个单位为1的区间[x, x+1]容易计算出y方向上有多少个方格，统计出第n个方格；如果x1 > x2，枚举x坐标属于(x2, x1]，用同样的方法进行计算。151Construct a triangle解析几何题意：给定三角形的两条边AB = c、AC = ...继续阅读 (31)

A. PeriodPKU 1961http://poj.org/problem?id=1961题意：给定一个长度为N(N <= 106)的字符串S，求它的所有前缀中能够表示成AK的前缀，并且要求求出每个前缀对应的K。题解：KMP利用KMP求出该串的Next数组，然后枚举每个前缀，根据Next数组的定义，对于某个前缀S[1...i]，有S[1...Next[i]] = S[i-Next[i]+1...i]，假设前缀S[1...i]能够表示长AK的形式，则A = S[Next[i]+1...i]，所以必须满足i能够被i - Next[i]整除，满足条件后K = i/( i - Next[i])。B. Corporative NetworkPKU 1962http://poj.org/problem?id=1962题意：给定N(N <= 20000)个点和M(M <= 200000)次操作，每次操作有两种类型：I a b将a的父结点设为b，并且合并距离为|a-b| mod 1000E a询问a到根结点的合并距离。题解：并查集利用路径压缩的思想，用dist[p]表示p和p的父结点的合并距离，每次查询的时候累加p到根结点的合并距离，并且将p到p所在树的根结点R的路径上的所有点的父结点都设为R，然后更新各自的合并距离。合并操作O(1)，查询操作总复杂度O(N)。C. Cave Explorat ...继续阅读 (41)

A . The Hardest Problem EverPKU 1298http://poj.org/problem?id=1298题意：解码题，按照如下对应关系解码：密文A B C D E F G H I J K L M N O P Q R S T U V W X Y Z原文V W X Y Z A B C D E F G H I J K L M N O P Q R S T U题解：简单题。B. Polar ExplorerPKU 1299http://poj.org/problem?id=1299题意：给定圆的半径X，求圆周上两个点A和B的距离，其中圆心角AOB的角度为Z(0 <= Z <= 360)。题解：核心是Z如果大于180，则Z = 360 - Z，即走劣弧。而且题目求的是来回一次，所以计算的时候弧长要乘2。C. Door ManPKU 1300http://poj.org/problem?id=1300题意：给定一些边和起点s，求能否找到一条从s到0的通路，并且要求访问所有的边。题解：欧拉回路可行解判定。首先利用flood fill从s遍历全图，如果0点没有被访问到则必定不存在；然后判断度数不为0的点是否有未被访问到的，如果有，说明图不连通，也必定不存在解；最后统计度数为奇数的点的个数P，以及具体的点：1) P = 0，则必定有解；2) P > 2，则无解；3) ...继续阅读 (33)

A.Artificial Intelligence?PKU2256http://poj.org/problem?id=2256题意：功率的计算公式为P = UI，给定一句话，这句话中一定会包含三个变量中的两个，求另外一个，并且单位会有三种前缀m(毫)，k(千)，M(兆)。题解：字符串扫描。gets读入字符串，进行一次遍历，查找是否包含子串’P=’,‘U=’,‘I=’, 格式化它后面的数字，需要用double来存，然后检查单位前缀，m需要将原值除上103，k需要将原值乘上103，M需要将原值常上106。然后分三种情况计算未知的那个值即可。B. Balancing Bank AccountsPKU 2257http://poj.org/problem?id=2257题意：给定N(N <= 20)个人，以及M(M <= 1000)条关系，每条关系的描述为nameA nameB C，表示nameA这个人给了nameB这个人C块钱，为了让所有人都不亏，需要再给出至多N-1条关系，使得所有人都收支平衡。题解：贪心。首先将所有人分成两堆，from_set表示收入大于支出的人的集合，to_set表示支出大于收入的人的集合，并且记录他们各自的 |收入-支出|，然后对于所有的from_set的人按 |收入-支出| 进行递增排序，枚 ...继续阅读 (31)

摘要: AC自动机 算法目的： AC自动机主要用于解决多模式串的匹配问题，是字典树(trie树)的变种，一种伪树形结构(主体是树形的，但是由于加入了失败指针，使得它变成了一个有向图)；trie图(我的理解^_^)是对AC自动机的一种改造，使得图中每个结点都...阅读全文英雄哪里出来2014-07-10 14:26发表评论 ...继续阅读 (47)

摘要: 140 Integer Sequences 数论：扩展欧几里得141 Jumping Joe &n...;阅读全文英雄哪里出来2014-07-06 13:00发表评论 ...继续阅读 (42)

A. ConstellationsPKU 3690http://poj.org/problem?id=3690题意：给定N*M(N<=1000, M <= 1000)的01矩阵S，再给定T(T <= 100)个P*Q(P <= 50, Q <= 50)的01矩阵，问P*Q的矩阵中有多少个是S的子矩阵。题解：位压缩+ KMP由于P <= 50，所以我们可以把所有P*Q的矩阵进行二进制位压缩，将P*Q的矩阵的每一列压缩成一个64位整数，这样P*Q的矩阵就变成了一个长度为Q的整数序列，用同样的方式对N*M的矩阵进行压缩，总共可以产生(N-P+1)个长度为M的整数序列，剩下的就是进行最多(N-P+1)次KMP匹配了。KMP相关算法可以参阅：http://www.cppblog.com/menjitianya/archive/2014/06/20/207354.html图1 ‘*’代表二进制的1, ’0’代表二进制的0B. DNA repairPKU 3691http://poj.org/problem?id=3691题意：给定N(N <= 50)个长度不超过20的模式串，再给定一个长度为M(M <= 1000)的目标串S，求在目标串S上最少改变多少字符，可以使得它不包含任何的模式串（所有串只有ACGT四种字符）。题解：AC自动机+动态规划利用 ...继续阅读 (34)

摘要: RMQ 定义： A[0...n-1]  ...;阅读全文英雄哪里出来2014-06-26 16:35发表评论 ...继续阅读 (29)

摘要: 130 Circle &n...;阅读全文英雄哪里出来2014-06-23 19:08发表评论 ...继续阅读 (18)

KMPKMP算法可以说所有数据结构书上都有，上大学的时候也陆陆续续学过三次，每次学完看似理解了，可是过了不到半年又忘记了，或许是因为代码太短，能写出来就以为自己会了，没有深入去理解，导致下次再来看的时候感觉很陌生，一定是这样的。今天看了matrix67对KMP的解释，很赞，附上地址：http://www.matrix67.com/blog/archives/115为了让老年的自己不用在迟暮的时候再学一遍KMP，还是决定把一些关键性的东西记录下来，如果那时候的自己看到自己当年写的这篇笔记能有恍然大悟的感觉，那么现在就不是在浪费时间了。定义：S[1... n] 目标串 T[1...m] 模式串算法目的：从目标串S中找到一个子串和模式串T完全匹配。算法核心思想：1) 枚举i从1到n，在S[i-j...i-1]和T[1...j]完全匹配的前提下，判断S[i]是否和T[j+1]相等：a) 如果相等，说明S[i-j...i]和T[1...j+1]完全匹配，那么i和j都自增1；b) 如果不相等，则需要找到一个最大的j' < j，满足S[i-j'...i-1]和T[1...j']完全匹配；2) 当i=n或j=m的时候说明匹配结束，否则重复1)；对于j'可以这样理解，由于前提是S[i-j...i-1]和T[1...j]完全匹配，如果要找到一 ...继续阅读 (32)

120 Archipelago计算几何：射线旋转121Bridges painting图论：染色问题122 The Book图论：哈密尔顿回路123 The Sum递推124 Broken Line计算几何：线段判交125 shtirlits搜索：深度优先搜索126 boxes初等数论127 Telephone directory排序128 Snake排序 + HASH129 Inheritance计算几何：凸包+线段判交120 Archipelago计算几何：射线旋转题意：需要求一个正多边形的N个点，但是给出的只有N和某两个点的坐标。题解：核心思想是根据给定的那两个点的坐标确定多边形中心点的坐标，这样边长也确定了，然后利用中心点到其中一个点的射线的旋转求出所有的点坐标。1)正多边形的中心点一定在任意两个顶点的连线的中垂线上，然后根据已知点的相对关系，算出他们和中心点的夹角，利用这两个条件就可以求出中心点的坐标了。2)然后就是要求某个点绕中心点旋转360/N度后的坐标了，做N-1次旋转操作就能求出所有的顶点了。旋转可以通过解方程求解：令原单位向量I，旋转alpha角度后的单位向量Ia，其中I和alpha已知，Ix是我们需要求的。那么有以下两个方程：1) I.x * Ia.x + I.y * Ia.y = cos( alpha )2) Ia.x2+ Ia.y2= 1将1)中的Ia.x ...继续阅读 (57)

110 Dungeon计算几何：射线和球体相交111 Very simple problem二分枚举112 a^b-b^a二分求幂113 Nearly prime numbers数论：素数筛选114 Telecasting station枚举115 Calendar简单模拟116 Index of super-prime动态规划：记忆化搜索117 Counting二分求幂118 Digital Root数学题119 Magic Pairs数论：扩展欧几里得110 Dungeon计算几何：射线和球体相交题意：给定一条3D射线和N个球体，问射线的各种反弹经过的球体编号，如果反射超过10次，只需要输出前十次。题解：很明显，首先需要枚举每个球体和当前射线的相交情况，如果和多个球体相交肯定是取距离最近的球体进行相交计算，然后计算出空间反射射线，重复以上操作11次，如果某次的反射射线已经不能和任何球体相交那么直接跳出这个过程。图11)射线和球体相交如图1，表示射线AB和球O相交于B点，反射后的射线为BC，BD为球心O到交点的延长线，那么必定满足以下几个条件：已知A点坐标(xa, ya, za)，单位向量tabB点坐标为(xb, yb, zb) = (xa, ya, za) + |AB| * tab(1)B点在球O上，所以B点坐标满足| (xb, yb, zb) - (xo, yo, zo ...继续阅读 (71)

摘要: 100 A+B 测试题101 Domino &nbs...;阅读全文英雄哪里出来2014-06-10 13:43发表评论 ...继续阅读 (32)

摘要: 高斯消元算法目的： 高斯消元，一般用于求解线性方程组AX = B（或 模线性方程组AX mod P = B），以四个未知数，四个方程为例，AX=B表示成4x4的矩 ...阅读全文英雄哪里出来2014-06-08 19:55发表评论 ...继续阅读 (37)

A . JohnPKU 3480http://poj.org/problem?id=3480题意：N堆石子，两人轮流从其中一堆中取任意石子，最后一个取完石子的人输。题解：博弈。1)当所有石子的SG值异或和不等于0时：a) 个数大于1的堆数=0，必定是奇数个1，所以先手必输；b) 个数大于1的堆数=1，总能想办法将局面变成奇数个1，所以先手必胜；c) 个数大于1的堆数>1，总能取掉某些石子，使得所有石子的SG值异或和为0，并且个数大于1的堆数至少还剩两堆；2) 当所有石子的SG值异或和等于0时：a)个数大于1的堆数=0，必定是偶数个1，先手必胜；b)个数大于1的堆数=1（不存在）；c)个数大于1的堆数>1，无论怎么取，SG值异或和都不可能为0。并且无论先手怎么移，后手可以要么进入偶数个1的状态，要么保持SG值和为0并且非全1的状态（该状态先手必输），所以这种情况，先手必败。由于1) 的c)情况可以到达2的c)情况，所以1的c)情况为先手必胜点。B . Double QueuePKU 3481http://poj.org/problem?id=3481题意：给定一些数据(K,P)和一些询问，K为数据值，P为优先级，每次询问输出当前优先级最高或者最低的数据的K的值，询问完删除这个数据。题解：平衡树。可以用SLT的set(内部也是平衡树的实现)水过去。C .‘JBC’ ...继续阅读 (23)

A.Nth Largest ValuePKU 3781http://poj.org/problem?id=3781水题，求10个数中第3大的数。B.Equal Sum PartitionsPKU 3782http://poj.org/problem?id=3782题意：给定一个M(M <= 10000)个元素的序列，将它切割成K块，每块的和相等，求最大的K。题解：枚举。首先，切成K块，每块和相等，那么这个和必定是M个元素总和的一个因子，那么可以枚举第一个块的长度（M种），判断当前块的和是否能被所有数的总和整除，如果可以，顺序判断可行性，看似复杂度是O(M^2)，但是能否整除这个剪枝可以筛选掉绝大部分情况。C.BallsPKU 3783http://poj.org/problem?id=3783题意：给定B (B <= 50)个一样的球，从M (M <= 1000)层楼上一个一个往下扔，存在某个楼层K，使得低于它的楼层往下扔球，球不会碎，在第K层扔下去会碎。求最坏情况下，需要扔几次才能确定这个K。题解：动态规划。令DP[i][j]表示总楼层为i，持有j个球时，最坏情况需要的次数；那么如果从k ( 1 <= k <= i)层进行扔球，有两种情况：1)如果球不碎，则还需要进行DP[i-k][j]次测试（向更高的楼层进发）；2)如果球碎，那么还可以进行的次数为DP[k-1][j-1]（损失 ...继续阅读 (47)

A. Up and DownPKU 3912http://poj.org/problem?id=3912题意：给定一个一维的棋盘，范围为[0, W] (W <= 1000,000,000)，某两个点之间有梯子或虫洞，梯子的下端点到上端点以及虫洞的上端点到下端点花费的步数为0，其它任意点之间的距离通过跳跃来计算，最多每次跳跃不超过S格（S<= 6），跳跃的过程中如果跳到梯子的下端点或者虫洞的上端点就会被直接传送到另一端，并且每次跳跃只能从小的点跳到大的点（虫洞是个例外），求从0到W的最短距离。图A-1题解：离散化+ SPFA。将所有梯子和虫洞的两端点、0和W以及他们往前往后S步以内的数全部记录下来，梯子和虫洞有P（P <= 40）个，加上起点终点，总共82个点，算上前后各六步，总共82 * 13 = 1066个点，然后将这些点排序后离散化，最后就是要构建一个网络图，通过网络求0到W的最短路，最短路可以用SPFA求解。谈谈建图的过程，对于任意两个点，他们之间必定可以连一条边，然后有一个步数表示边的权值（这里的步数也可能是正无穷，也即永远都无法到达）。对于任意两个点(u, v)，他们的步数w(u, v)（边权）我们做如下讨论（这里的u、v是离散化后的点）：1）如果u是梯子的下端点，v是梯子的上端点或者u是虫洞的上端点，v是虫洞的下端点，那么w(u, v) = 0，否则进入2)的判断;2） ...继续阅读 (43)

A．Grandpa's Rubik CubePKU 1290http://poj.org/problem?id=1290题意：给定一个3X3的六面魔方（每个面有3X3个块），求经过某些旋转之后能否使得所有面的颜色都相同，旋转包括对某个面进行顺时针和逆时针旋转（共12种情况）。图A-1如图1，输入数据为左图的形式，右图给对应的面编号，箭头方向为顺时针旋转方向。+A表示对A这个面进行一次顺时针旋转，-B表示对B这个面进行一次逆时针旋转。问经过一定的+A/-B操作之后能否使得所有面的3X3个字母都相同。题解：模拟题做法很多，这里介绍一种比较容易理解的状态记录方式，考虑某次旋转，一定是旋转某个面，然后对邻接的四个面的某条边进行顺次平移。如图A-2, 2号面的旋转带动的是1、5、3、6四个面。图A-2我用一个数组rotate_n来记录某个面旋转的时候带动的面的编号集合（编号为0的数据为占位符），那么有：int rotate_n [7][4] = {{0, 0, 0, 0}, {4, 5, 2, 6}, {1, 5, 3, 6}, {2, 5, 4, 6}, {3, 5, 1, 6}, {1, 4, 3, 2}, {1, 2, 3, 4}};光记录带动的面是哪些还不够，还需要知道带动面的对应边，对于一个魔方的一个面，我们编号如下：（0,0）（0,1）（0,2）（1,0）（1,1）（1,2）（2 ...继续阅读 (44)

【开发信息】本游戏是采用Python的Pygame包开发而成，游戏的模式是射击类型，同时添加了RPG游戏特有的情节模式。【版本信息】v1.00【游戏简介】游戏的主要操作是键盘，但是在确认的时候也可以采用鼠标，鼠标还可以进行人物菜单栏的Tip的查看，主角主要有生命、魔法、灵魂、攻击力、防御力、速度等几项属性。生命值 传说中的血，中国古代角色扮演游戏里大多将它称为“精”。查克拉 中国古代游戏中所谓的内力，小时候智力卡游戏中的MP，决定你进行攻击时候同时释放的武器数目。灵魂 每次生命值达到负值的时候可以通过释放一个灵魂来将血补满。攻击力 主角自身攻击力和当前武器攻击力的总和，影响对敌人的伤害值。防御力 主角的自身防御，影响主角受到攻击时的伤害值。速度 决定主角的移动速度和闪避率。必杀技 可以作用于整个游戏世界的无敌必杀技，可以理解为“大招”。得分 每打到敌人一次可记一分，打死敌人记三分。当得分积满2000的时候可以换赎一个灵魂。【游戏操作】方向键 控制人物行走左Ctrl键 发射子弹 + 确认操作空格键 释放大招（必杀技）【几点说明】本游戏部分资源取自网络，部分由作者原创，所以请勿将其用于商业用途，否则后果自负。【试玩链接】http://code ...继续阅读 (43)

Tetrix v1.01 版本下载地址：http://code.google.com/p/sguzty/downloads/detail?name=Tetrix%20v1.01%20Release.rar&can;=2&q;=Bug 修正1.最大的bug是方块掉落的时候会将镂空的格子填满，修改之。2."方块"旋转的时候不应该有任何效果，先前的版本会改变位置。3.先前版本长条的旋转比较难看，这次略微好看一点。4.修改了之前Life和Speed的显示问题。功能 新增1.添加了背景音乐和音效。2.征询网友意见添加了随机种子，每次打开后都会有不同的开局。背景音乐是 智冠电子 的 单机游戏 <天龙八部> 中 某个场景的背景音乐。以此怀念我们儿时的单机游戏时代。并且多谢众多网友们提的意见,你们的支持是我们最大的动力。以下是其中一种在游戏中添加背景音乐的方法，拿出来分享以下，如果直接采用sndPlaySound是不能达到混音效果的，采用以下方法可以播放背景音乐，然后用sndPlaySound在播放音效，就可以达到混音效果。Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/voidBeginMusic(){CoInitialize( NULL );}class ...继续阅读 (45)

摘要: 昨天看到百度之星的趣味赛的帖子，很多代码挺有意思的，于是想在控制台下写个简洁点的小游戏，想想还是写个最经典的游戏------俄罗斯方块 吧。睡觉的时候构思了下大致的情况，今天早起开始写，遇到最大的困难是键盘按键的问题，本来想开一个线程，然后让系统读getch()，但是getch和ReadConsoleInput函数一样，是同步的，没有输入的状态下会...阅读全文英雄哪里出来2011-05-26 13:40发表评论 ...继续阅读 (45)

摘要: Pygame游戏开发之五 小试牛刀 大部分游戏都会对图像文件进行加密，这样你就很难看到它的图片信息，游戏就更加添加了神秘感。有加密自然有解密，所谓山外青山楼外楼，再高的加密手段都可以被破解，加密只是提高技术门槛，让一部分人看不到你的图片资源。 在进行加密之前，让我们首先把文件的结构组织一下，用文件夹来管理各类文件。 root/ ...阅读全文英雄哪里出来2011-05-01 16:40发表评论 ...继续阅读 (40)

Pygame游戏开发之四初学乍练Pygame中除了Group这个Sprite的容器类，还有一些继承自Group的容器类，它们分别是RenderUpdates、OrderedUpdates、LayeredUpdates、LayeredDirty。pygame.sprite.RenderUpdates继承自pygame.sprite.Group，它相对于Group的不同点就是重写了Group的draw函数，原型是：RenderUpdates.draw(surface) : return Rect_list它将所有它包含的Sprites绘制到surface上，和Group.draw一样。但是这个函数返回了一系列的屏幕上发生改变的矩形列表，这个矩形列表应该被传递到pygame.display.update中去。pygame.sprite.OrderedUpdates继承自pygame.sprite.RenderUpdates，它绘制Sprite的时候是以Sprite被添加时的顺序来绘制的。pygame.sprite. LayeredUpdates绘制的方式和pygame.sprite.OrderedUpdates类似，只是它引入了图层的概念。你可以通过'default_layer'设置默认图层，或者一个整数来表示图层。如果添加的Sprite自己有一个layer的图层属性那么就是用这个，否则 ...继续阅读 (48)

摘要: Pygame游戏开发之三 初出茅庐 Pygame中除了Sprite，还有一个DirtySprite，它是由Sprite派生出来的绘制效率更高的精灵，较之Sprite多了以下几个属性：dirty = 1 如果设为1，则进行...阅读全文英雄哪里出来2011-04-26 01:07发表评论 ...继续阅读 (24)

摘要: Pygame游戏开发之二 初窥门径 游戏中需要用到很多对象，比如人物、野怪、建筑物、UI控件等等，他们的行为不尽相同，但是总有那么些共同点，如果将所有的东西都封装成各自的类难免会写上很多重复的代码，因为两个对象如果具有相同的行为（比如人物和野怪都可以行走）如果写两个move()函数，以后改起来就要修改两个地方，不容易维护而且扩展很麻烦，但是人物和野怪又有其它不相同的行为，比如技能之类的不同...阅读全文英雄哪里出来2011-04-24 19:55发表评论 ...继续阅读 (54)

摘要: Pygame游戏开发之一 初涉红尘 本人是个游戏爱好者，同样是个游戏开发爱好者，最近开始学习Pygame，Pygame是 跨平台的 Python模块（包括Win32、Unix、Mac、Android等等），主要包含图像和声音，专为电子游戏设计。所有需要的游戏功能和理念都完全简化为游戏逻辑本身，这样就大大提高了开发效率。 ...阅读全文英雄哪里出来2011-04-23 20:39发表评论 ...继续阅读 (46)

摘要: 题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2984 /**//*题意： 给出一个长度为N(N <= 1000000)的串，要求求出所有串的不重复排列的方案。输出方案数的最后一个非零位。题解： 组...阅读全文英雄哪里出来2011-04-15 14:19发表评论 ...继续阅读 (30)