歇了好几个月的blog终于重见天日了。时间总是过得如此之快，一眨眼，3个月就这么过去了，期间发生的事情太多太多，而我又突然变得又忙又懒……于是，悲剧就这样产生，很多事情，我已然不是记得很清楚了。

然而我总是该写些什么的。

本来不想把这里变成一个技术blog的啊啊啊啊啊啊~~~

好了，言归正传。

下周开始星期一、二、四Training， 星期一老队员讲课，星期二老队员打code，星期四老队员Seminar。 这个暑假我负责讲DP……DP……一个又爱又恨的东西……

昨天敲定了这些事情，接着Gary讲了一道SRM470 D1 500的题目。

题目在这:http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153

一道关于概率的题目……不由得让我想起了327的final，最后就差一个概率题没做出来，不由得感叹数学是多么的重要。（这是后话）

题目的大概意思是说，有上下两排点，分别由N个，我现在告诉你其中一些pair已经连起来了，还有剩下的没有连起来的点随机的组合相连，问得是这N个pairs相交的数量的期望是多少。注意题目说的是Number of Crosses, 不是Number of intersection points。 所以不需要考虑交于一点的可能。

然后……这个题目该怎么做呢？

我们知道期望是线性关系的，所以可以拆分……Totally我们一共有N条线，对于其中任意的两条，假设叫line X 和 Y。（且line X 的top point index 小于line Y的index），那么我们的总期望就是每一个这种pair的期望的和。对于line X 和 Y，一共有4种可能。 两条都是fix的，两条都不是fix的，X是fix的而Y不是，Y是fix而X不是。对每种情况都可以计算。

1）对于两条都fix的，那么就直接判定它们相交与否。top[i]<top[j] && bottom[i]>bottom[j]

2）对于两条都不fix，期望是0.5。这个需要推算一下，应该不难，用CTLi的话说，应该好直观= =||

3）对于一条fix一条不fix的，统计下相交的点的数目再算出概率就行。

贴贴代码……这是O（N^2）的算法，ZQ有O（m^2）的算法，就不是挨个统计而是集体算= =||对于N很大的话可以瞬秒

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10005
#define clr(a) memset(a,0,sizeof(a))
class DrawingLines{
	public:
	double countLineCrossings(int n,vector up,vector down)
	{
		bool top[maxn],bottom[maxn];
		int  sa[maxn],sb[maxn],match[maxn];
		double ans=0;
		clr(top); clr(bottom); clr(sa); clr(sb);
		for(int i=0;imatch[j]) ans+=1;
				}else
				if(!top[i]&amp;&amp;top[j]) {
					ans+=((double)(n-match[j]-up.size()+sb[match[j]]))/(n-up.size());
				}else
				if(top[i]&amp;&amp;!top[j]) {
					ans+=((double)(match[i]-sb[match[i]]))/(n-up.size());
				}else {
					ans+=0.5;
				}
		return ans;
	}
};