ACM的暑假集训结束了，趁着军训还没开始，对整个暑假接触到的东西作了一个总结，因为刚参加ACM不久，所以内容大都比较基础吧，文章中提到了些参考资料，如果需要的话，请留下邮箱。

目录
1)数据结构
 1.并查集
 2.高精度数
 3.线段树
 4.字典树<未完成>
2)常用算法
 1.递推
 2.动态规划
 3.贪心
 4.搜索
3)图论部分  1.2-SAT问题
 2.差分约束系统
 3.二分图
 4.最短路(SPFA,Dijkstra)
 5.欧拉回路<未完成>
 6.最优比率生成树
 7.关键路径
 8.网络流(流的算法/应用)
  最大流算法(3种)
  最小费用最大流算法
  图的连通性（最小点割集）<未完成>
  混合欧拉回路
 9.其他图论相关问题算法:
  K短路
  图的单向连通（包括2次DFS缩点）
4)其他
 1.计算几何
 2.数学(数论,组合数学,数值计算)
5)附录
 1.A*算法
 2.位运算之格雷码：
 3.线性同余方程

一．数据结构：

1.并查集.

用于实现合并与查找两种操作的数据结构.
实现方法:线形数组,有根树.
优化:
把深度小的树合并到深度大的树,深度相等时任选一棵树,既max(h1,h2), if h1<>h2. / h1+1, if h1=h2.
合并操作时的路径压缩.
并查集的偏移向量:
并查集的偏移向量属于并查集的变形，只要适用于集合数目较少，或是固定的并查集类型。
增加一个offset字段,表示元素相对根的偏移量.

在find函数中计算偏移量
int findset ( int x )
{
    int t ;
    if ( father [ x ] == x ) return x ;
    else t = findset( father [ x ] ) ;
    offset [ x ] = ( offset [ x ] + offset [ father [ x ] ] ) % DEPTH ;//DEPTH表示几个状态量
    //如果1182中，DEPTH=3；
    father [ x ] = t ;
    return t ; 
}//使用函数递归调用查找父亲在处理上优于循环。
union函数中计算偏移量
void union(int x,int y,int d){
    int fx , fy ;
    fx = find ( x ) ;
    fy = find ( y ) ;
    if ( fx == fy ) return ;
    father [ fx ] = fy ;
    offset [ fx ] = (offset [ y ] - offset[x]+d+3)% 3 ;
} 

2.高精度数

大数的加减乘除
小数的高精度计算参考pku1001

RT
以后常来看看吧

Count.java

