NOI 2019信息学奥林匹克竞赛开赛第一天！
1、回家路线（route）
【题目描述】
猫国的铁路系统中有 n 个站点，从 1 ∼ n 编号。小猫准备从 1 号站点出发，乘坐列 车回到猫窝所在的 n 号站点。它查询了能够乘坐的列车，这些列车共 m 班，从 1 ∼ m 编号。小猫将在 0 时刻到达 1 号站点。对于 i 号列车，它将在时刻 pi 从站点 xi 出发， 在时刻 qi 直达站点 yi，小猫只能在时刻 pi 上 i 号列车，也只能在时刻 qi 下 i 号列车。
小猫可以通过多次换乘到达 n 号站点。一次换乘是指对于两班列车，假设分别为 u 号与 v 号列车，若 yu = xv 并且 qu ≤ pv，那么小猫可以乘坐完 u 号列车后在 yu 号站点等待 pv − qu 个时刻，并在时刻 pa 乘坐 v 号列车。
小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。
- 小猫在站点等待时将增加烦躁值，对于一次 t (t ≥ 0) 个时刻的等待，烦躁值将增 加 At2 + Bt + C，其中 A, B,C 是给定的常数。注意：小猫登上第一班列车前，即 从 0 时刻起停留在 1 号站点的那些时刻也算作一次等待。
- 若小猫最终在时刻 z 到达 n 号站点，则烦躁值将再增加 z。
1、
2、对于所有)
，满足 
对于该回家路线，小猫得到的烦躁值将为：
小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。
【输入格式】
从文件 route.in 中读入数据。
第一行五个整数 n, m, A, B,C，变量意义见题目描述。
接下来 m 行，第 i 行四个整数 xi , yi , pi , qi，分别表示 i 号列车的出发站、到达站、 出发时刻与到达时刻。
【输出格式】
输出到文件 route.out 中。
输出仅一行一个整数，表示所求的答案。
【样例 1 输入】
3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10
【样例 1 输出】
94
【样例 1 解释】
共有三条可行的回家路线：
1. 依次乘坐 1，4 号列车，得到的烦躁值为：
10 + (1 × 32 + 5 × 3 + 10) + ( 1 × (9 − 4)2 + 5 × (9 − 4) + 10) = 104
2. 依次乘坐 2，4 号列车，得到的烦躁值为：
10 + (1 × 52 + 5 × 5 + 10) + ( 1 × (9 − 7)2 + 5 × (9 − 7) + 10) = 94
3. 依次乘坐 3，4 号列车，得到的烦躁值为：
10 + (1 × 62 + 5 × 6 + 10) + ( 1 × (9 − 8)2 + 5 × (9 − 8) + 10) = 102
第二条路线得到的烦躁值最小为 94。
【样例 2 输入】
4 3 1 2 3
1 2 2 3
2 3 5 7
3 4 7 9
【样例 2 输出】
34
【样例 3】
见选手目录下的 route/route3.in 与 route/route3.ans。
该样例的数据类型与最终测试点 5 ∼ 8 一致。
【样例 4】
见选手目录下的 route/route4.in 与 route/route4.ans。
该样例的数据类型与最终测试点 11 ∼ 14 一致。
【样例 5】
见选手目录下的 route/route5.in 与 route/route5.ans。
该样例的数据类型与最终测试点 18 ∼ 20 一致。
【数据范围与提示】
对于所有测试点：
每个测试点的具体限制见下表：
2、机器人（robot）
【题目描述】
小 R 喜欢研究机器人。 最近，小 R 新研制出了两种机器人，分别是 P 型机器人和 Q 型机器人。现在他要测试这两种机器人的移动能力，测试在从左到右排成一排的 n 个柱子上进行，柱子用 1 ∼ n 依次编号，i 号柱子的高度为一个正整数 hi。机器人只能在相邻柱子间移动，即：若机器人当前在 i 号柱子上，它只能尝试移动到 i − 1 号和 i + 1 号柱子上。
每次测试，小 R 会选取一个起点 s，并将两种机器人均放置在 s 号柱子上。随后 它们会按自己的规则移动。
P 型机器人会一直向左移动，但它无法移动到比起点 s 更高的柱子上。更具体地，P 型机器人在 l (l ≤ s) 号柱子停止移动，当且仅当下列两个条件均成立：
-
。
- 对于满足
。
-
。
- 对于满足
。
【输入格式】
从文件 robot.in 中读入数据。
第一行一个正整数 n，表示柱子的数量。
接下来 n 行，第 i 行两个正整数 Ai , Bi，分别表示 i 号柱子的最小和最大高度。
【输出格式】
输出到文件 robot.out 中。
仅一行一个整数，表示答案模 109 + 7 的值。
【样例 1 输入】
5
3 3
3 3
3 4
2 2
3 3
【样例 1 输出】
1
【样例 1 解释】
柱子高度共两种情况：
1. 高度为：3 2 3 2 3。此时若起点设置在 5，P 型机器人将停在 1 号柱子，共移动 4 个柱子。Q 型机器人停在 5 号柱子，共移动 0 个柱子，不符合条件。
2. 高度为：3 2 4 2 3。此时无论起点选在哪，都满足条件，具体见下表：
【样例 2】
见选手目录下的 robot/robot2.in 与 robot/robot2.ans。
【样例 3】
见选手目录下的 robot/robot3.in 与 robot/robot3.ans。
【样例 4】
见选手目录下的 robot/robot4.in 与 robot/robot4.ans。
【数据范围与提示】
对于所有测试数据：1 ≤ n ≤ 300 , 1 ≤ Ai ≤ Bi ≤ 109。
每个测试点的具体限制见下表：
3、序列（sequence）
【题目描述】
给定两个长度为 n 的正整数序列 {ai} 与 {bi}，序列的下标为 1, 2, · · · , n。现在你需 要分别对两个序列各指定恰好 K 个下标，要求至少有 L 个下标在两个序列中都被指定，使得这 2K 个下标在序列中对应的元素的总和最大。
形式化地说，你需要确定两个长度为 K 的序列 {ci}, {di}，其中1 ≤ c1 < c2 < · · · < cK ≤ n , 1 ≤ d1 < d2 < · · · < dK ≤ n
并要求 | {c1, c2, · · · , cK} ∩ {d1, d2, · · · , dK} | ≥ L
目标是最大化
【输入格式】
从文件 sequence.in 中读入数据。
本题输入文件包含多组数据。
第一行一个正整数 T 表示数据组数。接下来每三行表示一组数据。
每组数据第一行三个整数 n, K, L，变量意义见题目描述。
每组数据第二行 n 个整数表示序列 {ai}。
每组数据第三行 n 个整数表示序列 {bi}。
【输出格式】
输出到文件 sequence.out 中。
对于每组数据输出一行一个整数表示答案。
【样例 1 输入】
5
1 1 1
7
7
3 2 1
4 1 2
1 4 2
5 2 1
4 5 5 8 4
2 1 7 2 7
6 4 1
1 5 8 3 2 4
2 6 9 3 1 7
7 5 4
1 6 6 6 5 9 1
9 5 3 9 1 4 2
【样例 1 输出】
14
12
27
45
62
【样例 1 解释】
第一组数据选择的下标为：{ci} = {1} , {di} = {1}。
第二组数据选择的下标为：{ci} = {1, 3} , {di} = {2, 3} 。
第三组数据选择的下标为：{ci} = {3, 4} , {di} = {3, 5}。
第四组数据选择的下标为：{ci} = {2, 3, 4, 6} , {di} = {2, 3, 4, 6}。
第五组数据选择的下标为：{ci} = {2, 3, 4, 5, 6} , {di} = {1, 2, 3, 4, 6}。
【样例 2】
见选手目录下的 sequence/sequence2.in 与 sequence/sequence2.ans。
【样例 3】
见选手目录下的 sequence/sequence3.in 与 sequence/sequence3.ans。
【数据范围与提示】
对于所有测试点：T ≤ 10 , 1 ≤ ∑ n ≤ 106 , 1 ≤ L ≤ K ≤ n ≤ 2 × 105 , 1 ≤ ai , bi ≤ 109。 每个测试点的具体限制见下表：
欢迎加入牛客OI交流群370123478，参与更多比赛资讯、题解交流~
Momenta公司福利 296人发布
