差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su [2020/07/24 11:15]
chielo [D. Catenary]
+++ 2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su [2020/07/24 16:35] (当前版本)
chielo [I. Archaeological Research]
@@ 行 11: / 行 11: @@
 ===== A. Three Servers =====
-**题目大意**：
+**题目大意**：3 台机器，我们要分配 $n$ 个任务给机器，每个任务分一个机器即可，占用该机器 $t_i$ 个单位的时间。3 个机器各自被占用的总时间中，我们需要让最大和最小的差尽可能小。问方案。
 **题解**：
+考虑贪心地去构造，会发现总有办法能限制答案在 $t_i$ 的最大值以内。因此在最优方案中，三台机器各自被占用的总的时间中的最大值不会超过 $t_i$ 的和除以 $3$ 加 $t_i$ 的最大值。
+想 DP 记方案？没门，内存不够。其他的队伍有用 bitset 先记一下可行性，然后隔着记录或者想办法再把转移拿回来。
+我比较菜，想了一下我一个一个加，那么假装我加的过程中，最大和最小的差不会太大。那么 DP 的状态就是记录现在插第 $i$ 个、最大减最小的值 $u$、次大减次小的值 $v$。然后假装最大和最小的差是在某个范围内，强行 DP。甚至记录了一大摞东西。
+队友表示可以 shuffle 一下，正常地插总有办法卡我，但是我随机刷一下他就卡不住了。然后把 DP 记得东西改用 short 存，就卡过去了。
 ===== B. Game on Bipartite Graph =====
@@ 行 99: / 行 107: @@
 到现在我已经分析的是头昏眼花，所以接下来的只能猜一下了。想象一下，如果 $\alpha_1$ 固定了，那么随着 $\alpha_2$ 的变化，我们通过上面的方式计算一下最后一个点的坐标，这个点划过的轨迹必然是一个连续、光滑的曲线，我们需要一个可以三分的目标函数，这个目标函数越小，就表明最终一个点越接近 $(L, 0)$。
-<del>
 最后就只能各种距离函数都试一下了 XwX，不过确实轨迹上的曲率很难确定，而且轨迹是光滑的，因此像切比雪夫距离、曼哈顿距离之类的，在确定的距离下图形不是光滑的距离函数会比较适合。
 最后发现三分第一个角套三分第二个角，最小化最终一个点到 $(L, 0)$ 的切比雪夫距离能获得正确的解，晚安。
-</del>
-哦天哪，我们先考虑一下解出来的 $\lambda_2$ 的意义，由于 $-\lambda_1 \ge 0$，所以 $\lambda_2$ 相当于是在确定一个下标 $j$，使得：
-$$x_1 - \lambda_2 > x_2 - \lambda_2 > \cdots > x_j - \lambda_2 \ge 0 > x_{j+1} - \lambda_2 > \cdots > x_n - \lambda_2$$
-即 $\lambda_2$ 确定了什么时候角度会超过 $\frac{pi}{2}$，也即纵坐标开始往反方向走的时候。
-来确定一下 $\lambda_2$ 和 $\alpha_2$ 的关系吧，有：
-$$
-\lambda_2
-= \frac{x_1 \sin{\alpha_1} \cos{\alpha_2} - x_2 \cos{\alpha_1} \sin{\alpha_2}}{\sin{(\alpha_1 - \alpha_2)}}
-= \frac{(x_1 - x_2) \sin{\alpha_1} \cos{\alpha_2}}{\sin{(\alpha_1 - \alpha_2)}} + x_2 \\
-\frac{\partial \lambda_2}{\partial \alpha_2}
-= (x_1 - x_2) \sin{\alpha_1} \frac{-\sin{\alpha_2} \sin{(\alpha_1 - \alpha_2)} - \cos{\alpha_2} \cos{(\alpha_1 - \alpha_2)}}{\sin{(\alpha_1 - \alpha_2)}}
-= -(x_1 - x_2) \sin{\alpha_1} \frac{\cos{\alpha_1}}{\sin{(\alpha_1 - \alpha_2)}} \ge 0
-$$
-即 $\lambda_2$ 随 $\alpha_2$ 的增大而单调递增，即是说第二个角度越大，纵坐标越是提早往反方向走。
-而由于 $-\lambda_1$ 始终大于或等于 $0$，因此 $\sin{\alpha_i} \ge 0$，也即横坐标是持续增长的，不会转一圈又捞回来。
-那么更重要的分析是确定一下最终一个点的纵坐标是否是随 $\alpha_2$ 的增大而持续增大的，再分析下去我就要死了，总之 $\cos{\alpha_i}$ 是前面一些是正的，后面一些是负的，我们假装用长度加权求和后是递增的好了 XwX。
-那么容易想到如果 $\alpha_1$ 固定了，那么随着 $\alpha_2$ 的增长，最终那个点的纵坐标会先从负的，连续地变化到正的，那刚好我们可以用二分来求一下纵坐标为 $0$ 时的 $\alpha_2$。此时的横坐标也会和 $\alpha_1$ 有一个关系，至于是不是单调地连续变化，已经没有什么好害怕的了，猜一下吧，随 $\alpha_1$ 的增长是单调递增的，那么这一层也是可以二分的。
-最终的做法就是二分 $\alpha_1$，求一下 $\alpha_2$ 是多少是最终的点的纵坐标为 $0$，二分找最终点横坐标为 $L$ 的 $\alpha_1$；对于 $\alpha_2$ 的求法，也是二分一下，找最终点纵坐标为 $0$ 时的 $\alpha_2$。
 ===== E. Evacuation Plan =====
@@ 行 153: / 行 137: @@
 ===== I. Archaeological Research =====
-**题目大意**：
+**题目大意**：现在有一个长度为 $n$ 的序列，知道从某个位置开始，到另外某个位置上会出现一个新的值。要你恢复出来字典序最小的序列。
 **题解**：
+不考虑字典序最小，$1, 2, 3, \ldots$ 就是符合条件的答案，因此绝对有解。
+显然，对于第 $i$ 个元素，如果表示它是从 $l_j$ 开始的一个新的值，那么它取没有出现在这些值中的最小值即可。（我一开始想成最大的，表示 max，队友听，mex，好呀）
+离线没修改的区间 mex，记当前我们处理到了第 $i$ 个元素，记录一下元素值为 $key$，在 $i$ 之前、离 $i$ 最近的出现的位置 $value$。想求的是 $l_j$ 到 $i$ 之间，没有出现过的最小的元素值，考虑从小到大枚举这个元素值，一旦遇到一个元素值最近出现的位置比 $l_j$ 小，那就是它了。
+所以用线段树维护一下元素值在相应区间中，最近出现的位置的最小值即可。查询的过程也就是看左子树是不是有符合条件、即区间内没有出现过的元素值，没有就走右子树。
 ===== J. Sockets =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具