$$ ax^3+bX^2+cx+d=0 $$

根的关系:

$$ x1 + x2 + x3 = (-\frac{b}{a}) $$

$$ x1 \times x2 + x1 \times x3 + x2 \times x3 = \frac{c}{a} $$

$$ x1 \times x2 \times x3 = (-\frac{d}{a}) $$

牛顿迭代解方程(x0附近的根)

double Newton_Iterative(double a,double b,double c,double d,double x0)
{
    double f0,f0d,x;
    x = x0;
    do
    {
        x0 = x;
        f0 = ((a * x + b) * x + c) * x + d;
        f0d = ( 3 * a * x + 2 * b ) * x + c;
        x = x0 - f0 / f0d;
    }
    while(fabs(f0) >= 1e-12);
    return x;
}

牛顿迭代法

校赛个人赛第三场部分解题报告（A,D,F,I）

这次我完成了四道题分别是A,D,F,I

一大半时间我都花在了A上，我犯了很究级的错误

首先是VC6.0的algorithm里没有min函数，而我用min做变量名导致CE4次，找了半天才找出来

校赛个人赛第六，七场总结

这两场比赛体现了英文水平的重要性

第六场的题目超长，用词还诡异，话了很长时间才看懂

这两场题目都比较有难度，第六场我只出了2题

A Grey Area

A题是很诡异的统计，是一道纯模拟就能过的题，其他的不多说了

先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？

有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但…也只能如此了。

POJ打破传统,以前是做一题送一题,现在是做一题送两题,那么我们就不用客气了

言归正传 题号:2606 Rabbit hunt 2780 Linearity 1118 Lining Up

大致题意是输入N个点.计算能穿过最多的点的直线,并输出最大点的个数

资料由互联网收集整理，供新手参考学习 这里又生动点的演示：http://www.cnblogs.com/wangfupeng1988/archive/2011/12/26/2302216.html

POJ 3267 The Cow Lexicon

这题是一道DP问题,我的想法如下:

1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;

2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)

//并查集
//注意类型匹配
const int maxn = 100002;
int DSet[maxn];
void init(int n) {
    for(int i = 0 ; i <= n ; i ++)
        DSet[i] = i;
}
int findP(int id) {
if(DSet[id] != id)
    DSet[id] = findP(DSet[id]);
    return DSet[id];
}
//返回根节点ID
int UnionEle(int a,int b) {
    a = findP(a);
    b = findP(b);
    if(a > b)
        a ^= b ^= a ^= b;
    DSet[b] = a;
    return a;
}

/**
 * KMP模式匹配
 * 算法复杂度O(m+n)
 * ACM 模板 
 *
 * @Author OWenT
 * @link http://www.owent.net
 */

// 最大字符串长度
const int maxLen = 10000;
// 前一个匹配位置,多次匹配注意要重新初始化
// 注：preMatch[i]表示0~preMatch[i-1]能和?~i匹配
int preMatch[maxLen]={0};

/**
 * kmp匹配算法
 * @param char[] source 查找源
 * @param char[] checked 查找目标
 * @return int 根据以下两个分支返回值分别表示不同的含义
 */
int kmp_match(char source[],char checked[]) {
    int i = 0, j = 0;
    memset(preMatch, 0, sizeof(preMatch));

    if(!checked[i]) // 被匹配串为空串，直接返回 0
        return 0;

    ++ i;
    while(checked[i]) {
        for(j = preMatch[i - 1]; checked[i] != checked[j] && j; j = preMatch[j - 1]);
        preMatch[i] = (checked[i] == checked[j])? j + 1 : 0 ;
        ++ i;
    }
    //计算匹配子串个数(子串间无重叠)(与以下一起二选一)
    int num = 0;//计数变量
    for(i = j = 0; source[i]; ++ i) {
        if(checked[j] == source[i])
            ++ j;
        else if(j)
            -- i, j = preMatch[j - 1];

        if(!checked[j])
            ++ num, j = 0;//如果要子串间重叠 则此句中j = 0 改成 j = preMatch[j - 1]
    }
    return num;

    //计算首个匹配子串位置(与以上一起二选一)
    for(i = j = 0; checked[j] && source[i]; ++ i) {
        if(checked[j] == source[i])
            ++ j;
        else if(j)
            -- i, j = preMatch[j - 1];
    }

    //返回匹配的串的第一个字符出现位置(从1开始计数,0表示无匹配)
    if(!checked[j])
        return i - j + 1;
    else
        return 0;

    return 0;
}