T3 暑假打工

题意

给定的N个工作中选择若干个，使得在M天内获得最大的总报酬。每个工作i有两个属性：A_i表示完成该工作需要等待的天数，B_i表示完成该工作后获得的报酬。每天最多只能做一个工作。

思路

1. 贪心：我们需要在有限的时间内选择报酬最高的工作。对于每一天，我们选择能够在当天完成且报酬最高的工作。
2. 优先队列：我们可以按照时间从后往前考虑，对于第k天，我们选择所有A_i ≤ k的工作中B_i最大的那个。

实现流程：

1. 将所有工作按照A_i从小到大排序。
2. 使用一个最大堆（优先队列）来维护当前可选的工作。
3. 从第1天到第M天，每天选择当前可选工作中报酬最大的一个。

时间复杂度

• 排序：O(N log N)
• 遍历每一天并维护优先队列：O(M + N log N)
• 总时间复杂度：O(N log N + M)

题意

我们需要找到最小的正整数$N$，使得$N!$是给定整数$K$的倍数。关键在于理解$K$的质因数分解与$N!$的关系。

解题思路

1. 质因数分解：首先对$K$进行质因数分解，得到$K = \prod_{i=1}^{m} p_i^{e_i}$。
2. 计算每个质因数的最小$N$：对于每个质因数$p_i$，我们需要找到最小的$N_i$使得$N_i!$包含至少$e_i$个$p_i$因子。
3. 二分：对于每个质因数$p_i$，使用二分来找到满足条件的最小$N_i$。
4. 取最大值：最终的$N$是所有$N_i$中的最大值。

算法知识点

• 质因数分解
• 二分查找

时间复杂度

• 质因数分解：$O(\sqrt{K})$
• 二分搜索：$O(\log K)$
• 总时间复杂度：$O(\sqrt{K} + \log K)$

题意

在一个有向无环图（DAG）中找到一条路径，使得路径起点和终点的黄金价格差最大。由于题目保证$X_i < Y_i$，所以这个图实际上是一个DAG。

思路

1. 关键观察：我们需要找到两个城镇i和j，其中i可以到达j，并且A[j]-A[i]最大。
2. 动态规划解法：我们可以维护一个数组min_cost，其中min_cost[i]表示到达城镇i之前（不包括i）的最小A值。然后对于每个城镇i，计算A[i] - min_cost[i]并取最大值。
3. 拓扑排序处理：由于图是DAG，我们可以按照拓扑序处理每个节点，更新其后继节点的min_cost值。

时间复杂度

• 拓扑排序的时间复杂度是O(N+M)
• 每个节点处理其后继节点的时间也是O(N+M)
• 总时间复杂度为O(N+M)