在某个神奇的下午，收到一个垃圾邮件（至少被邮件系统当成了垃圾邮件）。

结果就一不小心看到了这个充满回忆的ACM模式竞赛，还有咱腾讯的，就忍不住看了一下。

果然好久没碰算法，脑子是会生锈的。

第一题大水，懒得写。

第二题伤了很久的脑筋，想出了一个算法结果ultramanhu基于此想出了个更容易理解更容易实现的方法。

以我这种懒人的本性，必须是也懒得写得。

今天心情好，刷了两到ACM水题，思路很简单都在注释里，所以直接贴代码:

/**
 * @file 龟兔赛跑.cpp
 * @brief 龟兔赛跑 AC代码 (DP)
 * DP方程式: [到第i的充电站的最短时间] = [到最后一个冲了电的充电站的最短时间] + [那个充电站到第i个充电站的时间]
 *
 * @link http://acm.hdu.edu.cn/showproblem.php?pid=2059
 * @version 1.0
 * @author OWenT
 * @date 2013.07.15
 *
 * @history
 *
 *
 */

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <numeric>

int pn[128];…

某个课程的作业，促使我来看看这玩意。

整个程序的算法思想是看别人的ACM的blog看懂的，感觉确实和KMP很像。但是代码呢就比较工程化一点。顺便回忆了一把ACM的感觉。

基本原理呢基于字典树，并增加了失败节点。

最初是接受了lpld的邀请来写这篇大总结。我没有LHH华丽的文笔，就只能随便写写了。回想起来，ACM应该是我在大学期间参加的最有意义并且收获最大的活动了。

记得我的计算机写代码还是从魔兽3开始，那个时候还在高中。在Dota还没风生水起的时代，大家都在玩各种RPG。我也在玩各种RPG，但是我是个没耐性的人，有些个RPG太难了，玩不过去，怎么办呢？我就去改地图玩，当时还研究了各种加密解密地图文件的小工具。再之后，改地图也不好玩了，就直接去论坛上学怎么做地图了。

2010.10.11

要为出发做准备了，今天和Ultramanhu和Answeror一起去买了火车票，真是搞笑了，提前六天去买票，竟然动车没坐票了，难道世博就这么猛？只有买周四晚上出发的非动车卧铺票了。顺便带个三国杀什么的去玩，不过估计去的时候也没什么心思玩，等回来的时候再用吧。
回来的时候Answeror推荐我们去吃大娘水饺，然后就去了，我买了半斤水饺，花了25.5块，这么贵，果然学校外面就是贵啊，不过挺好吃的。起码比学校里的好太多了，而且那个水饺很有分量。
今晚协议到线段树的题竟然效率和不用线段树的一样，气死我了，明天看看别人怎么写的，然后改，顺便看看二维线段树，再顺便复习一下树状数组。

2010.10.12

本来打算好好看线段树的，结果线段树的基本操作是会了，可是还是不熟，这个很麻烦啊。今天一定要吧线段树搞定，明天整理一些以前写过的东西车上看看。
好吧，今天我们去买回程票（防止买不到坐票），结果售票员告诉我们明天才能买，原来我们说的提前六天是(12, 18],官方的是[12,18)。这个郁闷了，不过售票员的态度让我很不爽。
今天…

1.RangeMinimum、Maximum Query问题（计算单调区间内出现最多（少）的次数）

对元素的起点做离散化，再把离散化后的位置作为线段树的[l, r),记录次数为t.

对输入区间a, b:

如果（a = b）{很好处理}，

如果（a = b – 1）{分别计算a、b的次数，取大（小）的一项}，

/**
 * 二维ACM计算几何模板
 * 注意变量类型更改和EPS
 * #include <cmath>
 * #include <cstdio>
 * By OWenT
 */

const double eps = 1e-8;
const double pi = std::acos(-1.0);
//点
class point
{
public:
    double x, y;
    point(){};
    point(double x, double y):x(x),y(y){};

    static int xmult(const point &ps, const point &pe, const point &po)
    {
        return (ps.x - po.x) * (pe.y - po.y) - (pe.x - po.x) * (ps.y - po.y);
    }

    //相对原点的差乘结果…

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 <stack>
 * #include <cstring>
 */
std::stack<char> opr;
std::stack<double> 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)…

基础函数:

// 最大公约数,欧几里得定理
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…

关于差分约束（转载）

（本文假设读者已经有以下知识：最短路径的基本性质、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 <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
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};…