T1:决斗
题目描述 Description
今天是小 Q 的生日，他得到了 n 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 i 张卡代表一只攻击力为 ri，防御力也为 ri 的怪兽。
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 i 以及 .另 .一 .只怪兽 j（i≠ji≠j），并让怪兽 i 向怪兽 j 发起攻击。此时，若怪兽 i 的攻击力小于等于怪兽 j 的防御力，则无事发生；否则，怪兽 j 的防御被打破，怪兽 j 退出游戏不再参与到剩下的游戏中。一
只怪兽在整场游戏中 .至 .多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。
输入描述 Input Description
从文件 duel.in 中读入数据。
输入的第一行包含一个正整数 n，表示卡牌的个数。
输入的第二行包含 n 个正整数，其中第 i 个正整数表示第 i 个怪兽的攻击力及防御
力 ri。
输出描述 Output Description
输出到文件 duel.out 中。
输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。
样例输入 Sample Input
【样例 1】 5 1 2 3 1 2 【样例 2】 10 136 136 136 2417 136 136 2417 136 136 136
样例输出 Sample Output
【样例 1】 2 【样例 2】 8
数据范围及提示 Data Size & Hint
【样例 1 解释】
其中一种最优方案为：第一回合让第 2 只怪兽向第 1 只怪兽发起攻击，第二回合
让第 5 只怪兽向第 4 只怪兽发起攻击，第三回合让第 3 只怪兽向第 5 只怪兽发起攻击。
此时没有退出游戏的怪兽都进行过攻击，游戏结束。可以证明没有更优的攻击顺序。
【数据范围】
T2:超速检测
题目描述 Description
小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 L 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。
这个周末，主干道上预计出现 n 辆车，其中第 i 辆车从主干道上距离最南端 di 的位置驶入，以 vi 的初速度和 ai 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 vi > 0，但 ai 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 L 的位置）或速度降为 0（这只可能在 ai < 0 时发生）时，我们认为该车驶离主干道。
主干道上设置了 m 个测速仪，其中第 j 个测速仪位于主干道上距离最南端 pj 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度 .超 .过了道路限速 V ，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 n 辆车中会有多少辆车被判定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 n 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。
由于 n 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。
如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。
输入描述 Input Description
从文件 detect.in 中读入数据。
本. 题. 有. 多. 组. 测. 试. 数. 据。
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行包含四个整数 n, m, L, V ，分别表示车辆数量、测速仪数量、主干道长度和
道路限速。
接下来 n 行：
第 i 行包含三个整数 di, vi, ai 描述一辆车。
最后一行包含 m 个整数 p1, p2, · · · , pm 描述道路上所有测速仪的位置。
输出描述 Output Description
输出到文件 detect.out 中。
对于每组数据：输出一行包含两个整数，第一个整数为所有测速仪都开启时被判定
为超速的车辆数量，第二个整数为在不漏掉超速车辆的前提下最多可以关闭的测速仪数
量.
样例输入 Sample Input
1 5 5 15 3 0 3 0 12 4 0 1 1 4 5 5 ‐2 6 4 ‐4 2 5 8 9 15
样例输出 Sample Output
3 3
数据范围及提示 Data Size & Hint
【样例 1 解释】
【数据范围】
【提示】
T3:染色
题目描述 Description
给定一个长度为 n 的正整数数组 A，其中所有数从左至右排成一排。
你需要将 A 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 C 为长度为 n 的整数数组，对于 A 中的每个数 Ai（1 ≤ i ≤ n）：
• 如果 Ai 左侧没有与其同色的数，则令 Ci = 0。
• 否则，记其左侧 .与 .其 .最 .靠 .近 .的 .同 .色 .数为 Aj ，若 Ai = Aj ，则令 Ci = Ai，否则令Ci = 0。
你的最终得分为 C 中所有整数的和，即 ∑i=1nCi∑i=1nCi。你需要最大化最终得分，请求出最终得分的最大值。
输入描述 Input Description
从文件 color.in 中读入数据。
本. 题. 有. 多. 组. 测. 试. 数. 据。
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行包含一个正整数 n，表示数组长度。
第二行包含 n 个正整数 A1, A2, . . . , An，表示数组 A 中的元素。
输出描述 Output Description
输出到文件 color.out 中。
对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。
样例输入 Sample Input
3 3 1 2 1 4 1 2 3 4 8 3 5 2 5 1 2 1 4
样例输出 Sample Output
1 0 8
数据范围及提示 Data Size & Hint
【样例 1 解释】
【数据范围】
T4:擂台游戏
题目描述 Description
输入描述 Input Description
从文件 arena.in 中读入数据。
本. 题. 的. 测. 试. 点. 包. 含. 有. 多. 组. 测. 试. 数. 据，但不同测试数据只是通过修改 a1, a2, · · · , an 得到，其他内容均保持不变，请参考以下格式。
其中 ⊕ 代表异或运算符，a mod b 代表 a除以 b 的余数。
输入的第一行包含两个正整数 n, m，表示报名的选手数量和询问的数量。
输入的第二行包含 n 个非负整数 a′1, a′2, · · · , a′n，这列数将用来计算真正的能力值。
输入的第三行包含 m 个正整数 c1, c2, · · · , cm，表示询问。
设 K 是使得 2k ≥ n 的最小的非负整数，接下来的 K 行当中，第 R 行包含 2K-R个数（无空格），其中第 G 个数表示第 R 轮的第 G 场比赛抽签得到的 dr,g = 0/1。
注意，由于询问只是将人数凑齐到 2k ≥ ci，这里的 k ≤ K，因此你未必会用到全部的输入值。
接下来一行包含一个正整数 T，表示有 T 组测试数据。
接下来共 T 行，每行描述一组数据，包含 4 个非负整数 X0, X1, X2, X3，该组数据的能力值 ai = a′i ⊕ X(i mod 4)，其中 1 ≤ i ≤ n。
输出描述 Output Description
输出到文件 arena.out 中。
共输出 T 行，对于每组数据，设 Ai 为第 i（1 ≤ i ≤ m）组询问的答案，你只需要输出一行包含一个整数，表示 (1 × A1) ⊕ (2 × A2) ⊕ · · · ⊕ (m × Am) 的结果。
样例输入 Sample Input
5 5 0 0 0 0 0 5 4 1 2 3 1001 10 1 4 2 1 0 0 1 2 1 0 0 2 3 1 2 2 0 1
样例输出 Sample Output
5 19 7 1
数据范围及提示 Data Size & Hint
【样例 1 解释】
【数据范围】
