shiwei408-CSDN博客

原创 poj2411 2663 2420 dp+状态压缩（多米诺骨牌问题）

题目描述：用1*2 的矩形通过组合拼成大矩形，求拼成指定的大矩形有几种拼法。首先我们先求用1*2 的矩形拼成 n*m的矩形有多少种拼法当n*m为奇数时，一定是不会拼出来的，因为想要拼出来就需要整数倍的小矩形数目。为了加速算法，要把m，n中小的那个当做列分两个步骤：1）先求出相邻两行的转化关系 2）通过相邻两行的转化关系算出经过n次转化有几种方法能拼

2013-04-19 00:04:13 10900 7

原创矩阵快速幂 poj3070 3233 3735 3150

一、矩阵的基础知识1.结合性（AB)C=A(BC）．2.对加法的分配性（A+B)C=AC+BC，C(A+B）=CA+CB ．3.对数乘的结合性 k(AB）=（kA)B =A(kB）．4.关于转置 (AB)'=B'A'．一个矩阵就是一个二维数组，为了方便声明多个矩阵，我们一般会将矩阵封装一个类或定义一个矩阵的结构体，我采用的是后者。最特殊的矩阵应该就是单位矩阵e了，它的对

2013-04-18 13:04:53 5964 1

原创 dp+离散（RMQ）

一、RMQ问题描述RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j=n)，返回数列A中下标在[i,j]里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题ST算法（Sparse Table）:它是一种动态规划的方法。以最小值为例。a为所寻找的数组. 用一个二维数组dp(i,j)记录区间

2013-04-14 16:22:12 1219

原创 dp+四边形不等式优化（poj1160 hdu2829 3480 3506 3516）

一、四边形不等式基本理论在动态规划的转移方程中，常见这样一种转移方程：这两个定理证明在赵爽的《动态规划加速原理之四边形不等式》中给出了相关的证明。二、四边形定理的应用1、poj1160 题目大意：给定n个城市，在m个城市里建邮局，使所有城市到最近邮局的距离和最小。很容易得到这样的方程：dp(i,j)=min(dp(i-1,k)+w(k+1,j)) , i-1

2013-04-11 23:21:57 5264 2

原创阶乘浅析poj1150 3406 zoj1222 2358

阶乘问题分为几类：1.求阶乘末尾0的个数，，直接除以5，累加即可。2.求阶乘的结果一共有多少位，stirling公式：n！≈sqrt(2*PI*n) * (n/e)^n，直接取以10为底的对数，整数部分即为位数。http://poj.org 第1423题3.求阶乘的最后非零位，这类问题比较复杂，专题中我们着重讨论这个问题首先看POJ1150题目大意：求n的m排列的最后非零

2013-03-30 11:09:16 2365

原创 true false 与TRUE FALSE 的区别

BOOL 是window中的数据类型，BOOL的原型是typedef long BOOL，所以 int i=6; BOOL b=(BOOL)i; 是可以的。 bool是C++中的一个关键字它可以有两种值true和false也都是关键字，所以 int i=6; bool b=(bool

2012-08-30 15:39:35 9784 1

转载推荐一系列优秀的Android开发源码

专题类：一、Android开发图书推荐：http://book.apkbus.com/ 二、Android开发精选源码推荐：http://demo.apkbus.com/ 三、Android 开发 UI设计http://www.apkbus.com/design/ 四、 Android开发系列教程合集http://dev.apkbus.com/

2012-08-29 16:37:44 3839

转载各种距离

在做分类时常常需要估算不同样本之间的相似性度量(SimilarityMeasurement)，这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。　　本文的目的就是对常用的相似性度量作一个总结。本文目录：1.欧氏距离2.曼哈顿距离3. 切比雪夫距离4. 闵可夫斯基距离5.标准化欧氏距离6

2012-05-25 16:05:37 87307 15

转载 [学习笔记--Printf()输出格式控制]

hzh-fa 发表于 2006-8-12 12:26:001．转换说明符 %a(%A) 浮点数、十六进制数字和p-(P-)记数法(C99) %c 字符 %d 有符号十进制整数 %f 浮点数(包括float和doulbe) %e(%E)

2012-05-05 02:04:46 1321

转载 50个c/c++源代码网站

C/C++是最主要的编程语言。这里列出了50名优秀网站和网页清单，这些网站提供c/c++源代码。这份清单提供了源代码的链接以及它们的小说明。我已尽力包括最佳的C/C++源代码的网站。这不是一个完整的清单，您有建议可以联系我，我将欢迎您的建议，以进一步加强这方面的清单。1、http://snippets.dzone.com/tag/c/--数以千计的有用的C语言源代码片段2、http://w

2012-04-15 22:55:02 2350

原创 __int64 与long long 的区别

//为了和DSP兼容，TSint64和TUint64设置成TSint40和TUint40一样的数 //结果VC中还是认为是32位的，显然不合适 //typedef signed long int TSint64; //typedef unsigned long int TUint64; //ANSI C中规定long long才能表示64位 //参见：http://msd

2012-04-15 19:25:53 127467 16

转载在java应用程序中加入声音

先说一下在 applet 中播放声音文件的一般步骤：　　　　创建一个 AudioClip 对象　　装入 .au 或者wav的声音文件（或者后面所说的支持的类型）到 AudioClip 对象　　　　　　下面是相应的代码：　　　import java.applet.*;　　　　AudioClip ac = getAudioClip(getCodeBase(), soundFil

2012-03-12 23:54:42 7049

转载 jframe 标题栏处理

jframe 标题栏处理收藏转http://zengxx1989.javaeye.com/blog/470040在JDK1.4以前，我们只有一种方式来去掉窗口的标题栏，那就是直接使用JWindow，用JWindow来代替JFrame使用。但用过JWindow的人一定知道，JWindow在操作系统的任务栏是不可见的，这样我们就无法在几个视窗之间来切换到这个窗口了。使

2012-03-10 20:15:08 9686

原创 vim 的使用方法

Vim几句话介绍 Vim是Unix系统上的文本编辑软件（你该不会不知道什么是文本编辑软件吧！），在windows上也有移植的版本，方便了Windows上的用户。Vim的文本编辑功能非常强大，强大的有些让人吃惊！并且非常稳定，你的文档不用经常存盘，它不会出现类似于“***程序内部错误！”等等现象，***程序曾经让我欲哭无泪啊！开始使用Vim吧！启动：在命令提示

2012-02-26 21:56:41 18600 1

转载优先队列队列栈的使用方法

STL 中优先队列的使用方法(priority_queu)基本操作：empty() 如果队列为空返回真pop() 删除对顶元素push() 加入一个元素size() 返回优先队列中拥有的元素个数top() 返回优先队列对顶元素在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。使用方法：头文件： #include 声明方式：

2012-02-25 10:52:37 998

原创 poj2305 JAVA大数运算

描述：给一个数b，两b进制大数p，m，求p mod m b进制结果。String st = Integer.toString(num, base); // 把num当做10进制的数转成base进制的st(base int num = Integer.parseInt(st, base); // 把st当做base进制，转成10进制的int(parseInt有两个参数,第一个为要转的字符

2012-02-22 15:09:10 889

原创 int longlong int64所占字节数

32位系统下，int、long、long long、__int64所占字节数和取值范围字节数char: 1字节（8位）int: 4字节 (32位，取值范围 -2^31 ～ 2^31-1)unsigned int : 4字节 (32位，取值范围 0 ～ 2^32-1)long: 4字节 (32位，取值范围 -2^31 ～ 2^31-1)unsigned long : 4字节

2012-02-21 16:51:58 29356 1

转载计算几何常用算法

1. 矢量减法设二维矢量 P = （x1,y1），Q = (x2,y2)则矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )显然有性质 P - Q = - ( Q - P )如不加说明，下面所有的点都看作矢量，两点的减法就是矢量相减；2.矢量叉积设矢量P = （x1,y1），Q = (x2,y2)则矢量叉积定义为： P × Q

2012-02-19 22:43:24 4564

原创几大最短路径算法比较

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要介绍其中的三种。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题

2012-02-19 14:12:46 1642

转载探索之美——接触优先队列~

转自：http://blog.csdn.net/dooder_daodao/article/details/5761550优先队列：顾名思义，首先它是一个队列，但是它强调了“优先”二字，所以，已经不能算是一般意义上的队列了，它的“优先”意指取队首元素时，有一定的选择性，即根据元素的属性选择某一项值最优的出队~ 百度百科上这样描述的：　　优先级队

2012-02-19 13:42:39 805

原创 inline 的作用及使用方法

作用inline函数不像正常函数在调用时存在压栈和call的操作，它会把程序代码直接嵌入到调用代码段中，也就是说使用inline函数会增大二进制程序的体积，但是会使执行速度加快。同时，它在编译期间可以对参数进行强类型检查，这是它优于宏的一个方面方法（一）inline函数（摘自C++ Primer的第三版）在函数声明或定义中函数返回类型前加上关键字inline即把min（）

2012-02-19 12:25:29 1918

转载 Bellman-ford和spfa算法

一、Bellman-Ford算法最优性原理它是最优性原理的直接应用，算法基于以下事实：l 如果最短路存在，则每个顶点最多经过一次，因此不超过n-1条边；l 长度为k的路由长度为k-1的路加一条边得到；l 由最优性原理，只需依次考虑长度为1，2，…，k-1的最短路。适用条件&范围l 单源最短路径

2012-02-18 17:55:35 1536

原创如何用dos运行cpp

首先找到编译器的位置，例如：g++的位置D:\codeblocks\MinGW\bin然后设置环境变量，将系统变量的Path中加入D:\codeblocks\MinGW\bin就可以了。最后运行cmd如图

2012-02-16 10:33:19 5978

原创出现问题：BOOTSTRP导致访问侵犯在IMSCUT.DL的解决办法

这个问题困惑了我很久，经过不断尝试发现这个问题是微软输入法与该程序不兼容导致的！出现这个问题的用户一般都是把中文作为默认输入法，任务栏右边为"CH"（打字时无需切换输入法即可打中文），解决方法即是把"EN"作为默认输入方式。我是这样解决的： 1. 在添加删除程序里删除微软输入法。 2. 在语言设置里，把微软输入法全部删除。 3. 重起后你会发现语言设置里微软输入法依然存在，不过这

2012-02-15 22:02:15 1954

原创次小生成树

T0 --> T1 --> T2 --> ... --> Tn (T) 变成最小生成树.所谓的变换是，每次把T_i中的某条边换成T中的一条边, 而且树T_(i+1)的权小于等于T_i的权. 具体操作是： step 1. 在T_i中任取一条不在T中的边u_v. step 2. 把边u_v去掉，就剩下两个连通分量A和B，在T中，必有唯一的边u'_v' 连结A和B.

2012-02-14 16:34:02 685

原创并查集

设想要对不相交的集合进行两种操作：（1）检索某元素属于某个集合；（2）合并两个集合。我们最常用的数据结构是并查集的森林实现。也就是说，在森林中每棵树代表一个集合，用树根来标识一个集合。树的形态不重要，重要的是每棵树里有哪些元素。合并操作为了把两个集合s1和s2并起来，只需要把s1的根的父亲设置为s2的根就可以了，这里有一个优化：让深度较小的树成为深度较大的树的子树，这样查找的次数会少一些。

2012-02-14 10:36:11 620

原创 prim算法的简单证明

反证法：假设权值最小的边不在最小生成树中。此时将权值最小的边加入生成树中，那么必然会构成一个回路，去掉回路中权值最大的边，构成一个新的树，这时与假设构成矛盾。所以权值最小的边一定在最小生成树中。

2012-02-12 13:44:47 5984 1

我只想做一个努力的人