小、pi孩

数据结构

Codeforce(14) python学习(29) 动态规划(1) 快速幂逆元(2) 最短路(1) 算法(26) 蓝桥杯(1) 计算机网络(2) 题解(2)

/ 注册

全部文章 / 数据结构（共19篇）

POJ-3690 二维哈希

二维哈希题意：给定一个由和0组成的大小为nm的匹配对象，和T个大小为pq的匹配模式，求匹配对象中至少出现一次匹配模式的个数思路：将每一行看成一个字符串，计算从每个位置开始长度为Q的字符串子串的哈希值，然后把得到的哈希值在列方向看成一个字符串，计算每个位置开始长度为P的字符串子串的哈希值，通过上...

2020-10-07

0 361

Next 数组及KMP

Next 数组及KMP KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个getnext()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。其中最难理解的部分即next数组的求法以及回溯前缀数组 ...

2020-10-07

0 466

线段树（区间求和，区间加，单点更新等）

线段树线段树是一种二叉搜索树。它将一段区间划分为若干个单位区间，每一个节点都储存着一个区间。线段树可做区间求和，区间最值，区间更新，单点更新等操作以区间和为例来做介绍：建树 const int maxn=1000000+5; struct Tree{ int l,r; ...

2020-10-07

0 420

归并排序

归并排序归并排序是建立在归并操作上的一种有效的排序算法，是采用分治法的一个典型应用。其时间复杂度为O(n log n) 归并排序的步骤如下：划分求解：将序列分成元素个数尽量相等的两半。递归求解：将两半元素分别排序。合并问题：将两个有序表合并在一起当我们要排序一个数组的时候，...

2020-10-07

0 492

POJ-1258 最小生成树(Prim)

最小生成树一个有n个节点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用Kruskal算法或者prim算法求出。 kruskal 算法的过程为不断对子图进行合并，直到形成最终的最小生成树。prim 算法的过程则是只存在一个子图，不断...

2020-10-07

0 377

区间第K大（POJ-2104）

可持久化线段树不是一颗完全二叉树，所以不能用层次序编号，而应该直接记录每个节点的左、右子节点的编号。可持久化线段树维护了每次操作后线段树的历史形态。下面举个简单的例子来理解一下：以poj-2104为例；这棵树是一颗不用修改的线段树题意：即多次查询，查询区间第K大的数。 POJ-2104 (区...

2020-10-07

0 350

POJ-1456（并查集）

回顾并查集。题意：给定N个商品，每个商品有利润pi和过期时间di，每天只能卖一个商品，过期商品不能在卖，求如何安排每天卖的商品，可以使收益最大。（1 <= N, pi, di <= 10000）样例： 4 50 2 10 1 20 2 30 1 7 20 1 2...

2020-10-07

0 345

练习搜索之三维迷宫（HDU-2102）

A计划题目：可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。现据密探...

2020-10-07

0 531

Codeforces 1106D(Lunar New Year and a Wander )

题目： Lunar New Year is approaching, and Bob decides to take a wander in a nearby park. The park can be represented as a connected graph with n nodes a...

2020-10-07

0 431

Codeforces 1263D(Secret Passwords )

题目： One unknown hacker wants to get the admin’s password of AtForces testing system, to get problems from the next contest. To achieve that, he sneake...

2020-10-07

0 493