Catalan数:

$$ h(1)=1,h(0)=1 $$$$ h(n)=\begin{cases} \sum_{i=0}^{n-1} h(i) \times h(n-i-1) & \text{if }(n>=2) \\\\ \frac{C(2n,n)}{n+1} & \text{if }(n=1,2,3,\mathellipsis) \end{cases} $$

相关结论： n边形能分解成三角形的分法数为 h(n – 2) n个节点能组成的二叉树个数为 h(n) 一个栈(无穷大)的进栈序列为1，2，3，…，n，出栈序列种数为 h(n)

参考（转载）： http://zh.wikipedia.org/wiki/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0 http://baike.baidu.com/view/4076365.htm

/**
 * 简易四则运算（栈实现）
 * #include 
 * #include 
 */
std::stack opr;
std::stack num;
char oprPRI[256];
//初始化调用
void initCalc()
{
    //优先级设置
    char oprMap[7][2] = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}, {'(', 100}, {')', 0} };
    for(int i = 0; i < 7; i ++)
        oprPRI[oprMap[i][0]] = oprMap[i][1];
}
bool checkNum(char c)
{
    return c == '.' || (c >= '0' && c <= '9');
}
double calcOpr(double l, double r, char opr)
{
    switch(opr)
    {
        case '+': return l + r;
        case '-': return l - r;
        case '*': return l * r;
        case '/': return l / r;
        case '^': return ::pow(l, r);
    }
    return 0.0;
}
void calcStack()
{
    double cl, cr;
    cr = num.top();
    num.pop();
    cl = num.top();
    num.pop();
    num.push(::calcOpr(cl, cr, opr.top()));
    opr.pop();
}
double calc(const char str[])
{
    while(!opr.empty())
        opr.pop();
    while(!num.empty())
        num.pop();
    int i = 0, len = strlen(str);
    num.push(0.0);
    opr.push('(');
    while(i < len)
    {
        if(::checkNum(str[i]))
        {
            double l;
            ::sscanf(str + i, "%lf", &l);
            while(::checkNum(str[i]))
            i ++;
            num.push(l);
        }
        else
        {
            char c = str[i ++];
            if(c == ')')
            {
                while(opr.top() != '(')
                    calcStack();
                opr.pop();
            }
            else if(oprPRI[c] > oprPRI[opr.top()])
                opr.push(c);
            else
            {
                while(opr.top() != '(' && oprPRI[c] <= oprPRI[opr.top()])
                    calcStack();
                opr.push(c);
            }
        }
    }
    while(opr.size() > 1)
        calcStack();
    return num.top();
}

基础函数:

// 最大公约数,欧几里得定理
int gcd(int a, int b)
{
    return b?gcd(b, a % b): a;
}
// 拓展欧几里得定理
// 求解ax + by = gcd(a,b)
int ext_gcd(int a, int b, int &x, int &y)
{
    int tmp, ret;
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    ret = ext_gcd(b, a % b, x, y);
    tmp = x;
    x = y;
    y = tmp - (a / b) * y;
    return ret;
}
//交换数值
void swap(int &a, int &b)
{
    a ^= b ^= a ^= b;
}

/**
 * a的b次方Mod c
 * 参数为整数
 * 使用时注意修改类型
 */
