solution

T1 幂次方

题意

给定一个 $N$ ，输出 $1$ 到 $N$ 之间不能表示为 $a^b$ 的数字个数，$a$ 和 $b$ 不小于数字 $2$ 。

思路

如果本题不看 $N$ 的范围，那么我们可以直接穷举每个数据 $i$ ，测试 $i$ 能否表示为 $a^b$ 。

但是这样的时间复杂度是 $O(n \times \log n \times \log n)$ ，本题的 $n$ 为 $10^{10}$ ，一定会超时。

因为本题要求的是不能表示，所以我们可以考虑容斥，先算出可以表示为 $a^b$ 的个数，然后用 $n$ 减去即可。

题目限制 $a \ge 2 , b \ge 2$ ，我们发现，当 $b$ 取最小值时， $a$ 会有最大值 $\sqrt{n}$ ，也就是只会有 $10^5$ 。

所以可以在 $[2,\sqrt{n}]$ 中枚举底数 $a$ ，然后从 $2$ 次幂开始枚举 $a^b$ ，当 $a^b \gt n$ 时结束本次 $a$ 的枚举，否则标记 $a^b$ 。

这样做的思路类似筛法，当 $b=2$ 时，底数 $\le 10^5$ ，当 $b=3$ ，底数 $\le 10^3$ ，显然更大的 $b$ 会让底数更少。

这样子时空复杂度都不会超。

T2 自学

题意

有 $N$ 门不同的课程，一个学期一共有 $M$ 周，每一周会上 $N$ 次课，每一门课程恰好一周上一次课，Alice 对于每一个课程都有一个熟练度，初始时都为 $0$。

对于一周里的一节课， Alice 可以选择如下选项中的一个：

• 去上课：如果他上的是第 $i$ 门课，那么他对于这节课的熟练度增加 $A_i$。
• 翘课：Alice 热爱学习，所以他会选一门课自学，如果他选了第 $i$ 门课，那么他对于这节课的熟练度增加 $B_i$。

为了去更多的学习课外知识，Alice 不会在课下学习这 $N$ 门课程，但是他又不想要让自己挂科，于是他找到了你，他想让自己对每一门课的熟练度的最小值最大。

思路

暴力做肯定会超时，发现可以用二分答案加验证的做法。一般来说，求最大值最小，最小值最大一类的问题，一般都可以使用二分答案加验证的做法。

本题答案最小为 $1$ ，最大不超过 $10^{18}$ 。而且预期越小，是可行解的可能性越大。所以就可以进行二分答案了。

如何验证答案是否正确？可以考虑贪心。

贪心策略：对于某个答案 $x$ ，考虑分析每门课。如果自学比上课更好，那就自学，直到达到目标值为止。如果上课比自学更好，那就先看看仅上课可否达到目标，如果可以，就尽量少上课（留出自学的空间），如果达不到，那就先上完课，再尽量少的自学。

把自学与上课的总课程数记为 $num$ ，如果 $num \le n \times m$ ，说明是可行的，反之不可行。

用样例 $1$ 举例。首先通过不断地二分，最终找到 $18$ 。遍历一遍每个课程：

• 课程 $1$ ：上课更优，所以优先上课，发现上 $1$ 节就够了。
• 课程 $2$ ：自学更优，所以全部自学，要自学 $3$ 次。
• 课程 $3$ ：上课更优，优先上课，但发现哪怕上满 $3$ 周，也达不到 $18$ ，所以剩下要再自学 $2$ 节。

总共 $3$ 门课用了 $9$ 节，刚好用完，且没有比该答案更大的可能。

T3 假期

题意

现在有 $n$ 项工作，如果你完成了第 $i$ 项工作，你将会在从完成那天开始算起的 $A_i$ 天时获得 $B_i$ 的工资。

每天你最多只能做一项工作，每项工作也只能做一次，每项工作在当天就能做完。

现在问你在 $m$ 天的时间，能获得的最大工资是多少。

思路

贪心。由于是当天完成算起的 $A_i$ 天才能得到工资，可能会存在在 $M$ 天内做完工作但是收不到工资的情况（等 $A_i$ 的时间超过了 $M$ ），所以我们尽量去做工作完成后 $A_i$ 比较小的任务，然后再在这些任务中做工资最大的任务。

其中要得到最少天数的任务，直接对原数组按 $A_i$ 大小排序。之后枚举天，对于枚举到的第 $i$ 天，每天选择一个工资最大的任务，对于如何选出最大工资的任务，我们选择用优先队列来维护这些任务，这样可以继承前一天可以做但没有做的任务，之后每次弹出工资最大的任务并计入 $ans$ 。

T4 排队

题意

