我在哪？是LBS领域首先要解决的问题。因为技术限制，传统的GPS卫星定位只有室外的空旷地区才能够准确定位，对于室内环境来说，GPS定位往往会因“搜星”失败而无法定位。正因为GPS定位的天然缺陷，基于手机基站的定位技术正在蓬勃发展。然而因为基站的覆盖范围大，很难以取得高精度的效果，本文利用基站轨迹，提出了一个提高基站定位精度的方法。

关键字：基站定位，轨迹定位，Viterbi算法

绪论

对于单基站定位，如果仅根据用户当前的基站ID进行定位，精度必定有限。用户可能出现在基站覆盖范围内的任意一个地方，基站的覆盖范围越大，推测出来的用户位置就越不准。
如果我们还知道用户之前一段时间内经过的基站ID序列（称为基站轨迹），此时即可大致判定用户行动轨迹，可借此提高精度。
例举一个简单例子:

如上图所示，假设用户在一瞬间，基站ID从A切换到了B，此时用户属于B基站，单单从B这一个基站考虑的话，很难从其巨大的覆盖圆内取出精准位置。
但是从假设条件我们知道，用户之前一直是在A基站范围内，切换到B基站只是刚刚发生的事情，通过这个条件，人很容易就想到用户很大可能在两圆相交的位置（图中手机的位置）。当然，对于这种特殊情况来说，不光是人，程序也很容易去模拟，但是如果用户继续行走呢？比如一直走到B基站的右侧，还有算法可以继续推算吗？
本算法便是提出一种模型，用以解决此问题。

隐马尔可夫链模型(HMM)与Viterbi算法介绍

隐马尔可夫链作为一个常见的序列预测模型，其具体定义在这里就不细细展开了，有兴趣的用户可以到wiki上搜索相关资料。此模型已经在多个计算机场景中得到了成功的应用，比如拼音输入法中，我们输入”wo zai bai du da sha”，实际想输入的是“我在百度大厦”，也就是说其中有两个序列、一个是拼音字母序列（明序列），一个是汉字序列（隐序列）。两个序列之间有一定的相互关系，如何通过一个已知的“明序列”来推测另一个未知的“隐序列”便是隐马尔可夫链模型要解决的问题。本文的重点也是如何用隐马尔可夫链模型解决轨迹基站定位。

解决隐马尔可夫链问题中的一个著名算法是Viterbi算法。建议读者先去阅读wiki中的Viterbi算法介绍，里面有一个简单的天气的例子详细说明了该算法的大体过程。：

http://en.wikipedia.org/wiki/Viterbi_algorithm

算法细节

隐马尔可夫链模型

我们知道隐马尔可夫链中有两个序列，一个是明序列（A1、A2、A3……），一个是隐序列（B1、B2、B3……）。在本模型之中，明序列（A1、A2、A3……）代表了用户经过的基站序列，隐序列是用户的实际位置序列。我们要做的是通过基站序列，来推测用户的实际位置序列。

首先，我们做如下假设：

● 用户行使在道路上。

●用户在匀速的行驶。

有了这两个假设，再把道路分解成一个一个的路段，我们便可以用路段序列来代替用户的位置序列。也就是说，我们需要通过观察到的用户基站序列，来推测用户的路段序列。如下图所示，我们观察到的是用户所经过的基站覆盖圆情况，需要求得的是用户的路段行驶轨迹。假设观察到基站轨迹是图中的绿色基站，那很明显用户最大可能是沿着红色箭头在行走。

Viterbi算法

如果要用Viterbi算法来解决本应用，只要知道如下几个问题即可。

路段的定义：将路网数据每隔10m抽象成一个有向线段，并且假设用户在这些路段之间离散的跳跃，每一个有向线段，即为一个路段。并且在这里假设用户将要跳跃到的路段只和当前路段相关，与过去的路段无关。

基站序列的定义：每秒钟检测其所处的基站，并且做记录。比如记录信息为（基站A、基站B、基站B、基站C），则表示用户在四秒钟的时间内分别属于基站ABBC三个基站，并且在B基站待了2秒。

路段序列定义：如果用户能够每秒钟记录其所属的路段，这个序列便是路段序列，这是用户的真实位置序列。

路段从属于基站的概率：Viterbi算法中需要知道隐状态从属于明状态的概率，拿到本应用中来看，便是要知道路段从属于基站的概率。解决此问题有如下两个方法：