int PowerMod(int a, int b, int c)
{
    int tp = 1;
    while (b)
    {
        if (b & 1)
            tp = (tp * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return tp;
}

1.欧拉函数

Ψ（n） = 小于n且与n互质的数的个数

关于差分约束（转载）

（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。） 比如有这样一组不等式：

$$ \begin{cases} X1 - X2 <= 0 \\\\ X1 - X5 <= (-1) \\\\ X2 - X5 <= 1 \\\\ X3 - X1 <= 5 \\\\ X4 - X1 <= 4 \\\\ X4 - X3 <= (-1) \\\\ X5 - X3 <= (-3) \\\\ X5 - X4 <= (-3) \end{cases} $$

(1)

一、引言

　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

这是一道并查集+树的题，采用Tarjan离线算法

首先BS一下出题的人，也太懒了吧，还要我们看1984题才知道输入

题目的意思是告诉一个节点数为40000的树，问我们两个节点间的距离。实际上就是找出公共父节点，Tarjan算法写挫了很容易TLE，我开始用Vector就写搓了，结果TLE，后来重写，自己写邻接表然后AC了。

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2446

这是一道匹配题，把行数（r）和列数（c）按（r+c）%2分成两组，然后连边，做一次二分图匹配，可以直接用匈牙利算法

匹配数等于两组的元素个数则为YES，否则NO

代码如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;

int py[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
/**
 * 最大二分图匹配
 * 最大二分图匹配 = 最小点覆盖
 * Base 1
 */
#define MAXM 1024 //行
#define MAXN 1024 //列
bool mat[MAXM][MAXN] = {false};
bool isMatchedR[MAXN] = {false};
int matchedR[MAXN];//调用前初始化: memset(matchedR, 0, sizeof(matchedR));

bool getLeftPath(bool matin[MAXM][MAXN], int pos, const int &n)
{
    int i;
    for(i = 1 ; i <= n ; i ++)
    {
        if(matin[pos][i] && !isMatchedR[i])
        {
            isMatchedR[i] = true;
            if(!matchedR[i] || getLeftPath(matin, matchedR[i], n))
            {
                matchedR[i] = pos;
                return true;
            }
        }
    }

    return false;
}
long GetMaxMacthNumber(bool matin[MAXM][MAXN], const int &m, const int &n)
{
    int i,ans = 0;
    for(i = 1 ; i <= m ; i ++)
    {
        memset(isMatchedR, false, sizeof(isMatchedR));
        if(getLeftPath(matin, i, n))
            ans++;
    }
    return ans;
}

bool mapbs[35][35];
int index[35][35];
int main()
{
    int m, n, k, i, j, r, c, tx, ty;
    scanf("%d %d %d", &n, &m, &k);
    memset(matchedR, 0, sizeof(matchedR));
    memset(mapbs, true, sizeof(mapbs));
    for(i = 0; i < k; i ++)
    {
        scanf("%d %d", &c, &r);
        mapbs[r][c] = false;
    }
    for(i = 0; i < 35; i ++)
        mapbs[0][i] = mapbs[i][0] = mapbs[n + 1][i] = mapbs[i][m + 1] = false;

    r = c = 0;
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
        {
            if(mapbs[i][j])
            {
                if((i + j) % 2 == 0)
                    index[i][j] = ++ r;
                else
                    index[i][j] = ++ c;
            }
        }
    }
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
        {
            if(mapbs[i][j] && (i + j) % 2 == 0)
            {
                for(k = 0; k < 4; k ++)
                {
                    tx = i + py[k][0];
                    ty = j + py[k][1];
                    if(mapbs[tx][ty])
                    {
                        mat[index[i][j]][index[tx][ty]] = true;
                    }
                }
            }
        }
    }

    if(r != c || GetMaxMacthNumber(mat, r, c) != r)
        printf("NO\n");
    else
        printf("YES\n");
    return 0;
}

好久不写代码，省赛之后一直在赶作业和复习。对自己还真没什么信心

话说回来试了一下联系赛

三道水题，虽然钱两题很快，但是竟然多敲了几个没用的字符导致WA掉了，会范这种错误表示最近状态不宜写算法题啊

第三题想水一把结果我推得结论有漏洞+有道难题的服务器让人不爽的程度

int a = 12345678;
//格式为sring输出
Label1.Text = string.Format("asdfadsf{0}adsfasdf",a);
Label2.Text = "asdfadsf"+a.ToString()+"adsfasdf";
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",a);//asdfadsf￥1,234.00adsfasdf
Label2.Text = "asdfadsf"+a.ToString("C")+"adsfasdf";//asdfadsf￥1,234.00adsfasdf
double b = 1234.12543;
int a = 12345678;
//格式为特殊的string样式输出
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",b);//asdfadsf￥1,234.13adsfasdf
Label2.Text = "asdfadsf"+b.ToString("C")+"adsfasdf";//asdfadsf￥1,234.13adsfasdf
Label1.Text = string.Format("{0:C3}",b);//￥1,234.125
Label2.Text = b.ToString("C3");//￥1,234.125
Label1.Text = string.Format("{0:d}",a);//十进制--12345678
Label2.Text = b.ToString("d");//十进制--相同的类型，转换报错
Label1.Text = string.Format("{0:e}",a);//指数--1.234568e+007
Label2.Text = b.ToString("e");//指数--1.234125e+003
Label1.Text = string.Format("{0:f}",a);//定点数--12345678.00
Label2.Text = b.ToString("f");//定点数--1234.13
Label1.Text = string.Format("{0:n}",a);//数值--12,345,678.00
Label2.Text = b.ToString("n");//数值--1,234.13
Label1.Text = string.Format("{0:x}",a);//十六进制--bc614e
Label2.Text = b.ToString("x");//16--带有小数不能转换，出错
Label1.Text = string.Format("{0:g}",a);//通用为最紧凑--12345678
Label2.Text = b.ToString("g");//通用为最紧凑--1234.12543
Label1.Text = string.Format("{0:r}",a);//转来转去不损失精度--整数不允许用，报错
Label2.Text = b.ToString("r");//转来转去不损失精度--1234.12543
double b = 4321.12543;
int a = 1234;
自定义模式输出：
//"0"描述：占位符，如果可能，填充位
Label1.Text = string.Format("{0:000000}",a);// 001234
Label2.Text = string.Format("{0:000000}",b);// 004321
//"#"描述：占位符，如果可能，填充位
Label1.Text = string.Format("{0:####### }",a);// 1234
Label2.Text = string.Format("{0:####### }",b);// 4321
Label1.Text = string.Format("{0:#0#### }",a);// 01234
Label2.Text = string.Format("{0:0#0000}",b);// 004321
//"."描述：小数点
Label1.Text = string.Format("{0:000.000}",a);//1234.000
Label2.Text = string.Format("{0:000.000}",b);//4321.125
double b = 87654321.12543;
int a = 12345678;
//","描述：数字分组，也用于增倍器
Label1.Text = string.Format("{0:0,00}",a);// 12,345,678
Label2.Text = string.Format("{0:0,00}",b);// 87,654,32
Label1.Text = string.Format("{0:0,}",a);// 12346
Label2.Text = string.Format("{0:0,}",b);// 87654
Label1.Text = string.Format("{0:0,,}",a);// 12
Label2.Text = string.Format("{0:0,,}",b);// 88
Label1.Text = string.Format("{0:0,,,}",a);// 0
Label2.Text = string.Format("{0:0,,,}",b);// 0
//"%"描述：格式为百分数
Label1.Text = string.Format("{ 0:0% }",a);// 1234567800%
Label2.Text = string.Format("{ 0:#% }",b);// 8765432113%
Label1.Text = string.Format("{ 0:0.00% }",a);// 1234567800.00%
Label2.Text = string.Format("{ 0:#.00% }",b);// 8765432112.54%
//"abc"描述：显示单引号内的文本
Label1.Text = string.Format("{0:'文本'0}",a);// 文本12345678
Label2.Text = string.Format("{0:文本0}",b);// 文本87654321
//"\"描述：后跟1要打印字的字符，也用于转移符\n等
Label1.Text = string.Format("\"你好！\"");// "你好！"
Label2.Text = string.Format("[url=file://\\c\\books\\new\\we.asp]\\c\\books\\new\\we.asp");//\c\books\new\we.asp
//"@"描述：后跟要打印字的字符,
Label1.Text = string.Format(@"""你好！"""); // "你好！"要打印"则需要输入两对才可以
Label2.Text = string.Format(@"\c\books\new\we.asp");//\c\books\new\we.asp

这次比赛成绩比预期差

开始Ultramanhu调整IDE

Q Boy从头开始看题

我的任务是倒数看题，最后看的题目是J，I，H，G

我看完J觉得J可做（哈密顿回路），但是需要很长时间。就首先放着继续看题

这时候Q Boy看完A提，觉得A题诗简单的图论，就交给Ultramanhu敲代码了，我大致想了一下J题的思路就开始看H题

树状数组模块

ACM个人模板

POJ 2155 题目测试通过

/**
 * 树状数组模块
 * 下标从0开始
 */
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;

//2^n
DG_Num LowBit(DG_Num n)
{
    return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
    return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
    return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran &sum)
{
    sum += *(g + pos);
    if(pos >= LowBit(pos + 1))
        DGFind(g, pos - LowBit(pos + 1), sum);
}
//查找对应线性数组元素
//参数(树状数组[in],索引[in]).
//返回值:对应线性数组元素log(n)
//复杂度:log(n)
DG_Ran DGFindEle(DG_Ran *g,DG_Num pos)
{
    DG_Ran a = 0 , b = 0;
    DGFind(g, pos, a);
    if(pos)
    {
        DGFind(g,pos - 1,b);
        return a - b;
    }
    else
        return a;
}
//树状数组,增加节点
//参数:树状数组[out],原数组大小[in],新增线性数组值[in]
//复杂度:log(n)
DG_Ran DGAdd(DG_Ran *g,DG_Num n,DG_Ran val)
{
    *(g + n) = val;
    DG_Num a = n;
    DG_Num b = 1;
    while((a & (~b)) != a)
    {
        *(g + n) += *(g + a - 1);
        a &= (~b);
        b <<= 1;
    }
    return n + 1;
}
//构建树状数组
//参数:线性数组[in],数组大小[in],树状数组[out]
//复杂度:nlog(n)
DG_Ran DGCreate(DG_Ran *g,DG_Num n,DG_Ran *tg)
{
    DG_Num i;
    *tg = *g;
    for(i = 1 ; i < n ; i ++)
        DGAdd(tg,i,*(g + i));
    return n;
}
//修改指定位置值
//参数:线性数组[in],数组位置[in],数组大小[in],新值[in]
//复杂度:log(n)
DG_Ran DGEdit(DG_Ran *g,DG_Num pos,DG_Num n,DG_Ran val)
{
    DG_Num f = DGFather(pos);
    DG_Ran o = *( g + pos );
    *( g + pos ) = val;
    if(f < n)
    {
        DG_Ran fv = val - o + *( g + f );
        DGEdit(g, f, n, fv);
    }
    return n;
}

//树状数组的翻转(树状数组的应用)
//一维  复杂度log(n)
//小于等于指定位置的元素的翻转<=pos
void DGDown1(DG_Ran g[],DG_Num pos,DG_Ran av)
{
    while(pos >= 0)
        g[pos] += av , pos = DGBrother(pos);
}
//获取位置pos的元素翻转次数
DG_Ran DGCUp1(DG_Ran g[],DG_Num pos , DG_Num n)
{
    DG_Ran t = 0;
    while(pos < n)
        t += g[pos] , pos = DGFather(pos);
    return t;
}
//二维  复杂度(log(n))^2
//小于等于指定位置的元素的翻转(0,0)->(x,y)
void DGDown2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y,DG_Ran av)
{
    while(x >= 0)
    {
        DG_Num tmp = y;
        while (tmp >= 0)
        {
            g[x][tmp] += av;
            tmp = DGBrother(tmp);
        }
        x = DGBrother(x);
    }
}
//获取位置(x,y)的元素翻转次数
DG_Ran DGCUp2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y , DG_Num n)
{
    DG_Ran t = 0;
    while(x < n)
    {
        DG_Num tmp = y;
        while (tmp < n)
        {
            t += g[x][tmp];
            tmp = DGFather(tmp);
        }
        x = DGFather(x);
    }
    return t;
}

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3398