有 $n$ 个小孩从左到右排成一条队，第 $i$ 个小孩的位置是 $i$ ，他有一个活跃度 $A_i$ 。你可以对这 $n$ 个小孩重新排序，对于第 $i$ 个小孩来说，假设一开始他的位置是 $x$ ，打乱重排后的位置是 $y$ ，那么他会获得 $A_i \times |x-y|$ 的开心值。现在问重新排序后可能能获得的最大开心值是多少。

思路

考虑贪心，我们应该让活跃度高的先选择位置，要使得幸福度越高，则一定分配为目前唯一的未站孩子的区间的左端点或右端点。

证明：

1. 为什么先移动最大数最优？ 这是考虑到同向冲突（因为如果都是反向就可以满的话，选大小数都可以是独立的，但关键就在于同向冲突），比如 1 5 6 1 1 1 ，5和6都要向着最右边排，设6移动x，5移动y，x+y=6，所获得的收益为：6x+5y。两式结合，得出收益为 30+x 或 36-y 。 即较大数移动距离越大，较小数移动距离越小，所获得的的收益就越大，所以较大数要先与较小数移动。

2. 确定了先移动最大数最优没错后，第一思路一般是将大数移动到最远的那一端。那么如何证明只需判断大数移动到最左端/最右端即可判断出最优选法？ 因为要想找与某点位置最远，该点一定在边界点上，左端点/右端点即是边界点。

因为每次选位置时都是选端点处，紧贴着边界放的，所以未被选择的区间有且仅有一个：区间dp。

因为先放大数是最优的，所以先将数按照活跃度倒序排列，下面所说的第 i 个数指的是排序后的下标为 i 对应的活跃值。

为了更好表示，我们不直接用区间，而是用左边已分配的数的个数和右边已分配数的个数来间接得出区间边界。

状态表示：$dp[i,j]$ 表示将已经将 i 个数分配在左边，j 个数分配在右边时的所有方案。属性：幸福值Max。

状态计算：以下一个数，即第 $k = i + j + 1$ 个数选择的位置是左端点/右端点为依据划分。

1. 第 $k$ 个数选择左端点。则现在左边分配的是 $i + 1$ 个数，右边配的是 $j$ 个数，即 $dp[i+1,j]$；相比于$dp[i,j]$，第 $k$ 个数的位置由 $b[k].y$ 到 $i + 1$，幸福值增加了 $a[k] * | b[k].y - (i+1) |$；

2. 第 $k$ 个数选择右端点。则现在左边分配的是 $i$ 个数，右边配的是$j + 1$ 个数，即 $dp[i,j+1]$；相比于$dp[i,j]$，第 $k$ 个数的位置由 $b[k].y$ 到 $n-(r+1)+1 = n - r$，幸福值增加了 $a[k] * | b[k].y - (n - j) |$;

所以，最终答案为 $dp[i,n-i]$ 的最大值。

T5 传送

题意

存在 $n$ 个小镇，$m$ 条传送通道，第 $i$ 条双向连结 $u_i,v_i$ 两个小镇，经过每个传送通道需要花费 $1$ 分钟。特别地，可能存在 $u_i=0$，表示该条传送通道只规定了一端，另一端待定。存在 $n$ 个独立询问，对于 $i=1,2,⋯,n$ ，钦定所有未确定的 $u_i$ 均为 $i$ ，求从小镇 $1$ 到小镇 $n$ 最小耗费的时间。若无法到达输出 $−1$ 。

思路

先声明一下，$dis1_i$ 表示不考虑不确定的边时点一到 $i$ 的距离，$disn_i$ 表示同样情况下 $n$ 到 $i$ 的距离。

首先每一次钦定所有不确定的 $u_j$ 为 $i$ 时，新增的边和所相连的点呈现为一个菊花图（下文中的叶子和根都是指这个菊花图的叶子和根），此时我们来考虑最短路是怎么形成的，因为新形成的图是菊花图，所以只能在以下几种情况中产生：

1. 不走新增的边。
2. 从一条新增的边走到 $i$ 上，然后从 $i$ 走原先的边直接走到 $n$ 。
3. 从原先的边走到 $i$ 上，然后经过一条新增的边走到 $n$ 。
4. 从一条新增的边走到 $i$ 上，然后经过一条新增的边走到 $n$ 。

然后我们来讨论每种情况在什么时候出现最小值。根据题意知这个菊花图的叶子结点是固定不变的，所以我们只需要考虑两个点，第一个点 $s$ 表示所有叶子中到点一距离最近的一个，第二个点 $t$ 表示所有叶子中到点 $n$ 距离最近的一个。此时我们就可以重新表示这几个状态了。

1. $dis1_n$ 。
2. $dis1_s + 2 + disn_t$ 。
3. $dis1_i + 1 + disn_t$ 。
4. $dis1_s + 1 + disn_i$ 。

所以我们只需要预处理出两个 $dis$ ，就可以 $O(1)$ 的统计答案了。