ByteDance - Moscow Workshops ICPC Programming Camp 2019. Day 3, Div A.

ABCDEFGHIJK

复盘人：rxd

开场gt会了I，叶队想C，我想H。

0h51min，I +2。

叶队给我讲了C，我咕了。

叶队开始写C，我下机搞H的细节，gt给我讲A。

1h26min~1h45min，叶队C dirt了几发，gt写A。

2h02min，A WA，我上机帮叶队拍C，gt眼调A。

2h17min，发现C没有去掉重点。改完后T 51。改了排序后RE 60。

叶队继续眼调，我写H。

2h25min，A +2。

我写完H过不了样例，发现折魔方的部分有问题，下机想。gt写G。

中途我上机了一次，改完发现还是有问题，再下机。

终于想清楚了细节，3h56min，WA。

发现无解的情况漏判了。

4h07min，H +1。

gt和叶队讨论出了D的好像对的算法，gt写。4h30min，交了两发感觉萎的。

最后半个小时叶队上机提交调试C。最后得知是atan2精度炸了。

4h50min，C +9。

A：

B：利用高斯消元求起点随机游走到终点的期望步数,需要判断inf的情况.对于一个Inf的点,注意到其在方程中肯定无解.故这些点肯定是解完方程后剩下的自由元和与自由元相关的所有点，直接判断即可.

C(by yjn)：enumerate the bottom side of the triangle, maintain the projection of each point to the bottom side(there're \(\Theta(n^2)\) different orders when enumerating), and calculate the nearst point.

       When sorting, atan2 is not enough. Use outer production when polar angles differs slightly(e.g. \(|\theta_1-\theta_2|<0.1\)).

D(by yjn)：problem: Find a 2-regular spanning graph of a 2k-regular graph.

      solution: Find the eulerian tour and redirect the edges. find a spanning subgraph s.t. every vertex has 1 incoming edge and 1 outgoing edge, which can be easily calculated by max matching algorithm on bipatite graph. Since the original graph has even degree 2k, the bipatite graph is k-regular, which certainly has a perfect matching.

       upd by gt:直接随便dfs给边定向即可.要注意M=0时事实上是无解的.(+N)

E：

F：

G：用俄罗斯方块填满4*N格子.考场上没写完.爆搜出状态剪枝后只有约60种有用的状态,直接矩阵即可.最后一段时间写这个题应该会更好,比D靠谱一点.

H：先dfs出每个魔方，考虑处于哪个位置，上方对应是展开图中哪个方向。然后搜8个方块的位置，每个方块暴搜所有24种体位，合法的只有最多1种。

I：

J：

K：

小结（by yjn）：

1、C这个题，atan2的精度只有9位左右，对于这种对顺序敏感的题，这个要小心。排序的时候当极角接近，换叉积来排。

2、欧拉回路板子要搞个（已完成）。UOJ上其他板子e.g. simplex要准备一下。