1.根据路段在基站覆盖圆的具体位置来调整概率，比如，距离基站覆盖圆中心越近，则从属于此基站的概率越大。

2.根据真实的用户数据来推算概率。此方法最准确，其原理也简单，根据用户的真实位置（GPS点）变可以知道用户处于的哪个路段，也就知道了这个路段曾经属于过哪些基站，以及其概率。

如果有用户的真实数据，那么采用方案2无疑是最好的，但是没有数据的情况下，用方案1也可以最大可能的模拟。

路段之间的转移概率：路段之间的转移概率是本算法的重点，在这里做如下定义：假设路段A指向了路段B和C，那么从路段A转移到B和C的概率分别是33%，也就是概率等分，请注意路段A能转移到自身，其到自身的概率也是33%。

Viterbi算法大体过程

Viterbi算法过程是在各个路段之间进行概率转移。如下图所示，用户的基站序列为ABBC,则需要进行三(n-1)次概率转移过程。

对于基站序列ABBC来说，需要分成以下几步：

1.求得每一个路段的初始概率，即各个路段属于基站A的概率。

2.进行第一次转移，从基站A到基站B。比如路段A转移到路段B的概率为：路段A的概率×两个路段的转移概率×路段B属于基站的概率。

3.重复过程2，再转移两次，分别为 基站Bà基站B  基站Bà基站C。

4.最后取出概率最大的路段即为用户位置。

有心的读者可能已经看到，路段之间转移概率的定义是一个路段只能转移与其相连接的路段，这样有一个问题便是，按照上述算法可能所有路段的最终概率均为0。这是因为我们假设在时间间隔内，用户只能从一个路段行驶到相邻的路段，然而实际情况下，用户的速度可能较快，在我们扫描基站的间隔内，用户能跨越多个路段。对于这个问题，我们需要根据用户的速度来对用户扫描到的基站序列进行修复，比如速度是我们假定速度两倍的用户可以将基站序列ABBC变换成AABBBBCC。用户的速度可以通过速度传感器或者基站轨迹进行大概的推算，比如用户经过了10个基站，将这10个基站的覆盖圆中心连接起来，用总长除以时间，即为大概的速度。

算法效果

作者在实现本算法之后，对于匀速运动的定位用户的定位精度提升了一倍之多。对于一些特定用户，更是能明显的起到优化作用，比如高速公路上的用户，基站覆盖半径大，没有用本算法的话，只能返回巨大基站覆盖圆的中心给用户，定位精度极差。采用本算法之后定位精度会得到极大的提高，甚至用户的定位点丝毫不差的跟随用户的真实走动而走动，这也是因为在高速公路上路网比较简单，此算法效果会更突出。

没想到后来居然成了百度校招的笔试题，早知道我就出的有新意一点了，也不枉费那么多去笔试的人的时间。不过我感觉百度也不怎么在乎笔试成绩，基本上还是看面试结果。我估计好多面试官都没看过笔试题。

第一题  简答（30分）

1.  请写出C++ STL中vector的相关问题。（20分）

(1)在调用成员函数push_back时，其内部的内存分配是如何进行的。（5分）

(2)调用成员函数clear时，内部是如何具体实现的，如果想将其内存释放，该如何操作。(15分)

答题要点：

1、当vector发现预先分配的内存不够用时，会申请一个大小为当前内存更大的地址，并把数据拷贝到新地址中。

2、在调用clear时，vector并不释放内存，只是在内部做一个“空”的标记。如果想释放内存可以参考如下方法:

vector<int> ver(n,0);//需要释放掉的vector

vector<int>().swap(ver);（这样便可释放ver的内存）

2. 请指出下面C语言中foo函数的问题，此函数想统计字符串中的字母a-z分别出现的个数。（10分）

void foo(char a[100], int cnt[256]) {
    memset(cnt, 0, sizeof(cnt));//sizeof(cnt)在这个时候是指针的大小，32位系统中永远等于4。此问题给5分
    while (*a != '\0') {
        ++cnt[*a];//因为有中文，所以这里*a可能为负数，会越界。指出问题给5分
        ++a;
    }
    for (char c = 'a'; c <= 'z'; ++c) {
        printf("%c: %d\n", c, cnt[c]);
    }
}
int main() {
    char a[100] = "百度abc";
    int cnt[256] ;
    foo(a, cnt);
    return 0;
}

