Posts by hostmaster

考试的时候状态非常好。 因为考场里没有钟，老师又说要收所有的手表，无论是否是电子手表，所以看不了时间。 因为害怕时间不够，做得很快。 前面单项选择题非常简单。 完善程序 T1 非常恶心，但其实也不恶心，就是我看不懂 [大哭]，所以蒙了个答案，然后最后再细看。 全部做完之后剩了 $30$ 多分钟，回头看完善程序 T1。 我觉得状态好，正确率…

没什么压力，去年拿过一等了，非 $0$ 就能进。 大概 $45$ 分钟做完了单项选择题。 阅读程序的 T1 太【】了，计算量这么大，算着算着人就傻了。。。而且这个 $13$ 行的 x | y << 1 也不知道哪个优先级更高。【】【】出题人。 阅读程序题 T2 也是【】，出题人不怀好意，整个递归搞我心态，还好果断放弃，先看下面题。 阅读程…

斜率单调，决策点单调 使用单调队列维护凸包。 题意 给定 $n, a, b, c$，和一个长度为 $n$ 的数组 $z$。 定义 $i$ 到 $j$ 这一段的价值： $$X = \sum\limits_{k = i}^j z_k$$ 则价值为： $$C = a \cdot X^2 + b \cdot X + c$$ 我们要把数组分成若干个…

题意 给定 $n$，你要猜一个长度为 $n$ 的 01 串。$n$ 是一个偶数。 每次你给出一个长度为 $n$ 的 01 串，如果 全部猜中，返回 $n$ 你恰好猜中一半，返回 $\dfrac n2$ 否则，返回 $0$ 最多询问 $n + 500$ 次。 $2 \leq n \leq 1000$ 题解 查看题解 随机至多 $499$ 次…

题意 有 $n$ 瓶水，其中一瓶有毒。 有 $maxk$ 只小白鼠，其中有一只变异了。现在要决定每只小白鼠喝哪些水。最后给出每只小白鼠的死亡情况，你需要输出毒水的编号。 普通小白鼠喝毒水会死，变异小白鼠不喝毒水会死。 |Subtask|分值|$n$|$maxk$| |-|-|-|-| |$1$|$1$|$n = 1$|$0$| |$2$|…

题目 Milk Scheduling Vacation Planning The Bessie Shuffle 题解 T1 算法 1 反悔贪心。 按照时间从小到大排序。从 $1$ 到 $N$ 枚举 $i$，如果当前时间可以让奶牛 $i$ 挤奶，那么就挤。否则我们找到产奶量最低的奶牛不挤，把时间腾出给当前这头。用堆维护产奶量即可。时间复杂度…

题意 有 $N$ 只奶牛，奶牛 $i$ 的位置是 $X_i$。 有 $M$ 种雨伞，第 $i$ 种雨伞的价格为 $C_i$，宽度为 $i$。 现在想买一些雨伞，使得每头奶牛都在伞下。求最少花费。 注意，大伞不一定比小伞贵，伞可以重叠。 $1 \leq N \leq 5000, 1 \leq M \leq 10^5, 1 \leq X_i \leq M$…

题意 给定一个长度为 $n$ 的只包含小写字母的字符串 $S$。现在要在纸上印出字符串 $S$。 你可以刻一个印章，印章每使用一次，就会将印章上的所有字母印到纸上。同一个位置的相同字符可以印多次。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。 求印章的最小长度。 例如：用 $\texttt{aba}$ 这个印章不可以…

题意 有 $n$ 个生物，第 $i$ 个生物有大小 $A_i$ 和颜色 $i$。 第 $i$ 个生物可以吞噬第 $j$ 个元素当： $$A_j \leq 2 \cdot A_i$$ 这些生不停的吞噬这其它生物，最终成为一个生物。求该生物可能的颜色的数量。 $2 \leq n \leq 10^5, 1 \leq A_i \leq 10^9$…

题意 给定 $k, F_0, F_1, F_2, F_3, F_4, F_5$。 你要把一个位数最多 $5$ 位的数 $n$，拆成 $k$ 个数的和，对 $k$ 个数中的每一个数的第 $i$ 位是 $3$ 的 $u$ 倍的话就会获得 $u \times F_i$ 的价值。一个方案的价值为所有价值之和。 你要让价值最大，求最大价值。 多组询…