public class  Count
{
    int resolveStm(Stm stm){
        int temp1=0,temp2=0;
        if(stm.kind==1){
            temp1=resolveStm(((CompoundStm)stm).stm1);
            temp2=resolveStm(((CompoundStm)stm).stm2);
            return temp1>temp2? temp1:temp2;
        }else if(stm.kind==2){
            return resolveExp(((AssignStm)stm).exp);
        }else if (stm.kind==3){
            return countExpInExpList(((PrintStm)stm).exps);
        }else{
            return 0;
        }
    }
    int countExpInExpList(ExpList expList){
        if(expList.kind==1){
            return 1;
        }else if(expList.kind==2){
            return 1+countExpInExpList(((PairExpList)expList).tail);
        }else{
            return 0;
        }
    }
    int resolveExp(Exp exp){
        int temp1,temp2;
        if(exp.kind==1){
            return 0;
        }else if(exp.kind==2){
            return 0;
        }else if(exp.kind==3){
            temp1 = resolveExp(((OpExp)exp).left);
            temp2 = resolveExp(((OpExp)exp).right);
            return temp1>temp2?temp1:temp2;
        }else if(exp.kind==4){
            temp1=resolveStm(((EseqExp)exp).stm);
            temp2=resolveExp(((EseqExp)exp).exp);
            return temp1>temp2?temp1:temp2;
        }else{
            return 0;
        }
    }
    int resolveExpList(ExpList expList){
        int temp1,temp2;
        if(expList.kind==2){
            temp1 = resolveExp(((PairExpList)expList).head);
            temp2 = resolveExpList(((PairExpList)expList).tail);
            return temp1>temp2?temp1:temp2;
        }else if(expList.kind==1){
            return resolveExp(((LastExpList)expList).last);
        }else{
            return 0;
        }
    }
}
Interp.java
public class  Interp
{
    void startinterpStm(Stm stm){
        Table t=new Table(null,0,null);
        interpStm(stm,t);
    }
    Table interpStm(Stm stm,Table t){
        if(stm.kind==1){
            Table t1=interpStm(((CompoundStm)stm).stm1,t);
            Table t2=interpStm(((CompoundStm)stm).stm2,t1);
            return t2;
        }else if(stm.kind==2){
            IntAndTable it1 = interExp(((AssignStm)stm).exp,t);
            Table t1=update(it1.t,((AssignStm)stm).id,it1.i);
            return t1;
        }else if(stm.kind==3){
            printExplist(((PrintStm)stm).exps,t);
            return t;
        }else{
            return t;
        }
    }
    IntAndTable interExp(Exp exp,Table t){
        if(exp.kind==1){
            int temp=lookup(t,((IdExp)exp).id);
            return new IntAndTable(temp,t);
        }else if(exp.kind==2){
            return new IntAndTable(((NumExp)exp).num,t);
        }else if(exp.kind==3){
            IntAndTable it1= interExp(((OpExp)exp).left,t);
            IntAndTable it2= interExp(((OpExp)exp).right,it1.t);
            int x1,x2,result;
            x1=it1.i;
            x2=it2.i;
            if(((OpExp)exp).oper==1){
                result=x1+x2;
            }else if(((OpExp)exp).oper==2){
                result=x1-x2;
            }else if(((OpExp)exp).oper==3){
                result=x1*x2;
            }else if(((OpExp)exp).oper==4){
                result=x1/x2;
            }else{
                result=0;
            }
            return new IntAndTable(result,t);
        }else if(exp.kind==4){
            Table t1=interpStm(((EseqExp)exp).stm,t);
            IntAndTable t3= interExp(((EseqExp)exp).exp,t1);
            return t3;
        }else{
            return new IntAndTable(0,t);
        }
    }
    Table update(Table t1,String i,int v){
        Table t2=new Table(i,v,t1);
        return t2;
    }
    int lookup(Table t,String key){
        if(key.compareTo(t.id)==0){
            return t.value;
        }else return lookup(t.tail,key);
    }
    void printExplist(ExpList exps,Table t){
        if(exps.kind==1){
            IntAndTable temp=interExp(((LastExpList)exps).last,t);
            System.out.println(temp.i);
        }else if(exps.kind==2){
            IntAndTable temp=interExp(((PairExpList)exps).head,t);
            System.out.print(temp.i+"");
            printExplist(((PairExpList)exps).tail,t);
        }else return;
    }
// IntAndTable interExpList(ExpList explist,Table t){
// }
}
class Table
{
    String id;
    int value;
    Table tail;
    Table(String i,int v,Table t){id=i;value=v;tail=t;}
}
class IntAndTable
{
    int i;
    Table t;
    IntAndTable(int ii,Table tt){i=ii;t=tt;};
}

KMP算法也算接触很久了，今天却突然发现不知道那个的复杂度是怎么来的
于是想啊想，查啊查，总结如下
设代码为

s=0;  
for(i=1;i<=m,i++){  
    while(s>0&&a[i]!=b[s+1])s=next(s)  
    if(a[i]==b[s+1])s++;  
    if(s==n) return (i-n)
}

分析的关键是那个while循环循环会让s减少
而s又只会在第五行增加，于是j最多增加m次，
在然后我们就知道j最多减少m次(因为不能为负)
平摊到每个for上就是一次
所以复杂度就是O(m)了
不过也有书上说是O(m+n)
这个就不是很明白了… 想想在说…

这里是我的技术博客。

文件：

