Overview:

。。#3 的构造题都是比较简单的啦。。（C, E, H 。。。
.. 另外有两道很经典的图论 （B, D 。。。
… 当然最推荐的还是 A 题。。。

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=1231#overview

Problem A. Areas:
… 平面内给定 n 条直线，求封闭区域的个数以及它们的面积。
。。( n <= 80 .. 。。。 ———————— 。。。先求交点，之后对相邻的交点连边。（被同一条线段覆盖。。且中间没有其他交点隔开。。。。 。。那么封闭区域等价于平面图中的环。。那么以逆时针为轴。。为了分割出最小的封闭区域， 。。我们只要从任意边开始，每次往最里侧的位置旋转即可。。O(m) 时间即可解决这个问题。。。 。。。所以总的复杂度是建图的复杂度。。O(n^2logn)。。 。计算几何。。（80ms。。。
（注意代码这里我禁止向顺时针方向转移，如果允许。。那么会顺时针方向会多分割出一个包含所有这些极小封闭区域的大封闭区域。。

————————
(。。补充说明一下精度问题。。这个真是折磨死人了。。当然最可靠方法还是是用分数的形式保存每个 double。。。。
。。这样的话中间对每个算式除的地方都乘上来。。这样虽然安全有效但是改累死了。。。
。。。后来发现其实别的地方有 bug 而已。。总之生卡精度的题其实还是没有的吧？。。。WA 的话可能还是别的其他的地方写疵了。。

（。。删去第721行可 AC。。（？？？。。。

Problem B. Beloved Sons:
匈牙利算法（120ms +-..

Problem C. Strange Counter:
。。构造 -> 不变式。。

Problem D. Data Transmission:
贪心初始流 + Dinitz() (0.8s +- 。。

Problem E. Strong Defence:
构造 -> bfs()..。

Problem F. Weird Dissimilarity:
dp()..

Problem G. PL/Cool
Tags: 解释器、表达式求值、并查集、字符串 Hash
…
。。。

Problem H. Royal Federation:
一个国家有 n 个城市，且城市之间的道路形成一棵树，现在要求划分出若干个省，使得每个省的城市数目属于 [B, 3B]。
并为每个省指定一个省会，使得属于该省的所有城市，都可以在该省内部的范围内到达省会。
（省会不要求不在省内。。）

递归构造，满足条件的方案一定存在。设 dfs() 中若访问到点 u 时，其子树的 size 都不超过 B，
那么把它们合并成若干 [B, 2B] 之间的点集，并以 u 点作为省会。剩下来的点集数目+上 u 点自己一定不超过 B。

最后会剩下与根节点相连的不超过 B 个点的集合，任选一个与该集合相邻的集合与之合并即可。
这样除了与根结点相连的这个点集外，其他点集的大小都是 [B, 2B] 之间。。

。。。

Problem I. Two Cylinders
$latex V = 8\int_0^{Min(r_1, r_2)} \sqrt{(r_1^2-x^2)(r_2^2-x^2)}dx&s=4$
。。。积分我完全不会。。移步这里。。。）。。
http://blog.watashi.ws/970/andrew-stankevich-3-solution/

。。。朴素（。设置块数。。分段黎曼近似。。。

External link:

http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=Andrew+Stankevich%27s+Contest+%233

Posted by xiaodao
Category: Andrew Stankevich’s Contest
Tags: 施工中