一、实操题
1、计算系数
【问题描述】
给定一个多项式
请求出多项式展开后
项的系数。
【输入】
输入文件名为 factor.in。
共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。
【输出】
输出文件名为 factor.out。
输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取模后的结果。
【输入输出样例】
【数据范围】
对于 30%的数据，有 0≤k≤10；
对于 50%的数据，有 a = 1，b = 1；
对于 100%的数据，有 0≤k≤1,000，0≤n, m≤k，且 n + m = k，0≤a，b≤1,000,000。
参考答案：对于输入的多项式，我们需要计算展开后特定项的系数。根据二项式定理，多项式$(a+b)^k$展开后，第$n+1$项的系数为$C_k^n \times a^k-n \times b^n$。其中，$C_k^n$表示组合数，即从$k$个不同项中选取$n$个的组合方式。因此，我们需要计算$C_k^n$，即$k$选$n$的组合数。根据组合数的定义，$C_k^n = \frack!n! \times (k-n)!$。由于$n+m=k$，我们可以将$C_k^n$转化为$C_k^k-m$。即需要计算$\frack!(k-n)! \times n! = \frack!(k-m)! \times m!$。最后，根据题目要求，我们需要对结果取模10007。
2、聪明的质监员
【问题描述】
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是：
1、给定 m 个区间[Li，Ri]；
2、选出一个参数 W；
3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ：
这批矿产的检验结果 Y 为各个区间的检验值之和。即：
若这批矿产的检验结果与所给标准值 S 相差太多，就需要再去检验另一批矿产。小 T不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近标准值 S，即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。
【输入】
输入文件 qc.in。
第一行包含三个整数 n，m，S，分别表示矿石的个数、区间的个数和标准值。
接下来的 n 行，每行 2 个整数，中间用空格隔开，第 i+1 行表示 i 号矿石的重量 wi 和价值 vi 。
接下来的 m 行，表示区间，每行 2 个整数，中间用空格隔开，第 i+n+1 行表示区间[Li, Ri]的两个端点 Li 和 Ri。注意：不同区间可能重合或相互重叠。
【输出】
输出文件名为 qc.out。
输出只有一行，包含一个整数，表示所求的最小值。
【输入输出样例】
【输入输出样例说明】
当 W 选 4 的时候，三个区间上检验值分别为 20、5、0，这批矿产的检验结果为 25，此时与标准值 S 相差最小为 10。
【数据范围】
对于 10%的数据，有 1≤n，m≤10；
对于 30%的数据，有 1≤n，m≤500；
对于 50%的数据，有 1≤n，m≤5,000；
对于 70%的数据，有 1≤n，m≤10,000；
对于 100%的数据，有 1≤n，m≤200,000，0 < wi, vi≤10^6，0 < S≤10^12，1≤Li≤Ri≤n。
参考答案：首先，对于每个区间 [Li,Ri]，我们遍历其中的每个矿石，计算 wi / W 并向下取整，再乘以 vi。将所有矿石的贡献累加，即得到 Yi。最后，我们将所有区间的 Yi 相加得到检验结果 Y。我们的目标是最小化 |S-Y|。为了解决这个问题，我们可以使用二分搜索的方法。在每一次迭代中，我们选择一个 W 的值，计算对应的检验结果 Y，并计算 |S-Y|。如果 |S-Y| 仍然很大，我们就增大 W 的值；否则，我们就减小 W 的值。这样，我们就可以逐渐逼近最优解。具体的算法步骤如下：1. 初始化左边界 L 和右边界 R，使得 L 是所有矿石重量的最小值，R 是所有矿石重量的最大值。2. 在每一次迭代中，计算 W = (L+R)/2。3. 计算检验结果 Y。4. 计算 |S-Y|。5. 如果 |S-Y| 大于 0，那么增大 W，更新 L = W。6. 否则，减小 W，更新 R = W。7. 如果 L 和 R 的差的绝对值小于一个很小的数 eps，那么我们就找到了最优解，退出循环。最终，输出最优解 |S-Y|。
3、观光公交
【问题描述】
风景迷人的小城 Y 市，拥有 n 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1号景点，随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻，公交车只能往前开，或在景点处等待。
设共有 m 个游客，每位游客需要乘车 1 次从一个景点到达另一个景点，第 i 位游客在Ti 分钟来到景点 Ai，希望乘车前往景点 Bi（Ai<Bi）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。
一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器，每使用一个加速器，可以使其中一个 Di 减 1。对于同一个 Di 可以重复使用加速器，但是必须保证使用后 Di 大于等于 0。
那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？
【输入】
输入文件名为 bus.in。
第 1 行是 3 个整数 n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。
第 2 行是 n-1 个整数，每两个整数之间用一个空格隔开，第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间，即 Di。
第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi，每两个整数之间用一个空格隔开。第 i+2 行表示第 i 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。
【输出】
输出文件名为 bus.out。共一行，包含一个整数，表示最小的总旅行时间。
【输入输出样例】
【输入输出样例说明】
对 D2 使用 2 个加速器，从 2 号景点到 3 号景点时间变为 2 分钟。
公交车在第 1 分钟从 1 号景点出发，第 2 分钟到达 2 号景点，第 5 分钟从 2 号景点出发，
第 7 分钟到达 3 号景点。
第 1 个旅客旅行时间 7-0 = 7 分钟。
第 2 个旅客旅行时间 2-1 = 1 分钟。
第 3 个旅客旅行时间 7-5 = 2 分钟。
总时间 7+1+2 = 10 分钟。
【数据范围】
对于 10%的数据，k=0；
对于 20%的数据，k=1；
对于 40%的数据，2 ≤ n ≤ 50，1 ≤ m ≤ 1,000，0 ≤ k ≤ 20，0 ≤ Di ≤ 10，0 ≤ Ti ≤ 500；
对于 60%的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 10,000；
对于 100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 100,000。
参考答案：对于此问题，我们可以使用动态规划来解决。首先，我们需要预处理每个景点到下一个景点的最短时间，然后对于每个乘客，我们计算他上车和下车的时间，并更新总时间。最后，我们遍历所有可能的加速器使用方案，找到使总时间最小的方案。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