options {
    JAVA_UNICODE_ESCAPE = true;
}
PARSER_BEGIN(MiniJavaParser)
public class MiniJavaParser {}
PARSER_END(MiniJavaParser)
// Insert a specification of a lexical analysis here.
TOKEN :
{
    < LPAREN: "(" >
        | < RPAREN: ")" >
        | < LSQPAREN: "[" >
        | < RSQPAREN: "]" >
        | < LBRACE: "{" >
        | < RBRACE: "}" >
        | < DOT: "." >
        | < ASSIGN: "=" >
        | < LT: "<" >
        | < PLUS: "+" >
        | < MINUS: "-" >
        | < AND : "&&" >
        | < NOT : "!" >
        | < SEMICOLON: ";" >
        | < PUBLIC: "public" >
        | < RETURN: "return" >
        | < BOOLEAN: "boolean" >
        | < CLASS: "class" >
        | < INTERFACE: "interface" >
        | < ELSE: "else" >
        | < EXTENDS: "extends" >
        | < FALSE: "false" >
        | < IF: "if" >
        | < WHILE: "while" >
        | < INTEGER: "int" >
        | < LENGTH: "length" >
        | < MAIN: "main" >
        | < NEW: "new" >
        | < STATIC: "static" >
        | < STRING: "String" >
        | < THIS: "this" >
        | < TRUE: "true" >
        | < PRINT: "System.out.println" >
        | < VOID: "void" >
    }
    TOKEN : /* LITERALS */
    {
        < INTEGER_LITERAL: ( ["1"-"9"] (["0"-"9"])* | "0" ) >
    }
    TOKEN : /* IDENTIFIERS */
    {
        < IDENTIFIER: (|)* >
        |
        < #LETTER:
        [
        "u0024",
        "u0041"-"u005a",
        "u005f",
        "u0061"-"u007a",
        "u00c0"-"u00d6",
        "u00d8"-"u00f6",
        "u00f8"-"u00ff",
        "u0100"-"u1fff",
        "u3040"-"u318f",
        "u3300"-"u337f",
        "u3400"-"u3d2d",
        "u4e00"-"u9fff",
        "uf900"-"ufaff"
        ]
        |
        < #DIGIT:
        [
        "u0030"-"u0039",
        "u0660"-"u0669",
        "u06f0"-"u06f9",
        "u0966"-"u096f",
        "u09e6"-"u09ef",
        "u0a66"-"u0a6f",
        "u0ae6"-"u0aef",
        "u0b66"-"u0b6f",
        "u0be7"-"u0bef",
        "u0c66"-"u0c6f",
        "u0ce6"-"u0cef",
        "u0d66"-"u0d6f",
        "u0e50"-"u0e59",
        "u0ed0"-"u0ed9",
        "u1040"-"u1049"
        ]
    }
    SKIP :
    {
        < " " >
        | < "t" >
        | < "n" >
        | < "r" >
        | < "//" (~["n"])* "n" >
        | <"/*" (~["*"])* "*" (~["/"] (~["*"])* "*")* "/">
    }
    // The following is a simple grammar that will allow you
    // to test the generated lexer.
    void Program() :
    {}
    {
        MainClass() (ClassDecl())*
    }
    void MainClass() :
    {}
    {
        "class" "{" "public" "static" "void" "main" "(" "String" "[" "]" "{" Statement() "}" "}"
    }
    void ext() :
    {}
    {
        ("extends"  )?
    }
    void ClassDecl() :
    {}
    {
        "class" ext()  "{" (VarDecl())* (MethodDecl())* "}"
    }
    void VarDecl():
    {}
    { Type() ";"}
    void MethodDecl():
    {}
    {"public" Type()
        "(" FormaList() ")"
        "{" ( LOOKAHEAD(2) VarDecl() )* (Statement())*  "return" Exp() ";" "}"
    }
    void FormaList():
    {}
    {(Type()  "FormalRest()")?}
    void FormaRest():
    {}
    {"," Type() }
    void Type():
    {}
    {
        |"boolean"
        |LOOKAHEAD(2)
        "int"
        |"int" "[" "]"
    }
    void Statement():
    {}
    {"{" (Statement())* "}"
    |"while" "(" Exp() ")" Statement()
    |"System.out.println"  "(" Exp() ")"
    | instat1() "=" Exp() ";"
    |"if" "(" Exp() ")" Statement() inif()
}
void inif():
{}
{(LOOKAHEAD(2) "else" Statement())?}
void instat1():
{}
{("[" Exp() "]")?}
void Exp():
{}
{Expa() (LOOKAHEAD(2) (Expb()))?
}
void Expa():
{}
{"true"
    |"false"
    |
    |"this"
    |"!" Exp()
    |"(" Exp() ")"
    |LOOKAHEAD(2)
    "new" "int" "[" Exp() "]"
    |"new" "(" ")"
}
void Expb():
{}
{
    op() Exp()
    |"[" Exp() "]"Exp()
    |LOOKAHEAD(2)
    "." "length"
    |"."
}
void op():
{}
{"&&"
    |"<"
    |"+"
    |"-"
    |"*"}
    void ExpList():
    {}
    {(Exp()  (ExpRest())*)?}
    void ExpRest():
    {}
    {"," Exp()}
    void Goal() :
    {}
    {
        ( MiniJavaToken() )*
    }
    void MiniJavaToken():
    {}
    {
        "class"  |  | "{" | "public" | "static" | "void" |
            "main" | "(" | "String"  | "[" | "]" | ")" | "}" | "extends" | ";"
            | "return" | "," | "int" | "boolean" | "=" | "if" | "else" | "while"
            | "System.out.println" | "&&" | "<" | "+" | "-" | "*" | "." |
            "length" | | "true" | "false" | "this" | "new" |
            "!"
    }