5 小鸡炖蘑菇_

尚未进行身份认证

stay hungry,stay foolish.

等级
TA的排名 1w+

DBCP和Druid数据库连接池使用

需要用到的jar包,commons-dbcp2-*.jar、commons-logging-*.jar、commons-pool2-*.jar,*代表版本号DataSourceTest类package com.edu.zzu.Util;import org.apache.commons.dbcp2.BasicDataSourceFactory;import org.apache.commons.l

2016-12-14 12:29:53

用于求最近公共祖先(LCA)的 Tarjan算法–以POJ1986为例(转)

原文地址:https://comzyh.com/blog/archives/492/给定有向无环图(就是树,不一定有没有根),给定点U,V,找出点R,保证点R是U,V的公共祖先,且深度最深;或者理解为R离这两个点的距离之和最小.如何找出R呢?最一般的算法是DFS(DFS本是深度优先搜索,在这里姑且把深度优先遍历也叫做DFS,其实是一种不严谨的说法).先看一道赤裸裸的LCA:POJ 1330 Near

2016-10-30 21:11:27

KM算法详解+模板(转)

KM算法用来求二分图最大权完美匹配。 本文配合该博文服用更佳:趣写算法系列之–匈牙利算法现在有N男N女,男生和女生每两个人之间有好感度,我们希望把他们两两配对,并且最后希望好感度和最大。 怎么选择最优的配对方法呢?首先,每个妹子会有一个期望值,就是与她有好感度的男生中最大的好感度。男生呢,期望值为0,就是,,,只要有一个妹子就可以啦,不挑~~这样,我们把每个人的期望值标出来。 然后,开

2016-10-29 20:28:17

Hopcroft-Harp 算法

匈牙利算法原理 为了降低时间复杂度,可以在增广匹配集合M时,每次寻找多条增广路径。这样就可以进一步降低时间复杂度,可以证明,算法的时间复杂度可以到达O(sqrt(n)*m)。 基本算法 该算法主要是对匈牙利算法的优化,在寻找增广路径的时候同时寻找多条不相交的增广路径,形成极大增广路径集,然后对极大增广路径集进行增广。在寻找增广路径集的每个阶段,找到的增广路径集都具有相同的长度,且随着算法的进行

2016-10-29 17:02:00

混合图的欧拉回路求解方法(转)

原文地址http://yzmduncan.iteye.com/blog/1149049基础知识 欧拉回路是图G中的一个回路,经过每条边有且仅一次,称该回路为欧拉回路。具有欧拉回路的图称为欧拉图,简称E图。 无向图中存在欧拉回路的条件:每个点的度数均为偶数。 有向图中存在欧拉回路的条件:每个点的入度=出度。 欧拉路径比欧拉回路要求少一点: 无向图中存在欧拉路径的条件:每个点的度数均为偶数或者

2016-10-29 13:16:05

poj-1041-John's trip(计算欧拉路)

计算欧拉路,如果欧拉路存在,就数组欧拉路上的边的编号;如果有多条欧拉路,输出字典序最小的那一条。而且题目保证了图的连通性图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次, 称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。 判断欧拉路是否存在的方法 有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度。

2016-10-27 21:43:18

poj-2449-Remmarguts' Date(A*算法+Dijkstra)

题目就是求两点之间第k短路,但如何起点和终点相等的时候,k需要加1涉及到的算法是Dijkstra和A*寻路算法#include <iostream>#include <iomanip>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <cmath>#include <queue>

2016-10-27 20:15:03

理解A*寻路算法具体过程(转)

这两天研究了下 A* 寻路算法, 主要学习了这篇文章, 但这篇翻译得不是很好, 我花了很久才看明白文章中的各种指代. 特写此篇博客用来总结, 并写了寻路算法的代码, 觉得有用的同学可以看看. 另外因为图片制作起来比较麻烦, 所以我用的是原文里的图片. 当然寻路算法不止 A* 这一种, 还有递归, 非递归, 广度优先, 深度优先, 使用堆栈等等, 有兴趣的可以研究研究~~简易地图 如图所示简易地图

2016-10-27 20:05:42

poj-2186-Popular Cows (tarjan算法)

题意:有n只牛,牛之间存在一些关系,比如a认为b很受欢迎,b认为c很受欢迎,这样呢,a也会认为c很受欢迎,问根据给出的关系,有多少头牛被其他所有的牛都认为是受欢迎的?思路:求强连通分量缩点后反向建图 然后判断图中是否有且仅有一个点的入度为 0,是的话就输出这个店包含的牛的个数,否则就输出 0#include <iostream>#include <cstdio>#include <cstdli

2016-10-25 20:28:59

CCF 201312-4 有趣的数

问题描述   我们把一个数称为有趣的,当且仅当:   1. 它的数字只包含0, 1, 2, 3,且这四个数字都出现过至少一次。   2. 所有的0都出现在所有的1之前,而所有的2都出现在所有的3之前。   3. 最高位数字不为0。   因此,符合我们定义的最小的有趣的数是2013。除此以外,4位的有趣的数还有两个:2031和2301。   请计算恰好有n位的有趣的数的个数。由于答案可能非

