1 相中人

尚未进行身份认证

Bug绝缘体. Bug绝缘体. Bug绝缘体.

等级
TA的排名 30w+

拓扑排序

拓扑排序算法思想1.入度数组ru[],记录是否存在环的情况;2.利用bfs()将入度为0的依次压入队列,将其所指向的点入度减一;3.在排序的过程中实现题目目的;例题HDU2647思路:1.先反向建边,x比y多则将y指向x;2.用一个val[]数组记录每一个点最大需要多花费的钱,依次向上更新,排序的过程就完成了,数据的更新;## 代码#include <bits/stdc...

2020-02-22 20:13:11

最短路三种算法(Floyd+dij(优先队列优化版)+spfa)

单源最短路Floyd(纯暴力)思想:贪心+暴力枚举;看代码就能理解了void Floyd(){ //初始化dis[][]为很大的值; //注意在输入时需要将dis[x][y],dis[y][x],都录入; for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ dis[i][j]...

2020-02-20 14:04:31

KMP(模板)

Oulipo The 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 nor...

2020-02-10 17:43:32

AC自动机(初学模板)

Keywords SearchIn the modern time, Search engine came into the life of everybody like Google, Baidu, etc.Wiskey also wants to bring this feature to his image retrieval system.Every image have a lon...

2020-02-10 17:26:01

回文串——马拉车(模板)

N - 最长回文给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等 Input 输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理)字符串长度len <= 110000 Output...

2020-02-10 15:37:11

dfs序+树状数组

Apple TreeThere is an apple tree outside of kaka’s house. Every autumn, a lotof apples will grow in the tree. Kaka likes apple very much, so he hasbeen carefully nurturing the big apple tree.The t...

2020-01-19 10:20:38

莫队板子

Chika and Friendly PairsChika gives you an integer sequence a1,a2,…,an and m tasks. For each task, you need to answer the number of "friendly pairs" in a given interval.friendly pair: for two integ...

2020-01-18 19:12:50

扫描线板子题

PictureA number of rectangular posters, photographs and other pictures of thesame shape are pasted on a wall. Their sides are all vertical orhorizontal. Each rectangle can be partially or totally c...

2020-01-16 19:50:46

分块模板

分块模板题目分块暴力;#include<bits/stdc++.h>using namespace std;const int N=1e5+55;int a[N],l[N],r[N],head[N],lazy[N]; //a,存输入数据,l存第i块的左边界,r记录第块的右边界,head[]记录点在哪一块int n; ...

2020-01-16 17:01:57

主席树模板题

I - Super MarioMario is world-famous plumber. His “burly” figure and amazing jumpingability reminded in our memory. Now the poor princess is in troubleagain and Mario needs to save his lover. We re...

2020-01-15 17:55:32

最小生成树——模板

题目模版题很简单;一共有n个城市(从1开始编号),有m条路线,求出一条能连通n个城市的最小路线;分析首先需要找到一条能连通所有城市的路线;其次要保证这条路径的路程最短;算法简介常用两种算法:Kruskal 时间复杂度为eloge e为总共的边数。1.先将各个边的权值从小到大排序;2.按从小到大的顺序依次将边连接的点加入到一个集合中,并利用并查集确定一个祖先节点,使其中的...

2019-08-11 11:21:40

最短路(dij+优先队列优化)模板

最短路径问题描述有n个城市,求s到e的最短路径;当n的值较小时,直接用(dij)算法没有问题,但是当数值较大或者访问过多时就需要优化;dij(算法)时间复杂度(n2);算法思想:贪心,从起点开始,不断的寻找不同点到起始点的最短距离;...

2019-08-10 17:49:41

最长上升序列

第一种方法复杂度(n2)虽然好理解但是耗时,会被卡时间;#include<stdio.h>#include<iostream>#include<algorithm>#include<cstring>#include<queue>#include<vector>#include<cmath>usin...

2019-08-10 16:17:08

取模运算

取模,变小1.加法取模 (A+B)%P=(A%P+B%P)%P;2.乘法取模 (AB)%P=(A%PB%P)%P;以上是最简单的取模;;;~减法取模:(A-B)%P=(A%P-B%P+P)%P; 要加上*P;~整除取模:费马小定理:(A\B\P)(A/B)%P=(A%P * B^(P-2)%P)%P:...

2019-07-31 20:22:23

数据结构——字典树

高大上,实用,真香;字典树,顾名思义:用来当成字典用的 树型结构处理方式——(两种应用:1.字母数,2. 01字典树)几个模块:1.建树。2.查询树。3.删除一些元素。上图这是一棵存储单词的字典树,数组tree[N][26], 表示字典树,图中的数字就是开辟空间的大小,从上至下每当没有相同字母时就开辟新的空间(代码中见详解),增加分支;这儿需要注意的是:要灵活使用辅助数组进行,标记或者...

2019-07-29 20:42:40

数据结构——树状数组

树状数组(Beautiful数据结构)树状数组,又名前缀树,是很实用的工具,顾名思义树状数组(树型结构的数组,一种存储方式)!!!!!由子树构成的大树,大数;上图就是其形象的结构图样。A[1]->C[1] ; C[2]->A[1]+A[2] ; C[3]->A[3] ; C[4]->C[2]+C[3]->A[1]+A[2]+A[3]+A[4]...

2019-07-29 19:15:02

数据结构——线段树

线段树(一种二叉搜索树)树形结构的特点让它更方便查询搜索。线段树方便与对区间查询,区间更新维护,这是因为树上的父亲节点表示了一段区间。叶子结点才是原始的元素。如上图所示:利用线段树解决问题的步骤如下(以模版题——给N个数,求任意区间合为例子):对于这个算法个人认为必需理解:1.在建树时怎样将树全部遍历,将节点处理成区间和。2.在维护区间时利用lazy标记将数据添加到树中,并且如何在需...

2019-07-28 12:28:16

算法入门--真入门

图论——最小生成树 最小生成树,从一点出发,要求经过每一个节点,问所经过的最短路径是多少? *模版题如下所示* H。。。。。修路问题啊!!!! 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成...

2019-07-17 20:15:56

背包问题

动态规划入门——背包问题注意计算机的最大优点在于它的强大计算功能,以及存储功能,你能做的就是合理利用这些优点该循环就循环,该遍历就遍历。要知道简洁的算法毕竟不是那么多。最基础、最重要、最好玩——01背包* 问题描述: 有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。 例如...

2019-07-13 13:33:12
勋章 我的勋章
  • 领英
    领英
    绑定领英第三方账户获取
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。