1.雀魂启动！
小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
- 总共有36张牌，每张牌是1~9。每个数字4张牌。
- 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
- 14张牌中有2张相同数字的牌，称为雀头。
- 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）
例如：
1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。
现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32M，其他语言64M
输入描述：
输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。
输出描述：
输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0
示例1
输入例子：
1 1 1 2 2 2 5 5 5 6 6 6 9
输出例子：
9
例子说明：
可以组成1,2,6,7的4个刻子和9的雀头
示例2
输入例子：
1 1 1 1 2 2 3 3 5 6 7 8 9
输出例子：
4 7
例子说明：
用1做雀头，组123,123,567或456,789的四个顺子
示例3
输入例子：
1 1 1 2 2 2 3 3 3 5 7 7 9
输出例子：
0
例子说明：
来任何牌都无法和牌
代码展示：
#include <stdio.h>
#include <stdbool.h>
#define NUM_CARDS 9 // 定义常量NUM_CARDS为9，表示麻将牌的数字范围是1到9
// 递归判断是否能将12张牌组成4个刻子或顺子
bool can_form_melds(int hand[NUM_CARDS + 1], int start) {
// 遍历从start位置开始的所有牌
for (int i = start; i <= NUM_CARDS; i++) {
if (hand[i] >= 3) { // 尝试使用一个刻子（三张相同的牌）
hand[i] -= 3; // 移除一个刻子
if (can_form_melds(hand, i)) { // 递归检查剩余牌是否能继续组成刻子或顺子
hand[i] += 3; // 恢复被移除的刻子
return true; // 如果能组成，返回true
}
hand[i] += 3; // 恢复被移除的刻子
}
if (i <= 7 && hand[i] > 0 && hand[i + 1] > 0 && hand[i + 2] > 0) { // 尝试使用一个顺子（连续三张牌）
hand[i]--; // 移除顺子的第一张牌
hand[i + 1]--; // 移除顺子的第二张牌
hand[i + 2]--; // 移除顺子的第三张牌
if (can_form_melds(hand, i)) { // 递归检查剩余牌是否能继续组成刻子或顺子
hand[i]++; // 恢复被移除的顺子的第一张牌
hand[i + 1]++; // 恢复被移除的顺子的第二张牌
hand[i + 2]++; // 恢复被移除的顺子的第三张牌
return true; // 如果能组成，返回true
}
hand[i]++; // 恢复被移除的顺子的第一张牌
hand[i + 1]++; // 恢复被移除的顺子的第二张牌
hand[i + 2]++; // 恢复被移除的顺子的第三张牌
}
}
// 检查是否所有牌都已经被成功组合
for (int i = 1; i <= NUM_CARDS; i++) {
if (hand[i] > 0) return false; // 如果还有未使用的牌，返回false
}
return true; // 所有牌都被成功组合，返回true
}
// 判断是否可以组成和牌
bool is_valid_hand(int hand[NUM_CARDS + 1]) {
// 枚举所有可能的雀头（两张相同的牌）
for (int i = 1; i <= NUM_CARDS; i++) {
if (hand[i] >= 2) { // 找到一个可能的雀头
hand[i] -= 2; // 暂时移除这两张作为雀头
if (can_form_melds(hand, 1)) { // 检查剩余12张牌能否组成4个刻子或顺子
hand[i] += 2; // 恢复被移除的两张牌
return true; // 如果可以组成，返回true
}
hand[i] += 2; // 恢复被移除的两张牌
}
}
return false; // 没有找到有效的雀头和组合，返回false
}
int main() {
int hand[NUM_CARDS + 1]; // 用来存储每种牌的数量，下标1到9分别表示牌1到9的数量
int num; // 存储当前输入的牌
// 输入多组测试用例
while (1) {
// 初始化手牌
for (int i = 1; i <= NUM_CARDS; i++) {
hand[i] = 0; // 初始化，将每种牌的数量设为0
}
// 输入13张牌
for (int i = 0; i < 13; i++) {
if (scanf("%d", &num) == EOF) { // 如果输入结束（EOF），退出程序
return 0;
}
hand[num]++; // 增加对应牌的数量
}
bool found = false; // 标志是否找到能和牌的牌
// 枚举剩下的23张牌中的每一张，看能否和牌
for (int i = 1; i <= NUM_CARDS; i++) {
if (hand[i] < 4) { // 如果某张牌的数量少于4
hand[i]++; // 假设加入这张牌
if (is_valid_hand(hand)) { // 检查是否可以和牌
if (found) {
printf(" "); // 如果之前已经找到其他能和的牌，先输出一个空格分隔
}
printf("%d", i); // 输出这张牌
found = true; // 标记为找到能和的牌
}
hand[i]--; // 恢复这张牌的数量
}
}
if (!found) { // 如果没有找到任何能和的牌
printf("0"); // 输出0
}
printf("\n"); // 换行，准备下一组输入
}
return 0; // 程序结束
}
2.毕业旅行问题
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32M，其他语言64M
输入描述：
城市个数n（1<n≤20，包括北京） 城市间的车票价钱 n行n列的矩阵 m[n][n]
输出描述：
最小车费花销 s
示例1
输入例子：
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0输出例子：
13例子说明：
共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
代码展示：
#include <stdio.h>
#include <limits.h>
#define MAX_CITIES 20 // 最大支持的城市数量
#define INF INT_MAX // 定义无穷大的值
// 辅助函数，用于返回两个整数中的较小值
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
int n; // 城市数量
scanf("%d", &n); // 读取城市数量
// 存储城市之间的车票费用
int cost[MAX_CITIES][MAX_CITIES];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]); // 读取城市 i 和城市 j 之间的车票费用
}
}
// dp[mask][i] 表示从起点出发，经过mask表示的路径，最后到达城市i的最小花费
int dp[1 << MAX_CITIES][MAX_CITIES];
// 初始化 dp 数组
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
dp[mask][i] = INF; // 将所有状态的最小花费初始化为无穷大
}
}
dp[1][0] = 0; // 从城市0（北京）出发，状态为1表示已经访问过城市0（北京），花费为0
// 状态转移
for (int mask = 1; mask < (1 << n); mask++) { // 遍历所有可能的状态
for (int i = 0; i < n; i++) { // 遍历当前状态下的所有城市 i
if (dp[mask][i] < INF) { // 如果从当前状态到城市 i 有合法路径
for (int j = 0; j < n; j++) { // 遍历所有未访问的城市 j
if (!(mask & (1 << j))) { // 如果城市 j 还没有被访问
int nextMask = mask | (1 << j); // 更新状态，将城市 j 标记为已访问
dp[nextMask][j] = min(dp[nextMask][j], dp[mask][i] + cost[i][j]); // 更新到达城市 j 的最小花费
}
}
}
}
}
// 从最后一个状态，找到回到城市0的最小花费
int result = INF; // 初始化结果为无穷大
for (int i = 1; i < n; i++) { // 遍历所有可能的城市 i
result = min(result, dp[(1 << n) - 1][i] + cost[i][0]); // 更新最小车费花销
}
printf("%d\n", result); // 输出最小车费花销
return 0; // 主函数返回0，表示程序成功结束
}