2016-10-25 13:51:53

CCF 201312-3 最大的矩形

在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。 请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。 输入格式   第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1

2016-10-25 13:40:12

求乘法逆元

乘法逆元,是指数学领域群G中任意一个元素a,都在G中有唯一的逆元a‘,具有性质a×a’=a’×a=e,其中e为该群的单位元。(百度百科的解释,鬼才能看懂┑( ̄Д  ̄)┍)我理解的乘法逆元是,若a*b≡1(mod p),则b是a的乘法逆元,a是b的乘法逆元,b也可以写成a-1乘法逆元有什么用呢? 在取模运算中,有a*b%p=(a%p) * (b%p) 但是没有(a/b)%p=(a%p)/(b%p)

2016-10-25 13:31:45

poj-2942-Knights of the Round Tabler

题目大意: 有N个骑士,他们要开圆桌会议,也就是要坐成一个圈,相互憎恨的两个骑士是不能坐在相邻位置的,那样他们就会打起来。给出所有的憎恨关系。如果有人不可能开会,例如他可能憎恨所有人,就不能再去开会了。求这样人的个数。注意:1、所给出的憎恨关系一定是双向的,不存在单向憎恨关系。 2、由于是圆桌会议,则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士。 3、一个骑

2016-10-23 19:46:59

无向图双连通分量(poj-3352)

预备知识:图的相关知识 https://www.byvoid.com/blog/biconnect/ 题目的大致意思是:在一个连通图中,至少添加多少条边,使图中不存在桥Tarjin时借助并查集,由于桥(删除之后图就不连通的边)不属于任何双连通分量,所以在Tarjin时,把不是桥的边的u,v并在一起,表示u,v在同一个双连通分量里,进行缩点。 一个重要的结论: 若要使得任意一棵树,在增加若干条边

2016-10-23 15:32:14

割点和桥

点连通度与边连通度 在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。一个图的点连通度的定义为,最小割点集合中的顶点数。 类似的,如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合。一个图的边连通度的定义为,最小割边集合中的边数。双连通图、割点与桥 如果一个无向连通图的点连通

2016-10-21 21:45:41

格雷码

格雷码(Gray Code)是一个数列集合,每个数使用二进位来表示,假设使用n位元来表示每个数字,任两个数之间只有一个位元值不同。 例如以下为3位元的格雷码: 000 001 011 010 110 111 101 100 。 如果要产生n位元的格雷码,那么格雷码的个数为2^n. 十进制 葛雷码 二进制 0 000 000 1 001 001 2 011

2016-10-19 13:52:20

原根

对于两个正整数gcd(a,m)=1,由欧拉定理可知,存在正整数 d ≤ m-1, 比如说欧拉函数 d=φ(m),即小于等于 m的正整数中与 m互素的正整数的个数,使得 ad≡1(mod m)。 由此,在gcd(a,m)=1时,定义 a对模m的指数 δm(a)为使 ad≡1(mod m) 成立的最小的正整数 d。由前知 δm(a) 一定小于等于 φ (m),若δm(a) = φ(m),则称a是模

2016-10-16 20:14:32

费马小定理&&欧拉定理

费马小定理费马小定理是数论中的一个定理:假如a是一个整数,p是一个质数,那么ap-a是p的倍数,可以表示为ap≡a(mod p) 如果a不是p的倍数,这个定理也可以写成 a(p-1)≡1 (mod p) 维基百科欧拉定理在数论中,欧拉定理(也称费马-欧拉定理或欧拉φ函数定理)是一个关于同余的性质。欧拉定理表明,若 n,a为正整数,且 n,a互素(即 gcd(a,n)=1),则 aφ(n)≡1(m

2016-10-16 19:51:04

中国剩余定理(转)

中国剩余定理介绍 在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以3余2),五五数之剩三(除以5余3),七七数之剩二(除以7余2),问物几何?”这个问题称为“孙子问题”,该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步:找出三个数:从3和5的公倍数中找出被7除余1的最小数15,从3和7的公倍数中找出被5除余1 的最小数21,最后从5和7的公倍数中找出除3余1

2016-10-15 20:03:57

poj-2115 C Looooops (单变元模线性方程)

题意:利用了 k位存储系统 的数据特性进行循环。例如int型是16位的,那么int能保存2^16个数据,即最大数为65535(本题默认为无符号),当循环使得i超过65535时,则i会返回0重新开始计数,如i=65534,当i+=3时,i=1,其实就是 i=(65534+3)%(2^16)=1。有了这些思想,设对于某组数据要循环x次结束,那么本题就很容易得到方程: x=[(B-A+2^k)%2^k]

2016-10-15 20:00:56

查看更多

勋章 我的勋章
    暂无奖章