yzmduncan
- 浏览: 330319 次
- 性别:
- 来自: 武汉
-
最新评论
-
di1984HIT：
学习了～
Spring scope="prototype" -
netkiller.github.com：
路还很长看看我的博客 http://netkiller.git ...
写博客是个好习惯 -
ooo456mmm：
JAVA 设计模式之——动态代理 -
hanmiao：
问题是这么问的：请使用 Java 的基本数据类型表示壹下单链表 ...
JAVA数据结构之——单链表的逆序 -
hanmiao：
谢谢，今天刚好有人问我这个问题，结果没有答上来，看了你这篇文章 ...
JAVA数据结构之——单链表的逆序
文章列表
不记得上一次写博客是什么时候了。平常工作忙的像狗，周末有时也加班，空余时间太少。这周妹纸出差，难得清静。
这一年工作节奏还是蛮快的，参与开发5、6个系统，也学了做了不少东西，有技术性强的，也有边 ...
听过朴素贝叶斯的人，知道多项式朴素贝叶斯是神马，伯努利贝叶斯是神马吗？如果不知道，请继续读下去。
其实所谓的“多项式”或“伯努利”，只不过是在求先验概率和条件概率时统计方法不一样，基本 ...
分类的概念很简单，就是给出一个样本x，判断样本所属的类别y，分类器就是映射函数f: y=f(x)。当然，这个函数是需要根据以往的经验（大量已知类别的样本集）来构造的。这个构造的过程，称为训练，而如何构造，就是 ...
例：ZOJ3645
题意：高斯消元模板题(浮点型)
/**
高斯消元求解线性方程组.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
///高斯消元模板
const double eps = 1e-12;
const int Max_M = 15; ///m个方程,n个变量
const int ...
本来上周日(11.25)轮到我做汇报，PPT都写好了，看到ZOJ有月赛，便想练练手。
当时做比赛的时候已经三点了，看到DFIJ这四题出的比较多，就决定拿下这4道题。
J题(ZOJ3675) Trim the Nails
题意：指甲宽为m，指甲刀宽为n，单位均为毫米，但指甲刀是不完整的，'*'表示完整，'.'表示不完整。问最少剪几次可以剪完指甲。注意指甲刀可以翻转。比如输入m=7 n=6且指甲刀表示为***..*：
fingernail: -------
nail clipper: *..***
nail clipper turned ...
STK简介
美国Analytical Graphics公司开发的STK卫星工具包软件，是航天工业领先的商品化分析软件。 STK可以快速方便地分析复杂的陆、海、空、天任务，
并提供易于理解的图表和文本形式的分析结果，确定最佳解决方案。它 ...
计算几何是研究几何目标在计算机环境内的数学表示，计算等方面的理论和应用。
首先必须理解向量的点积和叉积。点积一般用来计算投影，数学证明等。叉积用来判断相对方位，求面积等，叉积的模为平行四边形面积。
问题1. 如何判断两条线段相交
通过快速排斥实验和跨立实验。快速排斥实验室看以两条线段作为对角线的矩形是否相交，若不相交，则必定两条线段不相交；跨立实验是看其中一条线段是否跨立另一条线段，可以通过矢量叉积实现。
问题2. 如何判断点在多边形内（ZOJ1081）
一种简单的方法——射线法。从该点引一条水平射线，根据射线与多边形的交点数的奇偶性来判 ...
树形DP，即是在一颗树上进行DP，一般是有叶子节点状态推出根节点状态。结合几个简单例子分析。
例1. POJ2342/POJ3342
【题意】
公司有n个人，每个人有价值vi，有一天举办年会，每个人都可以参加，但有严格的等级制度，参加活动时，不能同时出现a和a的上司，问如何才能使总和最大。
【分析】
每个人只有去和不去两种状态，设DP[i][0]和DP[i][1]分别表示第i个人不参加和参加年会，获得的总的最大价值。
则状态转移方程为：
DP[i][1] += DP[j][0],
DP[i][0] += max{DP[j][0],DP[j][1]};其中j为i的孩子节点。 ...
最近在做单调队列，发现了最长上升子序列O(nlogn)的求法也有利用单调队列的思想。
最长递增子序列问题：在一列数中寻找一些数，这些数满足：任意两个数a[i]和a[j]，若i<j，必有a[i]<a[j]，这样最长的子序列称为最长递增子序列。
设dp[i]表示以i为结尾的最长递增子序列的长度，则状态转移方程为：
dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i].
这样简单的复杂度为O(n^2)，其实还有更好的方法。
考虑两个数a[x]和a[y]，x<y且a[x]<a[y],且dp[x] ...
单调队列即队列内元素单调递增或递减，删除数据可以在队头或者队尾，加入元素只能在队尾加入。 由于单调队列的队头一定是最小值，故查询为O(1)；每个元素最多进队一次，出队一次，摊排分析下来仍然是O(1).
例1. 广 ...
在二维平面上的n个点中，如何快速的找出最近的一对点，就是最近点对问题。
一种简单的想法是暴力枚举每两个点，记录最小距离，显然，时间复杂度为O(n^2)。
在这里介绍一种时间复杂度为O(nlognlogn)的算法。其实，这里用到了分治的思想。将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归地求最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。如果这两个点分别在S1和S2中，问题就变得复杂了。
为了使问题变得简单，首先考虑一维的情形。此时， ...
Polya定理
设有n个对象，G是这n个对象上的置换群，用m种颜色涂染这n个对象，每个对象涂染一种颜色，问有多少种染色方案？一种染色方案在群G的作用下变为另一种方案，则这两种方案当作是一种方案。
方案数为
POJ2409
题意：一家项链公司生产手镯。n颗珠子形成一个环，用m种颜色给n颗珠子染色，就得到了各种各样的手镯。但是，经过旋转和翻转使之吻合的算同一种方案。
例如，当用2种颜色对5颗珠子进行染色的方案数为8，如下图所示。
解：显然，对于这n个对象，有n种旋转和n种翻转。
1. 对于旋转，有c(gi) = gcd(n,i)，i为转动几颗珠 ...
n个有序的元素应有n!个不同的排列，若一个排列使得所有的元素都不在原来位置上，则称这个排列为错排。
错排公式推导
设n个数1,2,3...,n错排数目为Dn，对于其中任意一个数i：
(1) 数i分别与其他的n-1个数交换位置，其余n-2个数进行错排，共得到(n-1)Dn-2个错排；
(2) 对除数i以外的n-1个数进行错排，然后i与其中每个数互换，得到(n-1)Dn-1个错排。
因此，得到递推关系：Dn=(n-1)(Dn-1 + Dn-2),D1=0,D2=1。它的通解为Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)! - ... ...
所谓鸽巢原理，即n+1只鸽子，只有n个巢，则至少有一鸽巢有两只鸽子。
鸽巢原理理解起来并不困难，有些题目需要转换一下。
POJ3770
题意：有n个数，可能相同也可能不相同，从中取出一些数，使它们的和能被c整除(c<=n)，任意输出一种方案。
解：构造序列si，使得
s1 = a1
s2 = a1 + a2
s3 = a1 + a2 + a3
...
sn = a1 + a2 + ... + an
这样，有两种可能：
...
中国剩余定理
中国剩余定理是中国古代求解一次同余方程组的方法，是数论中的一个重要定理。
设m1，m2，m3，...，mk是两两互素的正整数，即gcd(mi,mj)=1，i!=j，i,j=1,2,3,...,k.
则同余方程组：
x = a1 (mod n1)
x = a2 (mod n2)
...
x = ak (mod nk)
模[n1,n2,...nk]有唯一解，即在[n1,n2,...,nk]的意义下，存在唯一的x，满足：
x = ai mod [n1,n2,...,nk], i=1,2,3,...,k。
解可以写为这种形式：
x = sigma( ...