- 博客(159)
- 收藏
- 关注
RSS订阅原创 2017中国大学生程序设计竞赛 - 女生专场
1.HDU-6023点我看题(此链接为vjudge链接题意：给出题目的数量，提交的次数，每次提交的题目编号，提交时间以及结果，其中罚时为每次错误提交20min+第一次成功提交的时间，问最后AC的题目数量以及总罚时。提交结果不存在CE。分析：水题，直接计算。参考代码：#include#include#include#include#include#include#
2018-05-10 10:00:46
495
原创 字符串之KMP详解
昨晚梳理了一下KMP的过程，感觉印象深刻了不少，在此写下博客加深印象，同时也希望能和大家交流。KMP这个名字来源于其三个创始人名字首字母，主要用于解决字符串的匹配问题。字符串的匹配问题：假设有两个字符串S和T，问串T是否出现在串S中/串T在串S中出现了多少次。(假设串S的长度为n，串T的长度为m)常规思路：按照我们正常的想法，肯定是用T跟S的每一位一一匹配，一旦遇到不能匹配的时候，就将正在匹配的起...
2018-03-10 11:34:54
772
原创 剑指offer——二叉搜索树与双向链表
题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。分析：这个题本质上其实是对二叉搜索树的中序遍历，但是要对结点的指针稍作改动。1.先遍历左子树，将其构造成双链表，并返回链表的‘根’结点；2.得到左子树双链表的最后一个结点；3.如果左子树不为空，将当前根结点追加到左子树链表后；4.遍历右子树，将其构造成双链表，并返回链表的‘根...
2018-03-05 10:48:22
263
原创 剑指offer——包含min函数的栈
题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析：定义一个辅助栈，保存对应元素存在时当前栈中的最小元素，即可在O(1)的时间内找到最小的数。参考代码：class Solution {public: void push(int value) { if(s_data.empty()){ s_data.push(val...
2018-02-25 14:38:13
193
原创 剑指offer——数组中出现次数超过一半的数字
题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。分析： 第一种思路，把序列从小到大排个序，然后相同的数字一定是连续的，记录连续数的个数，判断其长度。时间复杂度为O(nlog(n))，时间主要用在排序上。参考代码：c...
2018-02-22 20:52:57
207
原创 剑指offer——重建二叉树
题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。分析：先搞清楚二叉树的四种遍历方式（先序遍历：根左右；中序遍历：左根右;后序遍历：左右根；层析遍历：由根往下一层一层的遍历），然后这个题的题意很明显，就是...
2018-02-19 22:16:20
184
原创 POJ - 1001 Exponentiation(浮点数高精度乘法)
POJ 1001 DescriptionProblems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems. This problem requires that you
2017-12-29 20:17:08
474
原创 剑指offer——不用加减乘除做加法
题意：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。分析：之前自己手动yy了一下，直接用二进制进行位运算，然后没考虑负数，直接WA，接着仔细分析，数分四种情况(a>0,b>0;a>=0,b0;a参考代码：class Solution {public: int Add(int num1, int num2) { int a
2017-12-28 17:43:45
207
原创 HDU - 3294 Girls' research(manacher)
Problem DescriptionOne day, sailormoon girls are so delighted that they intend to research about palindromic strings. Operation contains two steps:First step: girls will write a long string (only contains lower case) on the paper. For example, "abcde", b
2017-12-02 20:32:59
236
原创 HDU - 3068 最长回文(manacher模板题)
点我看题题意：求给定的一串字符串中最长的回文子串。分析：manacher(马拉车模板题。推荐学习博客：https://www.cnblogs.com/grandyang/p/4475985.html参考代码:#include#include#include#include#includeusing namespace std;#define INF 0x3f3
2017-12-01 22:24:25
204
原创 HDU - 2896病毒侵袭(AC自动机)
Problem Description当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。万事开头难，小t收集了好多病毒
2017-11-29 20:23:20
182
原创 AC自动机模板
昨天晚上来基地看了看AC自动机，大概知道是怎么回事了，敲了一遍kuangbin的模板，还是可以理解的，下面就是对其模板的解析。/*求目标串中出现了多少个模式串*/#include#include#include#include#include#includeusing namespace std;const int maxn = 1e4+10;const int maxl
2017-11-25 16:14:02
210
原创 POJ - 2752 Seek the Name, Seek the Fame(KMP)
DescriptionThe little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring
2017-11-22 23:02:23
249
原创 POJ - 1961 Period(KMP)
DescriptionFor each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K >
2017-11-22 22:03:17
212
原创 POJ - 3461 Oulipo(KMP)
DescriptionThe French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book:Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’a
2017-11-22 21:40:04
172
原创 Chapter one 浏览器生成消息——探索浏览器内部
大三了，这两年多试着去接触了各种东西，也摸索过一些学习方法，最后还是想回归到书本，想多看看书。以上。Begin其实在看《网络是怎样连接的》这本书之前，也把编程珠玑过了一遍，才发现，耐心一点兴趣或许就被培养出来了呢，所以出于对网络的兴趣，再加上想把网络方面的知识理一理，就开看了这本书，讲的通俗易懂，条理清晰。好吧，开始讲讲看完Chapter one之后学到了什么吧。Chapter
2017-11-12 23:07:01
295
原创 Prim和Kruskal求最小生成树
前两天TCP/IP协议课上,老师谈到图论中的几个简单算法,发现自己不是很熟练,所以马上挂了一套MST的题目来练练手,题目很简单,但由于课程比较多,所以还有三个题没来得及刷,同时在此%一波典假设给出了一个图G首先是Prim算法,基于贪心的思想,任选一个点形成一棵树,然后不断的从剩下的点中挑出距离这棵树中任意一个点距离最小的点,不断的重复这个操作,直到n个点都加入到树中形成最小生成树.时间复杂
2017-11-02 21:14:22
732
原创 HDU - 5618 Jam's problem again(cdq分治和整体二分)
Problem DescriptionJam like to solve the problem which on the 3D-axis,given N(1≤N≤100000) points (x,y,z)(1≤x,y,z≤100000)If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1Ask for the each level of the point.
2017-10-17 19:54:16
220
原创 HDU - 5572 An Easy Physics Problem(计算几何)
Problem DescriptionOn an infinite smooth table, there's a big round fixed cylinder and a little ball whose volume can be ignored.Currently the ball stands still at point A, then we'll give it an initial speed and a direction. If the ball hits the cylind
2017-10-15 12:43:13
346
转载 ACM计算几何题目推荐
原文地址:http://blog.csdn.net/zsc09_leaf/article/details/6331809快出去比赛了,这三四天尽量多刷一点计算几何的题了,emmmm紧张诶//第一期计算几何题的特点与做题要领：1.大部分不会很难，少部分题目思路很巧妙2.做计算几何题目，模板很重要，模板必须高度可靠。3.要注意代码的组织，因为计算几何
2017-10-13 23:03:14
270
原创 POJ - 3348 Cows(求凸包的面积)
DescriptionYour friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Gi
2017-10-13 17:31:45
282
原创 POJ - 3241 Object Clustering(莫队算法/曼哈顿最小生成树)
DescriptionWe have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes a and b (a, b ≤ 500). The resemblance of object i and object j is defined by dij = |
2017-10-11 10:50:13
378
原创 CodeForces - 191A Dynasty Puzzles(dp)
The ancient Berlanders believed that the longer the name, the more important its bearer is. Thus, Berland kings were famous for their long names. But long names are somewhat inconvenient, so the Berlanders started to abbreviate the names of their kings. Th
2017-10-09 09:59:32
356
转载 HDU - 5517 Triple(二维树状数组)
Problem DescriptionGiven the finite multi-set A of n pairs of integers, an another finite multi-set B of m triples of integers, we define the product of A and B as a multi-setC=A∗B={⟨a,c,d⟩∣⟨a,b⟩∈A, ⟨c,d,e⟩∈B and b=e}For each ⟨a,b,c⟩∈C, its BETTER set
2017-09-29 15:41:21
281
原创 HDU - 5536 Chip Factory（字典树）
Problem DescriptionJohn is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today, the i-th chip produce
2017-09-22 09:22:12
300
原创 PHP实现验证码功能
//先做个记录,功能还不完善,界面还太丑画图的时候要安装扩展库gd2,我安装的命令是sudo apt-get install php-gd,加上php版本号之后说找不到包,就多尝试几次了captcha.php<?php //设置session，开启会话功能 session_start(); //设置验证码图片大小 $image = imagecrea
2017-09-20 23:26:15
376
转载 Ubuntu17.04重启搜狗输入法
//原文：http://blog.csdn.net/zhangxiao93/article/details/53267676、搜狗输入法老是出问题，输入不了中文，正写代码写的起劲，就不想用关机这种方法来解决这个问题了，百度了一下，用下面的命令解决这个问题，真的有用，嘻嘻嘻嘻#!/bin/shpidof fcitx | xargs killpidof sogou-qimpanel | x
2017-09-20 14:57:19
994
原创 PHP+MySql实现一个简单的留言板
//嗯，跟着书学的，代码不是自己写的，但是都能理解，有时间自己去写个好看一点的吼吼吼～留言板是接触WEB开发的基础，写一个留言板需要知道前端的一些基础标签，对数据库有一个了解会基础SQL语言，PHP基础知识，前段基础+数据库基础+PHP基础=>留言板。前方高能哇（界面真的是吃藕诶…先建一个数据库，数据库里有两张表，一个存账号密码，一个存留言信息//创建数据库，里面有两张表Admin
2017-09-15 17:38:30
29358
10
原创 POJ - 1113 Wall（计算几何凸包）
DescriptionOnce upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect sha
2017-09-14 23:08:33
388
原创 PHP连接数据库基础知识及易错点
emmmmm，想用PHP写计网的课设，所以滚去看了下PHP连接数据库…以下操作都是在Ubuntu17.04，LAMP下进行，且PHP数据库的扩展包为MySqli，MySqli为MySql的扩展版，在使用上稍有区别，比较容易混淆，要注意下面是PHP连接数据库的一些最最最基本的操作额，分界线两边的代码要分开操作一些细节问题：mysqli_connect()的第一个参数就是本机的地址，写
2017-09-14 11:40:00
2892
4
转载 HDU - 5489 Removed Interval （dp+线段树） 2015合肥网络赛
HDU - 5489 Removed Interval （dp+线段树） 2015合肥网络赛Problem DescriptionGiven a sequence of numbers A=a1,a2,…,aN, a subsequence b1,b2,…,bk of A is referred as increasing if b1<b2<…<bk. LY has just learned how to find the longest increasing subsequence (LIS).Now
2017-09-13 12:55:26
441
原创 记2017暑假这一段生活
记2017暑假这一段生活 两个多月，很长也很短，不长也不短，但它就这样过去了，很感慨。如果说学到了什么东西，当然有很多，比如最基础的数据结构包括单调栈单调队列树状数组线段树等等，还有难一点的主席树啊，数链剖分啊以及了解离线处理可持久化…当然这些都是很实质上的东西，同时还有一些其他感悟。原来大学也可以像高中一样每天好好的学习哇，真的很感谢两个队友在刚开始集训的时候把我从网易云这个坑里拉出来了（当然，现在还是喜欢网易云，真是有点觉得自己有一段时间很沉迷啊，仔细想想，如果自己荒废了今年的暑假，那现在我应该会
2017-09-12 15:06:43
367
1
原创 HDU-6052 card card card（尺取法）
HDU-6052 card card card（尺取法）Problem DescriptionAs a fan of Doudizhu, WYJ likes collecting playing cards very much. One day, MJF takes a stack of cards and talks to him: let's play a game and if you win, you can get all these cards. MJF randomly assigns
2017-09-11 21:43:17
265
转载 凸包问题的五种解法
凸包详解凸包问题的五种解法前言：首先，什么是凸包？ 假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。如下图： 这里写图片描述然后，什么是凸包问题？ 我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。 现给出点的数目13，和各个点的坐标。求构成凸包的点？解一：穷举法（蛮力法）时间复杂度：O(n³）。 思路：两点确定一条直线，如果剩余的其它点都在这条直线的同一侧，
2017-09-07 20:59:01
457
原创 HDU - 6183 Color it（线段树）
HDU - 6183 Color it（线段树）Problem DescriptionDo you like painting? Little D doesn't like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain foll
2017-09-07 15:02:27
343
原创 HDU - 6191 Query on A Tree（可持久化字典树）
HDU - 6191 Query on A Tree（可持久化字典树）Problem DescriptionMonkey A lives on a tree, he always plays on this tree.One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.M
2017-09-06 21:19:11
503
原创 HDU - 4575 Tree（可持久化字典树）
HDU - 4575 Tree（可持久化字典树）Problem Description Zero and One are good friends who always have fun with each other. This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give
2017-09-06 16:32:28
561
1
原创 NBUT - 1457 Sona (莫队算法)
NBUT - 1457 Sona (莫队算法)问题描述Sona, Maven of the Strings. Of cause, she can play the zither.Sona can't speak but she can make fancy music. Her music can attack, heal, encourage and enchant.There're an ancient score(乐谱). But because it's too long, Sona can
2017-09-04 20:17:50
325
原创 HYSBZ - 2038 小Z的袜子（分块+莫队算法）
HYSBZ - 2038 小Z的袜子（分块+莫队算法）Description作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽
2017-09-04 14:54:05
303
原创 POJ - 2104 K-th Number（主席树）
POJ - 2104 K-th Number（主席树）DescriptionYou are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order
2017-09-03 19:52:24
287
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人