第二题 算法与程序设计（40分）

1. 假设我们有rand(s, t)函数，可以返回[s,t]之间的随机小数。请问如何利用该函数在一个半径为R的圆内随机n个点，并给出相应的时间复杂度分析。（15分）

参考答案：

假设一个边长为2R的正方形把圆包住，那么可以调用rand(s, t)函数两次得到正方形内的随机点(x, y)。留下在圆内的随机点即可,这样可以保证随即概率相等。时间复杂度可以按照圆和正方形的面积比得到:

O(n*(πR^2)/4R^2 )=O(n* π/4)

也可在极坐标下通过线性随机θ得到角度，随机R*sqrt(rand(0,R))得到R。不过概率分析会略微复杂一些，关于此类问题，我准备近期专门写一个blog记录，包括在圆内随机点，在简单多边形内随机点等等。

2.  为了分析用户的行为，系统往往需要存储用户的一些query，但是因为query非常多，所以系统不能够存下每一条。假设我们的系统每天只能够存储m个query，现在需要设计一个算法，对用户时时请求的query进行随机选择m个，请给出一个方案，使得每一个query被抽中的概率尽量相等，也请附加相应的分析。需要注意的是，不到最后一刻你并不知道用户的总请求量是多少。（25分）

参考答案:

假设每天总共有n个query，那么目标是使得每一个query被抽中的概率为m/n。

系统设计如下：

1.  开一个大小为m的数组K，前m个query分别依次放入数组K[0..m-1]中。

2.  假设当前的query为第p个（p>m），随机一个[0-p)的整数i，如果i<m，则K[i]=query[p]，否则弃掉该query。

概率分析：

首先分析最后一个，也就是第n个query。其被抽中的概率=其随机数i小于m的概率，也就是m/n。再分析第n-1个query的概率。该query放入数组的概率为m/(n-1)。其没有被最后一个query替换的概率为(n-1)/n。所以第n-1个query被抽中的概率为m/(n-1)*(n-1)/n=m/n。

依次类推，第n-2个query被抽中的概率为m/(n-2)*(n-2)/(n-1)*(n-1)/n=m/n。

即：每一个query被抽中的概率均为m/n。

第三题 系统设计题（30分）

现在有一个“服务器-客户端”的实际系统。正常的客户端每1分钟最多发送一条请求到服务器，服务器需要做一个异常客户端行为的过滤系统。假设服务器在某一个时刻收到了客户端A的一条请求，那么1分钟内的客户端的任何其他请求都需要被过滤。现在知道每一个客户端都有一个IPv6的地址可以作为其ID。客户端个数太多，以至于无法全部放到单台服务器的内存hash表中。现在需要简单设计一套系统，使得支持高效的过滤，可以使用多台机器，但要求使用的机器越少越好。请把关键的设计和思想用图表和代码的方式表现出来。

参考答案：

虽然客户端的ID太多，无法放入到内存中，但是1分钟内请求服务器的ID却不会太多。可以根据这个条件进行设计。

申请队列Q, hash表H。H记录了每一个请求的到达时间。服务器收到请求之后：

While (队首的ID请求到达时间超过1分钟)

出队，并且清空hash表H中的相关记录

If     客户端ID存在于H中then

过滤此请求。

else

将此ID放入Q队尾

记录时间到H中，即H[ID]=now()。

另外还有一些开放的设计方法比如简单分布式设计、文件索引、等等

拿第0关来说：

其中有四个方格，A00、A01、A10、A11。初始状态中A00和A01是灯灭的状态，A10是灯亮，A11是障碍。游戏的规则允许在所有的非障碍格子上进行点击，其中每一次点击都会使得相同行和相同列格子的状态进行反转（亮–>灭，灭–>亮）。障碍物不可点，并且会阻挡状态反转的传递。游戏的目标是使得所有的非障碍物格子都点亮。

要解决这个问题，首先要看出一个显然的推理：

每一个格子所有的偶数次点击相当于点击了0次，所有的奇数次点击相当于点击了1次。

因而我们只需要考虑是否点击某一个格子，而不用关注起具体的点击次数。

对于上图来说，列举方程如下：

