昨天下午，BUPT又举行了一场比赛。这场比赛难度要比上一次小不少。都是一些比较水的题目。下面就简单写一写我的思路吧。
A. 学姐的桌面
大水题。。。排序+二分， 没啥好说的
附源代码
B. 学姐去学车
通过手工模拟，我们可以发现教练给学姐是以n+1为周期的。不过前m天不在这个周期内。所以前m天特判一下，后面先减去前面不在周期内的天数，再mod(n+1)就可以判断这一是由谁来教了。
附源代码
C. 学姐的学弟
题目大意是给你n个圆，每个圆的圆心(xi,yi)都为整数点且半径为1，且1<=xi，yi<=100。求这些圆的面积并。
刚开始拿到这道题，感觉好复杂，果断跳过去做其他的。在把另外4题A掉之后才回来看，还是感觉好复杂……发现了一种O(n^2 log(n))的算法最终也没调出来。
赛后whn同学提醒:圆心都在整点且半径为1，且坐标范围在[0,101]*[0,101]!!我们可以发现对坐标网格中的每一个格子来说，它所贡献的面积仅与它四个顶点处有没有圆来决定，而且仅有四种情况，即0，满格，四分之一圆，以及两个四分之一圆相交。这样枚举网格就可以了。复杂度仅为O( n^2 )。
附源代码
D. BLOCKS
题目大意是给一个nxm的仅由‘.’、‘#’构成的矩阵，问矩阵中由‘#’组成的矩阵的个数。要求每个‘#’所在的联通块必须是一个矩阵，若不是则输出“So Sad”
一道简单的搜索题。或称之为洪水填充法(Flood Fill)。对这个矩阵扫一遍，发现有‘#’就进行bfs，同时判断它构成的是不是一个矩阵（粗心写错了好几发T ^ T）。
附源代码
E. 数的关系
题目大意是告诉你有n个数，问这些数共有几种可能的序关系。
这个题比较有意思。有一种做法是直接从数学角度找，具体可以参考这篇博文。
我的做法是，将每个序关系等价描述为一种小球放箱子的方案。所有画等号的数放到一个箱子中，每有一个’<’号，就将它后面的数放在一个新的箱子中，不允许有空箱子。即箱子数为小于号的个数加一。
设f[i][j]表示把前i个数放入j个箱子的方案数。考虑第i个数放入时，
有两种情况。
- 数i单独在一个箱子里，那么相当于先把前i-1个数放入j-1个箱子，然后将数i和它所在的箱子一起插进去，一共有f[i-1][j-1] * j种可能
- 数i所在的箱子中还有其它数，那么我们可以先将i-1个数放入j个箱子，然后把数i放入其中一个箱子，也就是说有f[i-1][j] * j种可能
那么，我们就可以得到一个这样的额动态规划算法：
- 初始化: f[i][1] = 1
- 状态转移方程:
f[i][j] = (f[i-1][j-1] + f[i-1][j]) * j - 目标函数:
f[n][1] + f[n][2] + …… + f[n][n]
时间复杂度为O( n^2 )。
注意使用高精度。
附源代码