2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su

差别

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

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su [2020/07/24 10:21]
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 =====
@@ 行 102: / 行 110: @@
 最后发现三分第一个角套三分第二个角，最小化最终一个点到 $(L, 0)$ 的切比雪夫距离能获得正确的解，晚安。
 ===== E. Evacuation Plan =====
@@ 行 128: / 行 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 =====

2020-2021/teams/intrepidsword/ru-winter-camp-2015-saratov-su.1595557278.txt.gz · 最后更改: 2020/07/24 10:21 由 chielo