1 * A00 ^ 1 * A01 ^ 1 * A10 ^ 0 * A11 = 1（对应于格子A00，需要点亮）

coil这个问题类似于一笔划，虽然人工玩起来不咋地，但是其算法设计是我所看过的题目中最有意思的一个。这个问题明显没有多项式解法，估计解决思路也就只能暴力搜索+乱七八糟的剪枝。

我印象中我主要加了下面几个剪枝：

• 对搜索的起点进行估值，也就是排一个优先级，觉得搜出答案可能性高的先搜，可能性低的后搜。
• 在搜索的过程中按照一定规则进行分块，每一个块内部包含若干个小格，对各个块重新进行构图，这样极大的缩小了整个问题的范围，直接在新图上进行嵌套的搜索，如果发现搜索不到解，则可剪枝，需要继续在当前分支上继续搜索。用此优化，大部分搜索步骤都会被剪掉。
• 分块之后，有一些简单的规则可以直接判断是否无解，比如某一个块只有一个出口，则这个块之中要么包含起点，要么包含终点，也就是说这样的块只能是0个或者2个。
• 在分块过程中如果发现某一个小块内部如果是无解的，则可剪枝。

需要注意的是，这个问题天然支持分布式计算，也就是说对于一个搜索的起点，起一个单独的线程或者进程即可单独运算，不同的起点完全是独立的。

我当时是用C#写了一个大概1000行的程序，因为是用一个单核的破电脑跑的，所以也没有起多线程，大概运行了几天跑了273关，当时还在前十名来着，现在已经很往后了。后面我想用C++重新写一遍，不过看到那么长的代码，一直没有鼓起勇气重写。因为小函数的递归太多，C#的效率最终成为了一个瓶颈，所以我感觉着用C++重写，用上多线程和服务器来跑的话，我当时用的算法优化应该至少能超过300关。

后续我准备把这个问题重写一遍，现在我可以用公司的服务器来跑，所以一些限制可以放开，比如可以用大内存进行hash..特别是分块之后对每一个小块进行单独判断的时候，hash应该能有大的潜力。

加上实习，工作也有两年多了，除了工作之外，花在gReader、weibo、dota、sanguosha上面的时间还真不少，这几个活动，我觉着吧，最大的特点就是不用动脑。用脑这个事情还真是越不用就越懒，以前身边的同学都在玩dota的时候我还坚持去网上训练我的魔兽、星际对战等等搞高强度对抗性的脑力活动，现在也沦落到无脑打钱流的dota了。就dota而言，以前我还喜欢都只玩一些比较需要操作和意识的法师等英雄，现在基本上第一首选的是dps，前期无脑打钱，后期无脑杀人或者被杀。。

是时候该改变这种状态了，廉颇老矣，尚能饭否？

原题就是给一个数组，然后询问一段区间内的第K大数。。。

发信人: mmd (mmd), 信区: ACM_ICPC
标  题: F题解题报告
发信站: 珞珈山水BBS站 (Tue Apr  1 12:10:07 2008), 转信

解题报告:

F题:

先说一下n log(n)预处理, log(n) ^ 3查询的方法

线段树中的节点不是存的点, 是存一条线段.(也就是很多点, 个数是这条线段的长度)

线段树中的节点是有序的, 序是按key排的.

结构跟归并排序里面的一样的.

这样可以用合并两个有序序列, 来建树, 很明显, 建树的复杂度是n log(n)的.

这样的一个数据结构, 很明显我们是可以查找一个区间中的一个数在有序表中的哪个位
置.

我们如果要找第k个数话, 便可以对这个数进行二分, 然后在区间中查找.

这样总体复杂度应该是n log(n) + log(n) ^ 3

这个方法很明显是非常慢的,.

因为首先要有一个二分, 这个复杂度就比较高, 因为数据是可以无限大的(可以通过离散
化来减小数据范围, 但显的不够优美)

第二要在线段树中对线段进行分割, 麻烦, 常数也比较大.

第三这个线段树的实现比较麻烦, 代码较长, 也容易错.

下面说一下n log(n) + log(n)的方法

这个方法, 与上面所说的方法在数据结构上要有所改变

1.      线段树也是存的一条线段(很多点)

2.      线段树也是有序的, 但是是按position有序的(按在原来数组中的位置有序)

3.      线段树中左孩子节点的key要比右孩子的key小