题目要我们计算1，0的排列方式总数，并且对任意长的字符串，1的数量大于等于0的数量

我们可以把题目转化为从（0，0）点到（m，n）点的方法总数，且路径不经过y=x-1这条直线

然后我们可以把从（-1，-1）到（m，n）的所有路径按以y=x-1翻转，所得到的路径显然就是经过y=x-1的所有方案

/**
 * 线性筛法求素数表
 * 复杂度: O(n)
 */
const long MAXP = 1000000;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))
                break;
        }
    }
}

线性筛法,即是筛选掉所有合数,留下质数

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3400

这题就是一道简单的两重三分

首先设e点为从ab上离开的点，f为从cd上进入的点

显然对固定点e,f从距c的距离的长度是一个单调函数或者先减后增的函数，这里可以三分算出最优解。这里是第一个三分

然后对e点的最优解易证也存在这个性质，所以再来一个三分，就能解除最优解

又是我们的OJ

题目链接：

http://www.cn210.com/onlinejudge/problemshow.php?pro_id=92

Description

tancu likes space travels but he is a poor software developer and will never be able to buy his own spacecraft. That is why he is preparing to steal the spacecraft of Petru. There is only one problem - Petru has locked the spacecraft with a sophisticated cryptosystem based on the ID numbers of the stars from the Milky Way Galaxy. For breaking the system Stancu has to check each subset of four stars such that the only common divisor of their numbers is 1. Nasty, isn't it? Fortunately, Stancu has succeeded to limit the number of the interesting stars to N but, any way, the possible subsets of four stars can be too many. Help him to find their number and to decide if there is a chance to break the system.

http://www.cn210.com/onlinejudge/problemshow.php?pro_id=98

我们的OJ

Description

We say that a set 

$$S = {x1, x2, ..., xn}$$

is factor closed if for any xi ∈ S and any divisor d of xi we have d ∈ S. Let’s build a GCD matrix (S) = (sij), wheresij = GCD(xi, xj) - the greatest common divisor of xi and xj. Given the factor closed set S, find the value of the determinant:

Input

The input contains several test cases. Each test case starts with an integer n (0 < n < 1000), that stands for the cardinality of S.  The next line contains the numbers of S: x1, x2, …, xn.  It is known that each xi is an integer, 0 ≤ xi ≤ 2*109.  The input data set is correct and ends with an end of file.