差别

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

--- 2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su [2020/07/24 11:18]
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$。
-你可能会问 $\alpha_1 = \alpha_2$ 怎么办，恭喜你，没有这个数据，但真的求解的时候你的程序会聪明地帮你求得加了一个极小量的角度，所以精度卡好一点也差不多没问题。
 ===== E. Evacuation Plan =====
@@ 行 155: / 行 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

用户工具

站点工具

差别

页面工具