想清楚这个数据结构后, 可以想一下如何在这种数据结构上进行操作

上面这种结构非常巧妙, 是我无意中看一个外国人说的, 看到这个结构后, 我加了以下
几个简单附加结构, 就可以对这个问题比较完美的处理了.

1.a[n], a[i]表示从1 到 i中有多少个节点在左子树

通过这个数组, 我们可以计算出一个区间s – t中有多少个节点在左子树, 有多少个节点
在右子树, 为什么有这个东西呢?

有了这个东西, 我们就可以对我们要查找的区间进行递归了, 并且每次只会递归到一层
中, 所以复杂度是log(n)的

有了这个东西, 问题就基本解决了.

但我们递归的时候, 区间是变化的, 我们应该如何去应对这个改变呢?

比较简单的方法就是进行一次二分, 但是这样复杂度就变成log(n) ^ 2的.

为了解决这个问题, 我再次对区间进行了记录. 也就是对区间记录一个映射, 记录这个
区间在左孩子中所对应的区间和在右孩子中所对应的区间.

这些记录, 都可以能过合并两个有序序列的方法来建树, 都是n log(n)的.

说到这里, 这个问题就比较完美的解决了, 这个方法常数比较小, 又是单层递归, 可以
写成迭代形式.

参考代码：

//author: momodi@whuacm
class Tree {
	public:
		static const int maxn = 100000;
		struct Seg {
			int s, t;
			struct Acc {
				int b, c, l, r;
			};
			Acc *acc;
		}seg[maxn * 3];
		int n;
		int *dt;
		int id[maxn];
		void init(int _n, int *_dt) {
			n = _n;
			dt = _dt;
			for (int i = 0; i < n; ++i) {
				id[i] = i;
			}
			sort(id, id + n, cmp(dt));
			build(0, n, 0);
		}
		int find(int s, int t, int k, int v = 0) {
			if (s + 1 == t) {
				return dt[seg[v].acc[s].b];
			}
			int tmp = seg[v].acc[t - 1].c - ((s > 0)? seg[v].acc[s - 1].c: 0);
			if (k <= tmp) {
				return find(seg[v].acc[s].l, seg[v].acc[t].l, k, v * 2 + 1);
			}else {
				return find(seg[v].acc[s].r, seg[v].acc[t].r, k - tmp, v * 2 + 2);
			}
		}
	private:
		struct cmp {
			int *dt;
			cmp(int *_dt):dt(_dt){};
			bool operator () (const int &a, const int &b) {
				return dt[a] < dt[b];
			}
		};
		void build(int s, int t, int v) {
			seg[v].s = s;
			seg[v].t = t;
			if (s + 1 == t) {
				delete seg[v].acc;
				seg[v].acc = new Seg::Acc[2];
				seg[v].acc[0].b = id[s];
				return ;
			}
			int m = (s + t + 1) / 2;
			build(s, m, v * 2 + 1);
			build(m, t, v * 2 + 2);
			merge(seg[v].acc, seg[v * 2 + 1].acc, seg[v * 2 + 2].acc, t - s, m - s, t - m);
		}
		void merge(Seg::Acc *&d, const Seg::Acc *l, const Seg::Acc *r, int n, int ln, int rn) {
			delete d;
			d = new Seg::Acc[n + 1];
			d[n].l = ln;
			d[n].r = rn;
			for (int i = 0, li = 0, ri = 0; i < n; ++i) {
				if (ri == rn || li < ln && l[li].b < r[ri].b) {
					d[i].c = ((i > 0)? d[i - 1].c + 1: 1);
					d[i].l = li;
					d[i].r = ri;
					d[i].b = l[li++].b;
				}else {
					d[i].c = ((i > 0)? d[i - 1].c: 0);
					d[i].l = li;
					d[i].r = ri;
					d[i].b = r[ri++].b;
				}
			}
		}
};
Tree tree;
const int maxn = 100000;
int dt[maxn];
int main()
{
	int n, m;
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; ++i) {
			scanf("%d", dt + i);
		}
		tree.init(n, dt);
		while (m--) {
			int s, t, k;
			scanf("%d %d %d", &s, &t, &k);
			printf("%d\n", tree.find(s - 1, t, k));
		}
	}
    return 0;
}

比赛前一天：

