utpc2012 Wrapping 题解
题目链接题意用一个绳子去包绕一个三维空间的单位立方体，要求绳子有一段和向量 $(a,b,0)$ 平行。求最少需要的绳子长度。$a,b \leq 10^{18}$题解绕绳子问题由于会循环多个面，所以我们首先考虑将这个东西展开在无限的二维平面上，这样跳跃到另一个面就可以看作是走到相邻的面了。考虑一个形象的过程：先从结束的位置把绳子断开，然后我们按照需求往上或者往右滚动，这个绳子也会被留在平面上形...
题目链接题意用一个绳子去包绕一个三维空间的单位立方体，要求绳子有一段和向量 $(a,b,0)$ 平行。求最少需要的绳子长度。$a,b \leq 10^{18}$题解绕绳子问题由于会循环多个面，所以我们首先考虑将这个东西展开在无限的二维平面上，这样跳跃到另一个面就可以看作是走到相邻的面了。考虑一个形象的过程：先从结束的位置把绳子断开，然后我们按照需求往上或者往右滚动，这个绳子也会被留在平面上形...
上午打比赛的时候感冒了十分难受。。于是发挥非常差。A如果偶数层也是确定的话直接让 $a_i = h_i-h_{f_i}$ 就好了。否则我们考虑偶数层是干什么的：它可以让它所有儿子统一减少一个数。于是对于每个点统计出儿子节点的最小值，将这个点赋成最小值即可。B考虑如果确定了左上角 $2 \times 2$ 的矩阵，那么前两行剩下的格子的每一列的字符集就确定了，贪心分配一下。然后剩下的行每个 $...