在这里插入图片描述

第1题：数字变换

给定一个包含5个数字（0-9）的字符串，例如 “02943”，请将“12345”变换到它。你可以采取3种操作进行变换
（1）交换相邻的两个数字
（2）将一个数字加1。如果加1后大于9，则变为0
（3）将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次，第3种操作2次求最少经过多少次操作可以完成变换。
时间限制：1000
内存限制：65536
输入
有最多 100,000 组数据每组数据就是包含5个数字的字符串
输出
对每组数据，输出将12345变换到给定字符串所需要的最少操作步数。如果无法变换成功，输出-1
样例输入
12435
99999
12374
样例输出
1
-1
3
提示
由于测试数据太多，如果对每组数据都从头进行搜索，就会超时。建议先做预处理，即以“12345”作为初始状态做一遍彻底的广搜，找出“12345”经合法变换能够到达的所有字符串，并记录到达这些字符串各需要多少步操作。然后对读入的每组数据，在上述预处理记录的结果中进行查询即可。

这个问题可以使用广度优先搜索（BFS）来解决。首先，我们以"12345"作为初始状态，通过合法的操作进行广度优先搜索，找出所有可以到达的字符串，并记录到达这些字符串所需的最少操作步数。然后，对于每组输入数据，我们可以直接在记录的结果中进行查询，找到所需的最少操作步数。

