dreadnought/2015 ACM-ICPC Asia Regional Beijing

2015 ACM-ICPC Asia Regional Beijing

A. Xiongnu’s Land [Lolicon]

题解:水题不表。

B. Xiang Hex [Lolicon]

题解:模拟。枚举这一步的走法,再判断是否会被将军。一个比较麻烦的地方是对于六边形坐标的处理。

C. Today Is a Rainy Day [Bacon]

题解:bfs预处理出6^6个只用整体操作到达每种状态的最小步数,对每个询问枚举每种状态统计使用单个操作的代价。

D. Kejin Game [Bacon]

题解:每个点拆两个\(u,u'\),求源到\(s'\)的最小割,割掉\(s\rightarrow u\)表示学,割掉\(u\rightarrow u'\)表示氪。如果\(u\)\(v\)的前置则\(u'\rightarrow v\)容量为删边的代价。

E. Stamps [Rowdark]

题解:将式子暴力展开,对无穷级数化简再做差之后可以得到ans(n, m) = ans(n - 1, m) × (n / (n - 1))(m+1) + ans(n, m - 1),之后递推求解即可。

F. You Are Under Arrest [Rowdark]

题解:Simpson求多个三角形和单个圆的面积并,注意下这个题精度很差,所以直接Simpson可能会超时,需要对于圆外部分直接用梯形公式求解,圆内部分整体做simpson。注意由于可能有会和扫描线平行的边,需要随机转一次平面。

G. Mysterious Antiques in Sackler Museum [Lolicon]

题解:水题不表。

H. Archipelago Tour [Bacon]

题解:如果答案过环,则一个二分+线段树的\(n\log^2n\)做法是显然的。考虑不过环,即树的情况,点分治+二分答案+线段树的\(n\log^3n\)做法是显然的。

考虑怎么优化后面的部分,考虑分治中以\(u\)为根的树,将所有点按照到根的安全值排序。对于一个二分的答案mid,可以线性求出每个点到根的点权和,顺序按安全值枚举每个点\(u\),则可以与其配对的点为排过序数组的一段区间(左右端点单调),要求的则是这段区间中与\(u\)属于不同子树且点权和最大的点。

发现这个东西不太好求,但是如果子树个数较少的话则可以对每个子树分别维护一个单挑队列。出于这个思路则可以使用奇怪的分治,根可以重用,每次将儿子分成两个part,每个part在\(\frac{1}{3}\)\(\frac{2}{3}\)之间,成功将树的部分优化到\(n\log^2n\)

I. Snake Carpet [Lolicon]

题解:构造。把奇数和偶数分开搞。奇数可以简单地搞成一个正方形。偶数把每个对折,也可以拼成一个矩形。

J. Osu! Master [Lolicon]

题解:水题不表。

K. A Math Problem [Lolicon]

题解:数位DP。题目条件转化后得到f(2n)=3f(n) f(2n+1)=3f(n)+1。直接记下模k的余数dp即可。