test

初二期末算法测试

一、智子干扰下的学员成绩调整

在三体世界的威胁下，地球太空军训练营里，智子不断干扰成绩统计系统，导致学员成绩总是出错。训练营的教官在修正成绩时苦不堪言，他们需要多次给某些学员增加分数，同时还要关注最低分情况。现在请你帮忙解决这个问题。

输入数据格式

第一行有两个整数 $n$，$p$，代表学员数与增加分数的次数。 第二行有 $n$ 个数，$a_1 sim a_n$，代表各个学员的初始成绩。 接下来 $p$ 行，每行有三个数，$x$，$y$，$z$，代表给第 $x$ 个到第 $y$ 个学员每人增加 $z$ 分。

输出数据格式

输出仅一行，代表更改分数后，全体学员的最低成绩。

输入输出样例

输入 ##1	输出 ##1
3 2 1 1 1 1 2 1 2 3 1	2

说明与提示

对于 $60\%$ 的数据，有 $n \le 10^4$。

对于 $80\%$ 的数据，有 $n \le 10^5$。

对于 $100\%$ 的数据，有 $n \le 5\times 10^6$，$p \le n$，学生初始成绩 $\le 100$，$z \le 100$。

二、面壁者计划中的战略提升序列

在三体危机中，面壁者需要将一系列有效的战略行动混入大数量的行动序列中来迷惑三体文明。每个行动都有一个复杂度评分(不超过$10^6$)，有效的行动序列必须满足：

1. 后行动的复杂度严格大于前行动，因为复杂度递增可以增加三体文明理解难度
2. 行动必须按原始时间顺序执行，这样才能不引起三体文明发现有效的战略行动
3. 有效的行动序列越长越复杂，越能迷惑三体文明。

输入数据格式

第一行：整数 $n(n\le 5000)$，表示候选行动数量
第二行：$n$ 个整数 ，表示每个行动的复杂度评分（按时间顺序排列）

输出数据格式

一个整数，表示最长有效行动序列的长度

输入输出样例

输入 ##1	输出 ##1
6 1 2 4 1 3 4	4

说明与提示

选择复杂度为 $[1,2,3,4]$ 的行动序列（对应第1、2、5、6个行动），这是满足条件的最长有效行动序列。

三、宇宙广播（连通图问题）

黑暗森林威慑建立后，人类需在太阳系部署信号塔网络。现有$n$个信号塔和$m$条双向通信链路（链路可重复）。请计算还需建设多少条链路，才能使任意两塔直接或间接连通（实现宇宙广播能力）。

输入格式

• 多组数据（以$0$结束）
• 每组首行：$n$（塔数），$m$（现有链路数）
• 后续$m$行：每行两个整数（连接的塔编号）

输出格式

• 每组一行：还需建设的最少链路数

样例

输入	输出
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0	1 0 2 998

数据规模与约定 对于 100% 的数据，保证 1 $<=$ n < 1000 。

四、曲率驱动

人类启动光速飞船计划。韦德他们研究发现有$m$种必须的矿物，而这些矿物在太空中近乎无限，但是散布在太空各处，采矿飞船携带燃料有限，所以他们每次出去采矿都需要认证规划。现在他们可以大致确定采集第$i$种需时间$a_i$，价值$b_i$。飞船总航行时间为$t$，请计算如何采集能使总价值最大（例如：$t=70$时可采$2$份$1$号矿物，价值$140$）。

输入格式

• 首行：$t$（总时间），$m$（矿物种类）
• 后续$m$行：每行$a_i, b_i$（采集时间和价值）

输出格式

• 一个整数：最大总价值

样例

输入	输出
70 3 71 100 69 1 1 2	140

数据范围

• 对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
• 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

提交代码格式：

--张三
  t1.cpp
  t2.cpp
  t3.cpp
  t4.cpp

*学习笔记

暂没有学习笔记，快来抢first blood ！