编程与编程语言
【题解】网线主管
【题目描述】
仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。
该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。
你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。
【输入描述】
第一行包含两个整数N和K，以单个空格隔开。N（1 ≤ N ≤ 10000）是库存中的网线数，K（1 ≤ K ≤ 10000）是需要的网线数量。
接下来N行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。
【输出描述】
网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。
若无法得到长度至少为1cm的指定数量的网线，则必须输出“0.00”（不包含引号）。
【样例输入】
4 11 8.02 7.43 4.57 5.39
【样例输出】
2.00
【数据结构】优先队列（1）
【题解】合并有序表
【题目描述】
k路归并问题
把k个有序表合并成一个有序表。
元素共有n个。
【输入描述】
读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数，表示第i个序列。
总数小于100000。
【输出描述】
输出有序序列
【样例输入】
6 3 1 2 3 3 4 5 6 3 7 10 13 3 8 11 14 3 9 12 15 3 0 16 17
【样例输出】
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
【题解】河中跳房子
【题目描述】
每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。
在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。
请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？
【输入描述】
第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。
【输出描述】
一个整数，最长可能的最短跳跃距离。
【样例输入】
25 5 2 2 11 14 17 21
【样例输出】
4
【题解】搭配购买
【题目描述】
Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，…，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。
【输入描述】
第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。
第2~n+1行，每行ci，di表示i朵云的价钱和价值。
第n+2~n+1+m行，每行ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。
【输出描述】
一行，表示可以获得的最大价值。
【样例输入】
5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2
【样例输出】
1
【数据范围】
30%的数据保证：n≤100；
50%的数据保证：n≤1,000；m≤100；w≤1,000；
100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000。
【题解】打击犯罪
【题目描述】
某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。
【输入描述】
第一行一个正整数n。接下来的n行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第i行存在正整数k，表示i，k两个团伙可以直接联系。
【输出描述】
一个正整数，为k的最小值。
【样例输入】
7 2 2 5 3 1 3 4 2 2 4 2 2 3 3 1 6 7 2 5 7 2 5 6
【样例输出】
1
【算法】动态规划—区间DP问题
一、定义
区间DP是动态规划的一种特殊形式，主要用于解决涉及区间操作的问题，比如合并区间、分割区间、区间匹配等。
其核心思想是通过枚举区间的划分点，将大区间的问题分解为小区间的子问题，逐步求解并保存中间结果。
二、基本特征
问题定义：通常涉及一个序列或区间，如数组、字符串等。
状态表示：一般用
dp[i][j]表示区间[i, j]的最优解。转移方程：通过枚举区间内的某个分割点
k，将[i, j]拆分为[i, k]和[k+1, j]，然后合并子问题的解。初始化：通常
dp[i][i]表示单个元素的最优解（如dp[i][i] = 0或dp[i][i] = cost[i]）。遍历顺序：一般采用区间长度从小到大的顺序计算，确保子问题先被求解。
三、区间DP模板
for (int len = 1; len <= n; len++) { // 枚举区间长度 for (int i = 0; i + len - 1 < n; i++) { // 枚举起点i int j = i + len - 1; // 计算终点j if (len == 1) { // 初始化 dp[i][j] = ...; continue; } for (int k = i; k < j; k++) { // 枚举分割点k dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost); } } }四、例题：石子合并
问题描述：有 n 堆石子排成一排，每次只能合并相邻的两堆，合并的代价是两堆石子的总数。求将所有石子合并成一堆的最小总代价。
输入: stones = [3, 1, 2, 4] 输出: 20 解释: 1. 合并 [1, 2] → 代价=3, 剩余 [3, 3, 4] 2. 合并 [3, 3] → 代价=6, 剩余 [6, 4] 3. 合并 [6, 4] → 代价=10, 总代价=3+6+10=19
(1) 状态定义
dp[i][j]：表示合并区间[i, j]的所有石子堆的最小总代价。初始化：
如果
i == j（即区间长度为1），dp[i][j] = 0（因为不需要合并）。否则
dp[i][j] = +∞（初始化为极大值，方便后续取最小值）。
(2) 状态转移方程
对于区间
[i, j]，枚举所有可能的分割点k（i ≤ k < j），将其分成两个子区间：[i, k]和[k+1, j]。合并这两个子区间的总代价是：
dp[i][k]（合并[i, k]的代价）dp[k+1][j]（合并[k+1, j]的代价）sum(i, j)（当前合并的代价，即区间[i, j]的石子总重量）。因此，状态转移方程为：
(3) 计算顺序
按区间长度从小到大计算：
先计算所有长度为2的区间，再计算长度为3的区间，依此类推，直到计算整个区间
[0, n-1]。前缀和优化：
为了快速计算
sum(i, j)，可以预先计算前缀和数组prefix：
【题解】团伙
【题目描述】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友；
2、我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
【输入描述】
第1行为n和m，1<n<1000,1<=m<=100 000；
以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。
【输出描述】
一个整数，表示这n个人最多可能有几个团伙。
【样例输入】
6 4 1 1 4 0 3 5 0 4 6 1 1 2
【样例输出】
3