niuox-CSDN博客

原创 LA 4255 Guess

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2256题意：给定一串数字a1,a2....an，给出sij的正负数值。sij代表ai+...aj的大小。求一组结果满足此条件。-10思路：设：Bi = a1+ a2 +

2013-10-12 17:31:05 3847

原创欧拉回路

1.无向图的欧拉回路判断：如果一个无向图是连通的，并且每个点的度是偶数，那么这个无向图具有欧拉回路，所以无向图的欧拉回路判断是非常简单的，只需要一次BFS就可以搞定了。练习：Hdu 1878 欧拉回路题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1878#include #include #include #include

2013-09-29 18:10:29 10565

原创 C++ Factory & AbstractFactory 模式

1.工厂模式（Factory）：Factory模式是为一类对象提供创建接口或延迟对象的创建到子类中实现#include using namespace std;//抽象类class Product { public: virtual ~Product() =0;protected: Product();private:};class Concr

2013-09-21 21:07:19 4658

原创 C++ Singleton模式

Singleton(单例)模式是设计模式中最简单的模式。顾名思义，Singleton就是确保一个类只有唯一的一个实例。Singleton主要用于对象的创建，这意味着，如果某个类采用了Singleton模式，则在这个类被创建后，它将有且仅有一个实例可供访问。很多时候我们都会需要Singleton模式，最常见的比如我们希望整个应用程序中只有一个连接数据库的Connection实例；又比如要求一个应

2013-09-19 15:39:53 2898

转载 python用httplib模块发送get和post请求

原文连接：http://www.01happy.com/python-httplib-get-and-post/在python中，模拟http客户端发送get和post请求，主要用httplib模块的功能。1、python发送GET请求我在本地建立一个测试环境，test.php的内容就是输出一句话：echo 'Old friends and old wines ar

2013-09-16 22:46:58 7532

转载 c++ hash_map 详细介绍

文章转自：http://yujiawei.iteye.com/blog/409774为什么需要hash_map 用过map吧？map提供一个很常用的功能，那就是提供key-value的存储和查找功能。例如，我要记录一个人名和相应的存储，而且随时增加，要快速查找和修改：岳不群－华山派掌门人，人称君子剑张三丰－武当掌门人，太极拳创始人东方不败－第一高手，葵花宝典

2013-09-15 16:45:42 2771

原创操作系统的多道编程

近期，我亲爱的小伙伴们好像都在准备找工作，预祝他们找工作顺利！我这整天在实验室的伤不起。有一个小伙伴问了我一道操作系统的题目，大概如下：其实，乍看一眼，我也不会。。。可能是操作系统忘光了吧。复习了一下，知道这个题的题意其实是操作系统的多道编程：我做出的正确结果应该是23.47，也就是答案C分析过程：分析步骤：0-10分钟的时候，只有一个进程1在运行。单进

2013-09-14 10:40:09 5820 5

原创计词unigram和bigram的频次

在自然语言处理中，我们经常需要用到n元语法模型。其中，有关中文分词的一些概念是我们需要掌握的，譬如：unigram 一元分词，把句子分成一个一个的汉字bigram 二元分词，把句子从头到尾每两个字组成一个词语trigram 三元分词，把句子从头到尾每三个字组成一个词语.我们来简单的做个练习：输入的是断好词的文本，每个句子一行。统计词unigram和bigram的频次

2013-09-08 20:50:57 24177 3

原创 Sgu 128 Snake

题目连接：http://acm.sgu.ru/problem.php?contest=0&problem=128题意：给出n个点。给这n个点连线，使得满足：1.这n个点连线后形成的折线是闭合的。2.折线必须包含所有的n个点，且只能包含这n个点。3.折线中相邻线段要形成90度的转角。4.每条线段都必须是平行于坐标轴的，也就是说只能有x方向和y方向的线段。5.形成的线段不能自交

2013-09-08 10:06:57 3318

原创中文分词算法之最大正向匹配算法（Python版）

