困得离谱，瞎几把训练喽，南京要寄。

[A Access Levels]

solution

题面： 个人， 个文件。要求你给文件分组，每个文件在自己的组有个保密级别，同时你要分配给每个人对每个组一个权限，当权限大于等于保密等级则可以看文件。现给出每个人可以看的文件，要求构造分组情况，且组数最少。

做法：考虑 的 矩阵的任意两列，如果这两列存在包含关系则可以确定这两列的偏序关系。建出这张 后，可以发现答案就是最小链覆盖。拆点，转成二分图最大匹配，方案可以带权并查集暴力算算，差不多就是每个点初始设为一，然后考虑根到祖先的路径和这样。时间复杂度 。

[B Broken Keyboard]

solution

题面：签到题，不知道题意。

做法：

[C Card Guessing]

solution

题面：一个只有 长度为 ，其中每个数字出现次数为 的序列，其有一个预测方式：对 位置可由 的数字来预测，前面这些数中出现次数最少的数就是第 个位置的数，若有相同次数的则随机选择一个。当然预测归预测，真实序列仍然是给定的。一个序列的权值定义为预测正确的次数，随机序列，问期望权值。

做法：随机是无意义的，我们直接算总权值和。注意到贡献是独立的，所以枚举长度 的序列是啥，然后贡献加起来即可。枚举可以暴力 背包，即 表示用了 ，长度为 ，最短长度为 的方案，也存在简单 隔板法等等。然后算贡献发现其实是经典的 状物，所以把 这种东西塞进背包里，同时注意到除了当前枚举的序列，我们还要计算剩余位置，所以背包里还塞着 这种东西。同时会发现相同次数其实没有影响，这是因为此刻等价于第 个位置有 种选择，但由于随机性所以要除以 ，等价于啥也没发生。注意下第 个位置此刻是确定的，所以其实非枚举的序列的系数其实是 这种东西，发现只用乘上个 即可。时间复杂度 或 ，能不能更优其实我没有去想了。

[D Devil May Cry]

solution

题面： 个文件，每个大小为 ，电脑内存为 ，下载一的大小需要一的时间，看一个文件只需要一的时间，问最少的时间看完所有文件，下载过程的内存是预缓存的，即还没下完就已经有这些内存了，可以一边看一边下载。

做法：签到题，显然想的是拿最小的数去匹配最大的数，时间复杂度 。

[E Exchange]

solution

题面：签到题。

做法：

[F Chemistry Lab]

solution

题面：一个化学药剂定义为 ，一些化学药剂 要组装出一个权值为 的化学用品则是要求确定 ，满足 ，其中这个化学用品的价格为 。现有 个化学药剂，购买一个的价格为 ，购买后就可以无限用，有 个客户要求，每个要求都是权值在 均匀分布随机的化学用品，问如何购买化学药剂期望收益最大。

做法：可以注意到对一个确定的 而言，显然选择两个化学药剂是最赚的，且要求 恰好在它俩的 之间。于是等价于我们选择了一些化学药剂将区间分成若干段， 落在哪期望就选哪个。而 是无用的，这是因为期望的线性性。对于一组 的化学药剂而言，它们的期望贡献是可以积分算出来的，即

其中 为一常数，可以解方程迅速解出来，最后算出积分值为 。

于是 升序后，考虑 表示当前以 为结尾的最大期望，转移是 ，直接就做完了。时间复杂度 ，这个东西可不可以决策单调性优化呢，我不知道。

[G Guess the String]

solution

题面：

做法：

[H Hospital Queue]

solution

题面： 个数，构造，要求第 个数只能放在 的位置，同时 个限制，要求 出现在 前面，保证有解，求每个数可以出现的最前面的位置。

做法：建出 的 后，考虑对每一个数算答案。按照拓扑序，每次贪心地将 最大的拿出来先放在最后面的位置，同时枚举答案即可。时间复杂度 。

[I Infinite Chess]

solution

题面：

做法：

[J Hero to Zero]

solution

题面：

做法：

[K Torus Path]

solution

题面： 的网格图，每个点有权值，往右下走，是循环图，问最大权值。

做法：注意到权值都为正，可以发现最多一个位置走不了，时间复杂度 。

[L Project Manager]

solution

题面： 个员工，有 天是集体休息日，每个员工每周都有固定休息日，有 个工作，每个工作有 个工序，每个工序需要 编号的人来工作，问每个工作第几天完成。

做法：签到题。发现答案不超过 ，直接用 set 和 priority_queue 模拟即可，时间复杂度 。

[M Minimum LCM]

solution

题面：求 。

做法：签到题，枚举因子即可。时间复杂度 。

[N Number Reduction]

solution

题面：给个数 ，每次可以删掉其中一位数，要求中间过程不出现前导零，删 次，问最终剩下最小的数。

做法：签到题，贪心删最小即可。时间复杂度 。