本来是想周六中午BG大家的，结果发现了浙江理工在下沙之后就知道中午来不及BG了，所以改到晚上。晚上的湘菜馆还是挺不错的，虽然我感觉不够辣。。吃饭的时候看大家的状态都不错，都挺Happy的。

周六下午热身赛的时候，Dumbear问了我一句：“我们的比赛策略是什么？”

听到这个问题之后，我顿时感觉大脑空白了几秒。

思索了良久这个问题的答案，回想起了以前在ChaeYeon队伍的时候制定的种种策略，比如赛前要制定表格，说好每个人的读题顺序，想好卡题了怎么办，碰到什么类型的题目让谁做，谁负责主要读题，谁负责帮队友debug等等等等。

在回想完这种种之后，不知道为什么感觉这些策略都不值得提出来，于是跟Dumbear说:“到时候看情况，该怎么样就怎么样吧。”

不过虽然没有继续讨论“策略”这个问题，我仍然在那里静静的思考了良久，或许真正的策略便跟武侠里面一样“重剑无锋，无招胜有招”。

周日上午九点，比赛正式开始了：

简单题H和A：

Dumbear和ISea开始读题。这时候我把每一个题目都扫描了一下。为什么要这么做呢？

这还需要从出题说起，自从去年开始大量出题之后，自我感觉上我对比赛的一些细节问题有了一些很新的认识。比如：一般来说这种强度的邀请赛都会有一个sb题来保证每一个队伍都至少AC一道题。而这种SB题是字符串处理的概率很大，因为字符串处理题好出-.-

在寻找了一圈样例里面有字符串的题目之后，我选中了H，运气挺好的，H确实是一个足够简单的题目。

我在上机的时候Dumbear还问了我H是什么类型的，本想解释一番的我想到Dumbear可能是怕这个题目不够简单，怕我太急了。所以我随口回复了“H是A+B类型的题目。”

AC了H之后Dumbear上来AC了A题。这时候差不多是9点30分，也就是说比赛经过了半个小时了。我猜想接下来的题目应该就没有A和H那么简单了，没想到的是剩下的题目难度也都不大。唯一的压轴难题确是我们几乎没有可能做出来的题。

计算几何D题：

我在写H题的时候就听Dumbear和ISea在讨论有一个简单的计算几何，DumbearAC了A之后我便上机开始敲这道几何题（D题）。计算几何写完之后有个小插曲，就是不知道为什么有一个泛型的函数编译通过不了。在询问了ISea和Dumbear之后，他俩也表示不知道。于是我果断停止在这里纠结，换了一种写法。编译通过并且过了样例之后，我又盯着代码看了一会，继续回想了一下是不是有特殊情况。这时候ISea问怎么样了，我答：“可以交了”。Dumbear附和了一句“交吧，感觉momo这题写的挺仔细，应该没问题。”听到这句话我小小的惊讶了一下，为什么Dumbear会知道我写的很仔细呢？

D题1Y。

状态压缩DP题 B和数据结构题F：

ISea很早就说了B是一个简单题，不过因为题目里面要牵扯到棒球的规则，所以ISea在跟我讲这个题目意思和做法的时候，我只是听了一个大概。不过我还是挺相信ISea的，所以我也就没有追求这个题目的细节，跟ISea表示了一下问题不大后，ISea也是直接去写了。

而后Dumbear跟我讲了讲F题题意以及RMQ的做法。我知道题意之后发现此题就是求一个数列中每一个数的左右两边边比他大的第一个数。这个问题的解法我很早就知道了，代码也很短，所以先把ISea从机器上拉了下来，换我上去AC了这道题。

而后ISea也1Y了状态压缩的B题。

乱搞题I：

接下来ISea和Dumbear讨论了一下I题后发现了其“简单题”的本质，不过这中间有一点点冲突：ISea有一个优美的方法，而Dumbear想直接去暴力模拟。最后Dumbear去用ISea的优美方法写的，可惜的是WA了两次也还没有AC。这时候Dumbear和ISea又再次重新读题，在确保了题意理解无误的情况下，Dumbear没办法换了他原来准备的暴力模拟的方法AC了I题。回想此题，最好的情况应该是Dumbear一开始就写最保险的暴力模拟方法。不过在出问题之后Dumbear能够顶住压力重写代码，还是很赞的。

图论+树形DP题E：

