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

结果就一不小心看到了这个充满回忆的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太难了，玩不过去，怎么办呢？我就去改地图玩，当时还研究了各种加密解密地图文件的小工具。再之后，改地图也不好玩了，就直接去论坛上学怎么做地图了。

好久没写这种类型的代码，感觉真是退步了很多。 这是我第一次参加Google Code Jam，以前有过报名可是没有做过。 我发现Google Code Jam的题目使用经典算法的几乎没有，都是模拟或者数学题（起码我目前做过的几题是这样）

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…

题目链接：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};…

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 =…

这次比赛成绩比预期差

开始Ultramanhu调整IDE

Q Boy从头开始看题

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

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

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