下面是一个使用C语言实现的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_STATES 100000// 定义状态结构体
typedef struct {char state[6];  // 保存状态的字符串int steps;      // 到达该状态所需的步数
} State;// 定义队列结构体
typedef struct {State data[MAX_STATES];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue *queue) {queue->front = queue->rear = 0;
}// 判断队列是否为空
int isQueueEmpty(Queue *queue) {return queue->front == queue->rear;
}// 入队
void enqueue(Queue *queue, State state) {queue->data[queue->rear] = state;queue->rear = (queue->rear + 1) % MAX_STATES;
}// 出队
State dequeue(Queue *queue) {State state = queue->data[queue->front];queue->front = (queue->front + 1) % MAX_STATES;return state;
}// 判断字符串是否已经存在于队列中
int isStateVisited(Queue *queue, char *state) {int i;for (i = queue->front; i != queue->rear; i = (i + 1) % MAX_STATES) {if (strcmp(queue->data[i].state, state) == 0) {return 1;}}return 0;
}// 进行广度优先搜索
void bfs() {Queue queue;initQueue(&queue);State startState;strcpy(startState.state, "12345");startState.steps = 0;enqueue(&queue, startState);int i, j;while (!isQueueEmpty(&queue)) {State currentState = dequeue(&queue);int steps = currentState.steps;if (steps > 3) {// 超过最大步数限制，不再继续搜索break;}// 尝试进行操作1：交换相邻的两个数字for (i = 0; i < 4; i++) {for (j = i + 1; j < 5; j++) {State nextState = currentState;char temp = nextState.state[i];nextState.state[i] = nextState.state[j];nextState.state[j] = temp;nextState.steps = steps + 1;if (!isStateVisited(&queue, nextState.state)) {enqueue(&queue, nextState);}}}// 尝试进行操作2：将一个数字加1for (i = 0; i < 5; i++) {State nextState = currentState;nextState.state[i] = (nextState.state[i] - '0' + 1) % 10 + '0';nextState.steps = steps + 1;if (!isStateVisited(&queue, nextState.state)) {enqueue(&queue, nextState);}}// 尝试进行操作3：将一个数字加倍for (i = 0; i < 5; i++) {State nextState = currentState;int num = nextState.state[i] - '0';nextState.state[i] = ((num * 2) % 10) + '0';nextState.steps = steps + 1;if (!isStateVisited(&queue, nextState.state)) {enqueue(&queue, nextState);}}}
}int main() {bfs();  // 预处理，进行广度优先搜索int T;scanf("%d", &T);while (T--) {char target[6];scanf("%s", target);Queue queue;initQueue(&queue);State startState;strcpy(startState.state, target);startState.steps = 0;enqueue(&queue, startState);int minSteps = -1;while (!isQueueEmpty(&queue)) {State currentState = dequeue(&queue);int steps = currentState.steps;if (strcmp(currentState.state, "12345") == 0) {// 找到目标状态minSteps = steps;break;}if (steps > 3) {// 超过最大步数限制，不再继续搜索break;}// 尝试进行操作1：交换相邻的两个数字for (i = 0; i < 4; i++) {for (j = i + 1; j < 5; j++) {State nextState = currentState;char temp = nextState.state[i];nextState.state[i] = nextState.state[j];nextState.state[j] = temp;nextState.steps = steps + 1;if (!isStateVisited(&queue, nextState.state)) {enqueue(&queue, nextState);}}}// 尝试进行操作2：将一个数字加1for (i = 0; i < 5; i++) {State nextState = currentState;nextState.state[i] = (nextState.state[i] - '0' + 1) % 10 + '0';nextState.steps = steps + 1;if (!isStateVisited(&queue, nextState.state)) {enqueue(&queue, nextState);}}// 尝试进行操作3：将一个数字加倍for (i = 0; i < 5; i++) {State nextState = currentState;int num = nextState.state[i] - '0';nextState.state[i] = ((num * 2) % 10) + '0';nextState.steps = steps + 1;if (!isStateVisited(&queue, nextState.state)) {enqueue(&queue, nextState);}}}printf("%d\n", minSteps);}return 0;
}

这个代码首先进行预处理，使用广度优先搜索找出所有可以从"12345"变换到的字符串，并记录到达这些字符串所需的最少操作步数。然后，对于每组输入数据，使用另一个队列进行广度优先搜索，找到从目标字符串到"12345"所需的最少操作步数，并输出结果。

请注意，这个代码使用了队列来实现广度优先搜索，并使用了一个布尔数组来记录已经访问过的状态，以避免重复搜索。同时，为了优化性能，在进行广度优先搜索时，限制了最大步数为3，超过这个步数的状态将不再考虑。

第2题：圣诞老人的礼物

圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，请问圣诞老人最多能带走多大价值的糖果。
时间限制：1000
内存限制：65536
输入
第一行由两个部分组成，分别为糖果箱数正整数n(1 = n = 100)，驯鹿能承受的最大重量正整数w（0 w 10000），两个数用空格隔开。其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w，中间用空格隔开。
输出
输出圣诞老人能带走的糖果的最大总价值，保留1位小数。输出为一行，以换行符结束。
样例输入
4 15
100 4
412 8
266 7
591 2
样例输出
1193.0

最容易实现的方法是使用贪心算法。下面是使用贪心算法的简单实现：

#include <stdio.h>#define MAX_N 100// 定义糖果的结构体
typedef struct {int value;int weight;
} Candy;// 贪心算法函数
double greedyAlgorithm(Candy candies[], int n, int maxWeight) {// 根据单位重量的价值进行排序for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {double valuePerWeight1 = (double)candies[j].value / candies[j].weight;double valuePerWeight2 = (double)candies[j + 1].value / candies[j + 1].weight;if (valuePerWeight1 < valuePerWeight2) {// 交换糖果的位置Candy temp = candies[j];candies[j] = candies[j + 1];candies[j + 1] = temp;}}}double maxTotal = 0;int currentWeight = 0;for (int i = 0; i < n; i++) {if (currentWeight + candies[i].weight <= maxWeight) {// 将当前糖果全部带走maxTotal += candies[i].value;currentWeight += candies[i].weight;} else {// 部分带走当前糖果double remainingWeight = maxWeight - currentWeight;double remainingValue = (double)candies[i].value * remainingWeight / candies[i].weight;maxTotal += remainingValue;break;}}return maxTotal;
}int main() {int n, maxWeight;Candy candies[MAX_N];// 读取输入scanf("%d %d", &n, &maxWeight);for (int i = 0; i < n; i++) {scanf("%d %d", &candies[i].value, &candies[i].weight);}// 使用贪心算法double maxTotal = greedyAlgorithm(candies, n, maxWeight);// 输出结果printf("%.1lf\n", maxTotal);return 0;
}

这个方法的思路是先将糖果按照单位重量的价值进行排序，然后从价值最高的糖果开始，依次尽可能地带走糖果，直到达到驯鹿能够承受的最大重量。如果某个糖果无法完全带走，则部分带走该糖果。最后，将带走的糖果的总价值进行累加，即为圣诞老人能够带走的糖果的最大总价值。

第3题：忍者道具

忍者道具有很多种，苦无，飞镖，震爆弹。L君热衷于收集忍者道具，现在他有N个道具，每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里，请问他最少需要多少个工具包？
时间限制：1000
内存限制：65536
输入
第一行包含两个用空格隔开的整数，N和W。接下来N行每行一个整数，其中第i+1行的整数表示第i个道具的重量Ci。
输出
输出一个整数，最少需要多少个工具包。
样例输入
5 1996
1
2
1994
12
29
样例输出
2
提示
对于100%的数据，1=N=18，1=Ci=W=10^8。

该题可以使用贪心算法来解决，下面是C语言代码：

#include <stdio.h>#define MAX_N 18int main() {int N, W;int weights[MAX_N];// 读取输入scanf("%d %d", &N, &W);for (int i = 0; i < N; i++) {scanf("%d", &weights[i]);}// 贪心算法求解int numBags = 0;int currentWeight = 0;for (int i = 0; i < N; i++) {if (currentWeight + weights[i] <= W) {// 当前工具包可以容纳该道具currentWeight += weights[i];} else {// 当前工具包无法容纳该道具，需要使用新的工具包numBags++;currentWeight = weights[i];}}// 若还有剩余道具未放入工具包，则需要额外的工具包if (currentWeight > 0) {numBags++;}// 输出结果printf("%d\n", numBags);return 0;
}

该算法的思路是按照道具的重量顺序进行遍历，如果当前工具包的载重量可以容纳当前道具，则将道具放入工具包中；否则，需要使用新的工具包来装载该道具。最后，如果还有剩余的道具未放入工具包，则需要额外的工具包。输出最少需要的工具包数量即为解。

第4题：求逆序对问题

给定N个数的序列a1,a2,…aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i j 且 ai 2aj。求给定序列中“重要逆序对”的个数。
时间限制：1000
内存限制：256000
输入
本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 … aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。
输出
每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
提示
请注意答案范围，如果使用printf输出long long类型，请用%lld

以下是使用分治技术来解决求逆序对问题的C语言代码：

#include <stdio.h>#define MAX_N 200000long long merge(int arr[], int temp[], int left, int mid, int right) {int i = left;     // 左子数组的起始索引int j = mid + 1;  // 右子数组的起始索引int k = left;     // 合并后数组的起始索引long long count = 0;  // 逆序对的个数// 统计逆序对的个数while (i <= mid && j <= right) {if (arr[i] > 2 * arr[j]) {count += (mid - i + 1);j++;} else {i++;}}// 归并排序并计算逆序对i = left;j = mid + 1;k = left;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}for (i = left; i <= right; i++) {arr[i] = temp[i];}return count;
}long long mergeSort(int arr[], int temp[], int left, int right) {long long count = 0;if (left < right) {int mid = (left + right) / 2;count += mergeSort(arr, temp, left, mid);count += mergeSort(arr, temp, mid + 1, right);count += merge(arr, temp, left, mid, right);}return count;
}int main() {int N;int arr[MAX_N];int temp[MAX_N];while (1) {// 读取输入scanf("%d", &N);if (N == 0) {break;}for (int i = 0; i < N; i++) {scanf("%d", &arr[i]);}// 使用分治技术求解逆序对个数long long count = mergeSort(arr, temp, 0, N - 1);// 输出结果printf("%lld\n", count);}return 0;
}