E题样例里面输出的是小数，也就是说E题是两种题目可能性最大：几何题或者概率题。这两种不同类型的题目对我来说完全就是两个极端，每次碰上样例输出小数的题目我都是爱恨交加。

我在读完题之后，悲剧的发现是概率题。

在I题的解决过程中，我仔细的研究了一下E题，发现与概率关系不大，在跑完最短路之后只要两边BFS就可以了。不过因为场上还没有提交这个题目，所以我们也并没有急于去写这个题目。后来在跟Dumbear讲解这个题目的题意和做法的同时，我更加确信这个题目的做法没错。所以做法也没有讲完，我就直接上机去写这个题目了。

写完之后WA了一遍，不过我马上意识到了错误的地方（图有可能不联通），因为这个地方在我刚开始写的时候考虑到了，中间因为I题被打断了一次，竟然所以把这个Trick给忘记了。改过之后E题2Y。

需要转弯的矩阵乘法题G：

在Dumbear写I题的时候，我和ISea一直在思索G题的做法，可惜一直没有找到正确的方向。后来经Dumbear提醒才恍然大悟，原来可以改成递推式用矩阵乘法解决。ISea去写了G。因为还有很长时间去写这个题目，所以我们有足够的信心G题肯定能AC。J题AC之后就是剩下最后一题J了。

压轴题J：

此题是浙江省赛的一个变形，这个题对我们来说是一个很大的悲剧，因为浙江省赛的时候是我们校赛决赛的练习赛，Dumbear和ISea是在参赛，我是在出题，所以没有一个人在当时对这个题有细细的研究。不过因为知道这个题目是一个难题，所以我们前期并没有浪费时间在这个题目上。最后还有一个多小时没事做的情况下，我们才开始细细的推导这道题。

当时有两个思路：

1. 先用强连通分量来判断是不是无解，求这个图的圈覆盖，而后试图把圈合并。

2. 先用强连通分量来判断是不是无解，然后搜索答案。

第一个思路我感觉是比较接近最终答案的，但是因为就连最初的假设“存在哈密顿路的充分必要条件是整个图在一个强连通分量里面”都不确定是不是正确的，所以这个思路并没有发展成熟。

第二个思路比较简单，所以在没有办法的情况下，我去用这个思路试图“水了水”。得到的结果也是理所当然的TLE。在用了各种搜索技巧提交了几十次之后，比赛结束了。

最后的结果是浙大的队伍做出了J题，AK了所有的题目。

我们因为罚时排在了9题第一总排名第二，虽然有些小小的遗憾，但是终究还是输在了实力上，就算没有J题，也是只能第二名。

结束语：

能够和Dumbear和ISea组队很开心，赛后找了一个网吧10个人打Dota内战，大家在尽兴之后开始了此次比赛的结束之旅。

在回去的路上得知了另外两只6题的队伍，一个银牌第一，一个银牌第三。不过是因为输在题数上，所以我想也没什么特别的遗憾。

Dumbear和ISea在赛场上显得很老练，对各种问题的处理也很成熟。我想他们两个再加上我们的传奇人物，一定能够在赛场上取得辉煌的成绩。

虽然今年我们集训队相比去年来说有种种不足和问题，但是我相信今年区域赛我们还是会有更大的突破的。

大家加油～激情比赛，为了目标而奋斗到底：）

http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1004&cid=289

没啥特别意思的几何题。。做法就是双重三分，也就是三分里面套一个三分。

放在这里记录一下我的出题成果：）

突然发现，最近这一年我也狠狠的出了不少题了。从区域赛的出题到我们的校赛，再加上PKU和HDU的月赛加起来有几十道了。每一道题我都力求创新，绝不Copy陈题。。

想想出题最累的还是给区域赛出的题。。从最初组建了多人的出题委员会，到最后这个委员会只有我一个人。那个时候我相当囧迫，每天绞尽脑汁的想Idea想了整整一个暑假，好不容易凑出来十个题目。

虽然没啥经验，但是这十个题目还是整合了我参加acm这么多年以来的精华。我感觉挺不错的有两个：1. 原创了圆的面积并的算法。2. 完成了一个很复杂的但是却很有实际背景图论模型的建模（后来的决赛的I题）。