最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法，分为正向和逆向，原理都是一样的。正向最大匹配算法，故名思意，从左向右扫描寻找词的最大匹配。首先我们可以规定一个词的最大长度，每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配，如果没有找到，就缩短长度继续寻找，直到找到或者成为单字。实例：S1="计算语言学课程是三个课时" ,设定最大词长MaxLen = 5 ,S2

2013-09-06 17:33:18 14080 3

原创 Shell简易学习练习

1.Linux Shell入门Quiz 1 一个接受命令行参数的shell脚本任务编写一个shell脚本1.sh，这个脚本接受一个命令行参数，并把这个参数打印两次到标准输出。如果输入没有参数输入或者有多于一个参数输入，输出"error"。if [ $# != 1 ] ; then echo "error"else echo $1$1fiQuiz 2 生成时间相关文件

2013-09-03 21:05:02 4507 1

原创 Uva 10047 The Monocycle

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=988搜索题目。只不过把(x,y,d,c)作为一个结点。每个节点出发最多有三条边，分别对应前进、左转、右转。#include #include #include #include

2013-09-01 12:25:59 2458

原创 Poj 2187 Beauty Contest

题目链接：http://poj.org/problem?id=2187求平面上距离最远的两个点可以用旋转卡壳来做。如果qa，qb是凸包上最远两点，必然可以分别过qa，qb画出一对平行线。通过旋转这对平行线，我们可以让它和凸包上的一条边重合,如图中蓝色直线，可以注意到，qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点，计算这个

2013-08-29 11:23:41 2869

原创 Hoj 2468 GSM

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=2648有N块合金，每块合金的金银含量不同，现在知道N块合金融合后银的含量，求金的含量范围？若只有一种金属，假如有两块，其中一块10%，另一块20%，融合之后的范围(10%,20%)若有两种金属，假如有两块，其中一块金10%银30%，另一块金20%银40%，融合之后的范围金(10%,20%)，

2013-08-28 14:00:15 2346

原创 Hoj 3133 White-box testing

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=3133简单的搜索题。输出白盒测试的基本路径。注意题目中关于基本路径的定义。。。考虑到有可能（不知有没有可能）标号和数量不符的情况，离散化一下。#include #include #include #include #include #include #include #in

2013-08-27 19:31:44 2479

原创 Hoj 3134 Xiaodai’s Budget Program

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=3134根据依赖关系可以建立很多颗树，组成一个森林。然后我们增加一个虚拟节点0，使0作为这些子树根节点的父亲。那么这些森林就组成了一颗以0为根的树。接下来我们要在树上建立背包方程：dp[s][i]代表以s为子树的情况花费了i元钱取得的最大重要度。dp[s][i] = max(dp[s]

2013-08-27 11:04:38 2455

原创 Poj 1364 King

题目链接：http://poj.org/problem?id=1364差分约束系统。注意增加一个超级节点保证联通性即可。#include #include #include #include #include #include #include #include using namespace std;#define Maxn 505#define Maxm 1

2013-08-23 20:05:47 2311

原创 Poj 1201 Intervals

题目链接：http://poj.org/problem?id=1201差分约束系统。我们用s[i]代表从[0,i]所含有的元素和在本题中，如果[a,b]中有c个元素，那么：s[b]-s[a-1]>=c,我们可以推得：s[a-1] - s[b] 同时，由于每一个值上最多只能含有一个元素，那么:s[i] - s[i-1]s[i] - s[i-1]>=0 推得：s[i-1

2013-08-23 17:22:08 3035 1

原创 Hoj 1789 Electricity

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=1789题目大意：在一个无向图中，删除某一个点所形成的最大连通分量数目是多少。我们知道，删除一个点某个图的连通分量增加，那么这个点是割点。我们用cutNum[u]保存u这个点所关联的连通分量的数目。其中的最大值加上原图中的连通分量的数目就是答案。注意边数如果是0的话，要特判一下，此时去

2013-08-22 20:37:45 2319

原创 Hoj 1961 Arctic Network/Hoj 2507 The Bug Sensor Problem

两道求最小生成树第K大（小）边的题目。一般这种题目都是一个原本的连通图分割成s个连通分量，求这些连通分量中最长边。那么这就是求原图中最小生成树中第s大的边的长度。因为连接这s个连通分量的边肯定要求是前s-1长的边，这些边有s-1个。第一题：Hoj 1961 Arctic Network题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=19

2013-08-22 09:46:55 2337

原创 Hoj 2632 Blanks in a Table

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=2632题意：设a代表非空，a'代表空。b代表非空，b'代表空。那么：有n个条件要求a和b不可同时为空，则：a->b',b->a'有p个条件要求a和b至少有一个为空，则：a'->b,b'->a#include #include #include #include #in

2013-08-21 20:22:14 775

原创 Hoj 1917 Peaceful Commission

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=19172-sat问题。如果a和b矛盾，那么a向b的反面连一条线。以此建立了一颗有向图，然后对此图求强连通分量后缩点，反向连线后形成一个DAG图。然后对此图求拓扑排序即可。#include #include #include #include #include #includ

2013-08-21 17:21:29 779

原创 Poj 1144 Network

题目：http://poj.org/problem?id=1144Tarjan无向图求割点。#include #include #include #include #include #include using namespace std;#define Maxn 105#define Maxm 10005struct Edge{ int a,b;}edge[

2013-08-21 17:14:29 695

原创 Hdu 3859 By Recognizing These Guys, We Find Social Networks Useful

题目链接；http://acm.hdu.edu.cn/showproblem.php?pid=3849无向图求割边（Tarjan）：#include #include #include #include #include #include #include #include #include #include using namespace std;#define

2013-08-20 21:35:23 926

原创 Hoj 1086 Don't Get Rooked

题目：http://acm.hit.edu.cn/hoj/problem/view?id=1086本题数据范围较小，可以暴力搜索过。如果数据范围大一些的话，可以使用二分图。先以行考虑，每行中，没有墙分割的点集合为一块。这样扫描后会形成rNum块。再以列考虑，每列中，没有墙分割的点集合为一块。这样扫描后会形成cNum块。然后如果行块与列块之间为二分图的左右部分，如果两者之间有个公

2013-08-20 21:19:48 766

原创 Hoj 1520 The Bottom of a Graph/Poj 2186 Popular Cows/Poj 1904 King's Quest

这几题练习强连通分量的Tarjan求法：在一个有向图中，如果两个点a,b之间存在a->b的路径以及b->a的路径，则称a与b在同一强联通分量（SCC，strongly connected component）之中。因此可以将图划分为几个子图，每一个子图中都是一个极大强联通分量。如果将所有的强连通分量都缩成一个点，原图就变成了一个DAG（有向无环图）。可以用Tarjan算法、Kosara

2013-08-20 08:50:52 803

原创概率DP问题整理（一）

第一题：Hdu 3853 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853简单概率DP题。注意思维逆过来考虑。#include #include #include #include #include #include #include #include using namespace std;#define Ma

2013-08-15 16:21:55 2480

原创数位DP问题整理（一）

第一题：Amount of degrees (ural 1057)题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1057题意：[x,y]范围内的数，可以拆分成k个b进制的不同幂的和的数字有多少。我们可以将x转换成二进制来讨论。那么问题就变成了求[0,x]范围内，二进制表示中含有k个1的数字有多少个。求[x,y]区间相减。我们可

2013-08-13 23:11:11 20711 1

原创 Hoj 3040 Team Mate

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=3040题意：给定一串长度为n的数，求任意几个数的组合和能否是n的倍数。只要求输出其中一种情况即可。这题正解应该是用抽屉原理：依次求出前缀和s[i]，那么前缀和相等的s[i]和s[j]之间的数的和就是n的倍数。即(i,j]#include #include #include #inclu

2013-08-12 10:55:17 889

原创 Hoj 2060 Fibonacci Problem Again

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=2060题意：求Fibs和。f[n] = f[n-1] + f[n-2]。使用矩阵乘法很容易求出f[n] = [0 1 1 1]这个矩阵的n-1次方，然后这个二维矩阵的左下角和右下角的数值相加即可。对于本题，我们要求sigma(f[i]) ,0则，我们可

2013-08-11 20:06:03 707

原创 HYSBZ 1878HH的项链

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1878题意：给定一段区间，长度问N，查询某一区间内数值不同的数的个数，共有M个查询。数据范围：N ≤ 50000，M ≤ 200000。这个题的解法并非对每个答案直接查询，而是对询问排序后回答。记一个数组B，起初，对于每个颜色第一次出现的i，B[i]=1。这时，对于左端点

2013-08-08 18:56:41 776

原创 Poj 2778 DNA Sequence

题目链接：http://poj.org/problem?id=2778题目类型：AC自动机 + 矩阵快速幂+ DP题意:给定一些病毒的模式串，问给定的长度为N的所有DNA串中有多少是不含有病毒串的。数据范围N最大为2000000000这道题的解题思路可以参考：http://blog.henix.info/blog/poj-2778-aho-corasick-dp.html和：h

2013-08-06 20:08:12 790

原创 Hdu 4391 Paint The Wall

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4391给出一个长度为n(n 1、C l r z 将[l, r]区间内所有点的颜色标为z。2、Q l r z 查询[l, r]区间内颜色为z的点的数目。本题可以用线段树+剪枝优化做。#include #include #include #include

2013-08-05 11:41:59 1027

原创 Hdu 3887 Counting Offspring \ Poj 3321 Apple Tree \BZOJ 1103 [POI2007]大都市meg

这几个题练习DFS序。问题引入：给定一颗n(n 1、C x y 以节点x的权值修改为y。2、Q x 求出以节点x为根的子树权值和。最直观的做法，枚举一个子树内所有节点的权值加和。但这种做法的每一次讯问的时间复杂度是O(n)的，很明显无法满足题目的需要，我们需要更优的解法。第一题：http://acm.hdu.edu.cn/showpro

2013-08-03 18:57:16 1490

原创 Poj 3667 Hotel

题目链接：http://poj.org/problem?id=3667本题也是线段树区间合并问题。和上一题LCIS类似。题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边2 a b:将[a,a+b-1]的房间清空思路:记录区间中最长的空房间#include #include #include using namespace std;#define

2013-08-01 15:48:41 633

原创 Hdu 3308 LCIS

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308题意：一串数字，可以修改某一个位置的值，无限定查询，查询某一区间内的最长单调递增字串（是子串，而不是子序列；字串是连续的，子序列不需要连续）的长度。为了求区间内的最长单调递增子串的长度，我们除了用midGo[]数组维护某一区间内的最长单调递增字串的长度外，还需要开辟两个数组leftGo[]

2013-08-01 13:16:38 895

原创 Poj 2828 Buy Tickets \ Zoj 3635 Cinema in Akiba

这两道题思路是一样的。第一题：http://poj.org/problem?id=2828题意：依次插入人，每个人插入的地方告知，求最终的排位。乍看用链表来做即可，可是这样肯定会超时，不信试试：#include #include #include using namespace std;struct People{ int val; People() {

2013-08-01 12:51:54 762

原创 HOJ1119/HDU1542 Atlantis HOJ1909/POJ1177 Picture

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1542题意：求多个长方形在平面上所覆盖的面积和。扫描线。从下往上扫描，浮点数离散化处理。思路参考：http://www.cnblogs.com/scau20110726/archive/2013/03/21/2972808.html#include #include #include

2013-08-01 10:56:40 1270

原创 Poj 3225 Help with Intervals

题目链接：http://poj.org/problem?id=3225题意：题意大概是说原始的空集合S，经过U（并集操作）、I（交集操作）、D（相减操作）、C（反向相减操作）、S（异或操作）后，所形成的集合是什么。思路:我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含)U:把区间[l,r]覆盖成1I:把[-∞,l)(r,∞]覆盖成0D:

2013-07-31 10:39:54 1664

原创 Uva 11806 Cheerleaders

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2906本题我本来想逐步分类四个角的情况。但是发现分类之间是没有重复的，而内部是有重复的。错误代码如下。#include #include #include #include

2013-07-22 21:58:21 1086 2

HIT ACM 1004题源码

空空如也