format_jam's pan

对于GCC:

64位整数类型是long long

输出方法：printf("%lld ",x);同时支持cin cout

VC++等(PKU使用):

64位整数类型是__int64

输出方法: printf("%I64d ",x);不支持cin cout

谨记谨记~~

特别注意：dev c++ 的gcc有点“核突”（不是有点了好不好 >_< ）要用这个：printf("%I64d ",x);

我可真的被他害惨了。。。

cylixstar 晓鸣的文章对本文有重要贡献

查找序列中 元素之和最大的连续子序列 的一次扫描法：
eg.
2 3 4 -1 1 -10 12
从左到右扫描
当k>=0时，k一直累加；否则，k遇到较大数即可替换。Max记录当前最大值。

左右扫描思想：

这种思想可谓相当实用和普遍。今天的一题求两个不相交序列和上次google的那题不许用除法线性求一个数列b[i]=a[1]*a[2]*...*a...

这个算法的改进针对筛法里面的重大缺陷的：对同一个合数往往重复标记多次！（改进为1次）而且实现还非常简单，强烈推荐！！！

由于某道面试题目的驱使，GA和PSO成了这个假期里面最有意义的东西。

---------------------------我是好好味的分界线------------------------

GA:遗传算法其实是一个很大同时很热的课题，掌握好GA并不容易。关于GA的研究，主要集中在交叉和变异算子上，同时编码也是每一个实际应用中不可回避的问题。因此，这两个方面就构成了GA在应用上所要解决的问题，也直接决定了得出结果的好坏。

PSO:这是一种相当有意思的算法。理论基础是动物的群体智慧和个体经验对行为的影响。这其实是我在国庆前已经在宿舍看着维基百科写出来了。效果也是相当的好，连后来的GA都突破不了。附上关键公式：

第i个微粒表示为Xi =(xi1, xi2, …,xiD)，它经历过的最好位置（有...

原来除了快速排序等O(nlogn)优秀排序外,竟然还存在着计数排序、基数（radix）排序、和桶排序等线性O（n）排序算法。
尽管它们的实现前提是某种特定情况，而且速度上不一定快过快排等O（nlogn）之流。但它们的设计思路值得一提。传统排序算法都是基于比较大小而诞生的。而它们却抛开了这点，迎来了突破。这就是所谓的Thinkingout of the box！！！
其实早有科学家证明过基于比较的排序算法的极限就是O（nlogn），这无疑是给这种思路的继续发展判了死刑。这种思路上的否定值得借鉴。
ps.具体的算法实现可参看《算法导论》排序一章。
基数排序套用计数排序可以很好地应用于高精度中的排序。

最近被c++的字符串搞到焦头烂额，索性总结一下
源代码如下：

#include #include #include using namespace std; int main() { string s1,s2; int i,j,k; s1="jam"; //赋值 s2="jambo";//cin>>s2; s1.swap(s2); //交换 cout<< i=s1.length(); //长度 s1.insert(i,".lai"); //插入(位数,内容) s1+="wait"; s1.append("for"); //尾部添加字符串 cout<< s1.erase(0,9); //删除（开始位数，删除位数目） cout<< s1.replace(4,3,"u"); //替换（开始位数，位数目，替换内容） cout<< k=0; j=s1.find("ei",k); //查找（从第k位开始查找，不存在时返回－1） cout<< const char *ss= s1.c_str(); cout<< return 0; }

区间算术 //网上搜到的
区间算术又称区间数学、区间分析、区间计算，在1950、60年代引进以作数值分析上计算舍去误差的工具。

T × S = { x |属于T的某些y，及属于S的某些z，使得x = y × z }.
区间算术的基本运算是，对于实数在线的子集[a,b]及[c,d]：

[a,b] + [c,d] = [a+c, b+d]
[a,b] - [c,d] = [a-d, b-c]
[a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
[a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c,b/d)]
被一个包含零的区间除，在基础区间算术上无定义。

加法和乘法符合交换律、结合律和子分配律:集X ( Y + Z )是XY +XZ的子集。

1.矢量叉积  
   
  设矢量P=（x1,y1） ，Q＝(x2,y2) 
  则矢量叉积定义为：    P × Q   = x1*y2  -   x2*y1
  几何意义为 P Q移到同一起点时围成平行四边形的面积（有正负）

  得到的是一个标量  
  显然有性质   P×Q=-(Q×P)P×(-Q)=-(P×Q)  
 如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉积； 
  叉乘的重要性质：  
     若P×Q>0,则 P在Q的顺时针方向  
     若P×Q<0,则 P在Q的逆时针方向  
     若 P×Q=0,则P与Q共线，但可能同向也可能反向  

2、判断两线段是否相交

我们分两步确定两条线段是否相交：
(1)．快速排斥试验

  设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，
  如果R和T不相交，显然两线段不会相交；

(2)．跨立试验
  如果两线段相交，则两线段必然相互跨立对方，P1P2跨立Q1Q2 ，  
  则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即
  [( P1 - Q1 ) × ( Q2 - Q1 )] * [( P2 - Q1 ) × ( Q2 - Q1 )] < 0
  上式可改写成
  [( P1 - Q1 ) × ( Q2 - Q1 )] * [( Q2 - Q1 ) × ( P2 - Q1 )] > 0
  
  当( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，
    说明( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，
    所以 P1 一定在线段 Q1Q2上；

  同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。

所以判断P1P2跨立Q1Q2的依据是：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0
同理判断Q1Q2跨立P1P2的依据是：
( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0

   

没上博客已有一段时间了。
依然冷清。。。
 
 每对顶点间的最短路径——弗洛伊德（Floyd）算法
    解决此问题有两种方法：其一是分别以图中每个顶点为源点共调用n次Dijkstra算法；其二是采用Floyd算法。两种算法的时间复杂度均为O(n3)，但后者形式上比较简单。
    Floyd算法的基本思想：
    （1）利用二维数组A[1..n-1][1..n-1], A[i][j]记录当前vi到vj的最短路径长度，数组A的初值等于图的代权临街矩阵;
    （2）集合S记录当前允许的中间顶点，初值S=Φ;
    （3）依次向S中加入v0 ,v1… vn-1，每加入一个顶点，对A[i][j]进行一次修正：设S={v0 ,v1… vk-1}，加入vk，则A(k)[i][j] = min{ A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]}。
A(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
    A(n-1)[i][j]就是vi到vj的最短路径长度。