因为题目是我一个人出的，所以必然显得类型很偏门。不过我很奇怪的是为啥复旦的一些人那么愤愤不平，公然在校内上鄙视我们学校-.-（让我想起了多年以前也是复旦一队的成员公然跑到我们学校的OJ上说我们的OJ垃圾，骗代码。。）

预赛搞完了之后，和复旦的这件事好像搞的很多人都知道了，我们集训队也有很多人愤愤不平，跑到人家校内上有了开始对骂的势头-.-
没办法，为了不让事情搞大影响集训队的形象，我专门找到复旦的一个负责人，跟人家说明情况，并且对题目表示Sorry。。还好复旦也比较通情达理，都删掉了校内上的那些对话，一段往事就这样平息了。。

不过还是有点小小的无语。。我们都已经表示了决赛的题目不是我们出，预赛是因为经费问题所以才由我们自己出的。为啥有些人就不能宽容一点？还好当时正在研究佛法，我表示”忍了“，要是按照我以前的火爆性子，早就不知道啥样了。。

再后来看见有人用很不友好的言语在他的blog里面说我们学校公布的标程故意耍帅，故意不让别人看懂。。在表示无语的同时我也理解了一个道理，在做一些自认为是好事的时候，必然有一些人对你进行言语上的攻击，他们也不一定就是恶意，只是表示一下自己不爽了。。

F: Pie

此题很明显的是一个最小匹配的模型。而后根据题目数据的特点可以利用DP来解决。

简单说一下性质：

1. 排序之后的匹配是不存在交叉线的。也就是说，如果第i高的男的和第j高的女的匹配，那么比i矮的男的就不能和比j高的女的匹配。同理，比i高的男的也就不能和比j矮的女的匹配。

2. 题目里有说男女的人数相差不到100，所以我们可以知道一个人的的可选匹配数量最多是100个。再加上这个性质，我们就可以用O(n * 100) = O(1000000)的DP来解决这个问题。相关的实现要用到滚存。

附上代码：

G: Precious

这个题说白了就是判断一个简单多边形内部的两个点是不是可见的。做法也很简单，可能大家都对几何不感冒，不是很愿意去做。

判断两个点是不是可见的做法：

1. 用两个点来做一个端点都是开的线段，然后和多边形求交点，如果有交点的话，那么就是不可见的。

2. 取这个线段的中点来看看这个点是不是在简单多边形内部，如果不在内部的话，那么也是不可见的。

满足上面两个条件的就都是可见的。

知道了任意两个点是不是可见的之后，建立一个图，然后跑一下最短路就好了。

代码：

H: Railway

题意就是边是属于无向图的0个环，1一个环，还是多个环。

这是一个利用双连通分量来求解的图论题。

把原来的图的双连通分量都求出来之后，判断每一个连通分量里面的点和边的数量的关系。

1. 点>边 那么这些边都是没有用的。

2. 点=边 那么这些边都是有用的。

3. 点<边 那么这些边都是会发生冲突的。

代码：

I: Special Fish

这题我觉得没啥意思。。凑数的。把一个点拆成两个点之后，建立一个模型，然后跑km就好了。

我在公司比较忙，这次出题，其他题目我基本都没有看题意。整体上是xay把握的，所以其他题目的分析我就不说啦。标程和数据过会应该xay他们会发到官方网站上。

从Rank上来看，题目出的有点难了。。虽然我感觉题目和预赛的差不多。。G和H都ac的这么少，实在是出乎意料。

B题xay在赛前跟我说是难题，结果ac的这么多。。

A题xay说是sb题，结果没啥人ac。。

G题我以为会有5-6个队伍ac的。。结果也不对

反正基本没有猜对。。

题目大意就是用下面的距离定义来求每一个点的最近点对。

Distance (A, B) = max (|Ax – Bx|, |Ay – By|)

这题是我最初给我们学校去年的区域赛准备的题目。说一下做法：对于每一个点，先二分答案，这样转化为判断是不是一个正方形内有点的问题。对于解决这个问题，用二维的线段树来解决。很多人对于二维线段树的理解就是把一维变成二维，空间复杂度从O(n)变成O(n^2)。其实不是这样的，复杂度为O(n^2)的线段树基本没有什么用处。

可以用变化一下的实现方法使得空间复杂度变成O(nlogn)。具体的实现方法可以参见我们学校的wiki上我贴的代码。

http://acm.whu.edu.cn/wiki/index.php/Point