C语言算法赛——蓝桥杯（省赛试题）

版权声明：本文为博主作者：慢了半拍i原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/weixin_56641478/article/details/135726057

一、十四届C/C++程序设计C组试题

十四届程序C组试题A

#include <stdio.h>
int main()
{
    long long sum = 0;
    int n = 20230408;
    int i = 0;

    // 累加从1到n的所有整数
    for (i = 1; i <= n; i++)
    {
        sum += i;
    }

    // 输出结果
    printf("%lld\n", sum);

    return 0;
}

C++

//十四届程序C组试题B
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<time.h>

// 时间字符串解析为结构体 tm
void parseTime(char* timeString, struct tm* timeStruct) {
    sscanf(timeString, "%d-%d-%d %d:%d:%d",
        &timeStruct->tm_year, &timeStruct->tm_mon, &timeStruct->tm_mday,
        &timeStruct->tm_hour, &timeStruct->tm_min, &timeStruct->tm_sec);

    // tm_year表示的是自1900年以来的年数，需要减去1900
    timeStruct->tm_year -= 1900;
    // tm_mon表示的是0-11的月份，需要减去1
    timeStruct->tm_mon -= 1;
}

// 每一对相邻的上下班打卡之间的时间差
int calculateTimeDifference(char* time1, char* time2) {
    struct tm start, end;

    // 解析时间字符串为结构体 tm
    parseTime(time1, &start);
    parseTime(time2, &end);

    // 使用 mktime 将 tm 结构体转换为时间戳
    time_t startTime = mktime(&start);
    time_t endTime = mktime(&end);

    // 计算时间差
    return difftime(endTime, startTime);
}

int main() {
    // 打卡记录数组
    char* punchRecords[] = {
        "2022-01-01 07:58:02",
        "2022-01-01 12:00:05",
        "2022-01-01 16:01:35",
        "2022-01-02 00:20:05"
    };

    int numRecords = sizeof(punchRecords) / sizeof(punchRecords[0]);

    // 按照时间顺序对打卡记录进行排序
    for (int i = 0; i < numRecords - 1; i++) {
        for (int j = 0; j < numRecords - i - 1; j++) {
            if (strcmp(punchRecords[j], punchRecords[j + 1]) > 0) {
                // 交换记录
                char* temp = punchRecords[j];
                punchRecords[j] = punchRecords[j + 1];
                punchRecords[j + 1] = temp;
            }
        }
    }

    // 计算总工作时长
    int totalWorkDuration = 0;
    for (int i = 0; i < numRecords - 1; i += 2) {
        totalWorkDuration += calculateTimeDifference(punchRecords[i], punchRecords[i + 1]);
    }

    // 输出总工作时长
    printf("小蓝在2022年度的总工作时长是%d秒。\n", totalWorkDuration);

    return 0;
}

C++

十四届程序C组试题C

#include <stdio.h>
int main() {
    int n; // 事件数量
    scanf("%d", &n);

    int A[n], B[n], C[n]; // 存储每个事件中的A、B、C值
    int maxEvents = -1; // 最多发生的事件数量
    int X = 0, Y = 0, Z = 0; // 初始士兵数量

    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d", &A[i], &B[i], &C[i]);

        // 计算每个国家的士兵数量
        X += A[i];
        Y += B[i];
        Z += C[i];

        // 判断是否有国家获胜
        if ((X > Y + Z) || (Y > X + Z) || (Z > X + Y)) {
            // 更新最多发生的事件数量
            maxEvents = i + 1;
        }
    }

    printf("%d\n", maxEvents);

    return 0;
}

C++

#include <stdio.h>
int maximize_substrings(char* s)
{
    int count = 0;
    int i, n;

    // 遍历字符串，从第二个字符开始
    for (i = 1; s[i] != '\0'; ++i)
    {
        // 如果当前位置是'?'，则尽量使其与前一个字符不同
        if (s[i] == '?') {
            s[i] = (s[i - 1] == '1') ? '0' : '1';
        }

        // 计算互不重叠的00和11子串的个数
        if (s[i] == s[i - 1])
        {
            count += 1;
        }
    }

    return count;
}

int main()
{
    char input_str[] = "1?0?1";
    int result = maximize_substrings(input_str);

    printf("互不重叠的00和11子串个数：%d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <string.h>

// 函数：计算最小翻转次数
int min_flips_to_match(char S[], char T[])
{
    int n = strlen(S);
    int flips = 0;

    // 从第二个位置到倒数第二个位置进行遍历
    for (int i = 1; i < n - 1; ++i)
    {
        // 如果当前位置的字符与目标串不同
        if (S[i] != T[i])
        {
            // 进行翻转操作
            flips++;
            S[i] = T[i];
            S[i + 1] = (S[i + 1] == '0') ? '1' : '0';
            S[i + 2] = (S[i + 2] == '0') ? '1' : '0';
        }
    }

    return flips;
}

int main()
{
    // 示例输入
    char S[] = "01010";
    char T[] = "00000";

    // 计算最小翻转次数
    int result = min_flips_to_match(S, T);

    // 输出结果
    printf("Minimum flips required: %d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>

#define MOD 998244353

// 函数：计算矩阵子矩阵价值的和
int matrixSubmatrixSum(int n, int m, int matrix[n][m])
{
    // 预处理，计算每个位置的最大值和最小值
    int maxVal[n][m];
    int minVal[n][m];

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (i > 0)
            {
                maxVal[i][j] = (maxVal[i][j] > maxVal[i - 1][j]) ? maxVal[i][j] : maxVal[i - 1][j];
                minVal[i][j] = (minVal[i][j] < minVal[i - 1][j]) ? minVal[i][j] : minVal[i - 1][j];
            }
            if (j > 0)
            {
                maxVal[i][j] = (maxVal[i][j] > maxVal[i][j - 1]) ? maxVal[i][j] : maxVal[i][j - 1];
                minVal[i][j] = (minVal[i][j] < minVal[i][j - 1]) ? minVal[i][j] : minVal[i][j - 1];
            }
            maxVal[i][j] = (maxVal[i][j] > matrix[i][j]) ? maxVal[i][j] : matrix[i][j];
            minVal[i][j] = (minVal[i][j] < matrix[i][j]) ? minVal[i][j] : matrix[i][j];
        }
    }

    // 计算答案
    int result = 0;

    for (int a = 1; a <= n; ++a)
    {
        for (int b = 1; b <= m; ++b)
        {
            for (int i = 0; i + a - 1 < n; ++i)
            {
                for (int j = 0; j + b - 1 < m; ++j)
                {
                    int maxInSubmatrix = maxVal[i + a - 1][j + b - 1];
                    int minInSubmatrix = minVal[i + a - 1][j + b - 1];
                    result = (result + ((long long)maxInSubmatrix * minInSubmatrix) % MOD) % MOD;
                }
            }
        }
    }

    return result;
}

int main()
{
    // 示例输入
    int n = 3, m = 3;
    int matrix[3][3] ={{1, 2, 3},{4, 5, 6},{7, 8, 9}};

    // 计算答案
    int result = matrixSubmatrixSum(n, m, matrix);

    // 输出结果
    printf("Sum of submatrix values: %d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <math.h>

#define MOD 998244353

// 计算欧拉函数
long long phi(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
    if (n > 1)
        result -= result / n;
    return result % MOD;
}

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);

    // 计算欧拉函数
    long long euler_a = phi(a);
    long long euler_ab = phi((long long)pow(a, b));

    // 输出结果对MOD取模的值
    printf("%lld\n", (euler_ab - euler_a + MOD) % MOD);

    return 0;
}

C++

#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int max_xor_difference(int arr[], int n) {
    int prefix_xor_left[100000];
    int prefix_xor_right[100000];

    // 计算从左往右的前缀异或和
    prefix_xor_left[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix_xor_left[i] = prefix_xor_left[i - 1] ^ arr[i];
    }

    // 计算从右往左的前缀异或和
    prefix_xor_right[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        prefix_xor_right[i] = prefix_xor_right[i + 1] ^ arr[i];
    }

    // 计算两个不相交子段内数的异或和的差值的最大值
    int max_difference = 0;
    for (int i = 0; i < n - 1; ++i) {
        max_difference = max(max_difference, max(prefix_xor_left[i], prefix_xor_right[i + 1]));
    }

    return max_difference;
}

int main() {
    int n;
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[100000];
    printf("Enter the array elements: ");
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }

    int result = max_xor_difference(arr, n);

    printf("Maximum XOR difference of two non-overlapping subarrays: %d\n", result);

    return 0;
}

C++

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

void find_numbers(int arr[], int n) {
    int i_min = -1, j_min = -1;

    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (gcd(arr[i], arr[j]) > 1) {
                if (i_min == -1 || i < i_min || (i == i_min && j < j_min)) {
                    i_min = i;
                    j_min = j;
                }
            }
        }
    }

    if (i_min == -1) {
        printf("No such pair found.\n");
    } else {
        printf("Pair with minimum i and j: (%d, %d)\n", i_min + 1, j_min + 1);
    }
}

int main() {
    int n;
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[1000];
    printf("Enter the array elements: ");
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }

    find_numbers(arr, n);

    return 0;
}

C++

#include <stdio.h>

long long calculate_subtree_size(int m, long long k) {
    long long subtree_size = 1;

    // 计算当前结点的深度
    long long depth = 0;
    while (k > 0) {
        k = (k - 1) / m;
        depth++;
    }

    // 计算子树的结点数量
    for (long long i = depth - 1; i > 0; --i) {
        subtree_size = subtree_size * m + i;
    }

    return subtree_size;
}

int main() {
    int m;
    printf("Enter the degree of the tree (m): ");
    scanf("%d", &m);

    long long k;
    printf("Enter the node number (k): ");
    scanf("%lld", &k);

    long long result = calculate_subtree_size(m, k);

    printf("Number of nodes in the subtree corresponding to node %lld: %lld\n", k, result);

    return 0;
}

C++

二、十四届C/C++程序设计B组试题

#include <stdio.h>
#include <string.h>

int main() {
    char array[] = "5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";
    int arraySize = strlen(array);
    char date[9];  // 存储提取的8位子序列
    int uniqueDates = 0;  // 记录不同日期数量

    for (int i = 0; i <= arraySize - 8; ++i) {
        // 提取8位子序列
        strncpy(date, array + i, 8);
        date[8] = '\0';  // 添加字符串结束符

        // 解析日期
        int year, month, day;
        sscanf(date, "%4d%2d%2d", &year, &month, &day);

        // 检查是否为2023年的合法日期
        if (year == 2023 && month >= 1 && month <= 12 && day >= 1 && day <= 31) {
            // 记录合法日期，并避免重复计数
            uniqueDates++;
            i += 7;  // 移动到下一个可能的子序列的起始位置
        }
    }

    // 输出结果
    printf("满足条件的不同日期数量为：%d\n", uniqueDates);

    return 0;
}

C++

#include <stdio.h>
#include <math.h>

// 定义信息熵函数
double entropy_equation(double x) {
    double p0 = x / 23333333;
    double p1 = (23333333 - x) / 23333333;
    double entropy = -(p0 * log2(p0) + p1 * log2(p1));
    return entropy - 11625907.5798;
}

// 二分法求解方程
double binary_search() {
    double low = 0.0;
    double high = 23333333;
    double epsilon = 0.000001;  // 精度要求

    while (high - low > epsilon) {
        double mid = (low + high) / 2.0;
        double result = entropy_equation(mid);

        if (result > 0) {
            high = mid;
        } else {
            low = mid;
        }
    }

    return low;
}

int main() {
    double zero_count = binary_search();
    printf("0 出现的次数为: %lf\n", zero_count);

    return 0;
}

C++

#include <stdio.h>

// 计算最大公约数的欧几里得算法
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 计算数组中所有元素的最大公约数
int findGCD(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}

int main() {
    int n;
    printf("输入冶炼记录的数量 N: ");
    scanf("%d", &n);

    int A[n], B[n];

    printf("输入每条记录中的 A 和 B：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &A[i], &B[i]);
    }

    // 计算最小值
    int minV = findGCD(A, n);

    // 计算最大值
    int maxV = findGCD(B, n);

    printf("转换率V的最小值：%d\n", minV);
    printf("转换率V的最大值：%d\n", maxV);

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>

// 飞机结构体
struct Aircraft
{
    int arrivalTime;
    int hoverTime;
    int landingTime;
};

// 比较函数，用于排序
int compare(const void* a, const void* b)
{
    return (((struct Aircraft*)a)->arrivalTime + ((struct Aircraft*)a)->hoverTime) -
        (((struct Aircraft*)b)->arrivalTime + ((struct Aircraft*)b)->hoverTime);
}

// 判断是否可以全部安全降落的函数
int canLand(struct Aircraft aircraft[], int N)
{
    qsort(aircraft, N, sizeof(struct Aircraft), compare);

    int currentTime = 0;

    for (int i = 0; i < N; i++)
    {
        // 判断是否在时间窗口内降落
        if (currentTime + aircraft[i].landingTime > aircraft[i].arrivalTime + aircraft[i].hoverTime) {
            return 0; // 不能安全降落
        }

        // 更新当前时间
        currentTime = (currentTime + aircraft[i].landingTime > aircraft[i].arrivalTime)
            ? currentTime + aircraft[i].landingTime
            : aircraft[i].arrivalTime;
    }

    return 1; // 可以安全降落
}

int main()
{
    int N;
    printf("请输入飞机数量 N：");
    scanf("%d", &N);

    struct Aircraft* aircraft = (struct Aircraft*)malloc(N * sizeof(struct Aircraft));

    // 输入飞机信息
    for (int i = 0; i < N; i++)
    {
        printf("请输入第 %d 架飞机的到达时刻、盘旋时间和降落时间：", i + 1);
        scanf("%d %d %d", &aircraft[i].arrivalTime, &aircraft[i].hoverTime, &aircraft[i].landingTime);
    }

    // 判断是否可以全部安全降落
    if (canLand(aircraft, N))
    {
        printf("所有飞机可以全部安全降落。\n");
    }
    else
    {
        printf("有飞机无法安全降落。\n");
    }

    free(aircraft);
    return 0;
}

C++

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int minDeletionsForChain(int arr[], int N)
{
    int dp[N];
    int result = 0;

    for (int i = 0; i < N; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] % 10 == arr[i] / 10) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        result = max(result, dp[i]);
    }

    return N - result;
}

int main() {
    int N;
    printf("请输入数列的长度 N：");
    scanf("%d", &N);

    int arr[N];
    printf("请输入数列 A1, A2, ..., AN：");
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    int deletions = minDeletionsForChain(arr, N);
    printf("最少需要删除 %d 个数，使剩下的序列是接龙序列。\n", deletions);

    return 0;
}

C++

#include <stdio.h>

#define ROW 4
#define COL 5

void dfs(char grid[ROW][COL], int i, int j) {
    if (i < 0 || i >= ROW || j < 0 || j >= COL || grid[i][j] == '0') {
        return;
    }

    grid[i][j] = '0';  // 标记当前格子为已访问

    // 上下左右四个方向进行深度优先搜索
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j - 1);
    dfs(grid, i, j + 1);
}

int numIslands(char grid[ROW][COL])
{
    int count = 0;

    for (int i = 0; i < ROW; ++i) {
        for (int j = 0; j < COL; ++j) {
            if (grid[i][j] == '1') {
                ++count;
                dfs(grid, i, j);  // 深度优先搜索标记当前岛屿
            }
        }
    }

    return count;
}

int main()
{
    char grid[ROW][COL] = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    int result = numIslands(grid);
    printf("岛屿数量: %d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <string.h>

// 计算以c1开头、以c2结尾的子串个数
int countShortenedSubstrings(char S[], char c1, char c2, int K) {
    int n = strlen(S);
    int count = 0;

    for (int i = 0; i < n; ++i) {
        if (S[i] == c1) {
            for (int j = i + 1; j < n; ++j) {
                if (S[j] == c2) {
                    // 计算子串长度
                    int length = j - i + 1;
                    if (length >= K) {
                        // 符合条件，计数器加一
                        count++;
                    }
                }
            }
        }
    }

    return count;
}

int main() {
    char S[100];
    char c1, c2;
    int K;

    // 读取输入
    printf("Enter the string S: ");
    scanf("%s", S);
    printf("Enter the characters c1 and c2: ");
    scanf(" %c %c", &c1, &c2);
    printf("Enter the value of K: ");
    scanf("%d", &K);

    // 计算结果并输出
    int result = countShortenedSubstrings(S, c1, c2, K);
    printf("Number of shortened substrings: %d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <string.h>

// 计算以c1开头、以c2结尾的子串个数
int countShortenedSubstrings(char S[], char c1, char c2, int K) {
    int n = strlen(S);
    int count = 0;

    for (int i = 0; i < n; ++i) {
        if (S[i] == c1) {
            for (int j = i + 1; j < n; ++j) {
                if (S[j] == c2) {
                    // 计算子串长度
                    int length = j - i + 1;
                    if (length >= K) {
                        // 符合条件，计数器加一
                        count++;
                    }
                }
            }
        }
    }

    return count;
}

int main() {
    char S[100];
    char c1, c2;
    int K;

    // 读取输入
    printf("Enter the string S: ");
    scanf("%s", S);
    printf("Enter the characters c1 and c2: ");
    scanf(" %c %c", &c1, &c2);
    printf("Enter the value of K: ");
    scanf("%d", &K);

    // 计算结果并输出
    int result = countShortenedSubstrings(S, c1, c2, K);
    printf("Number of shortened substrings: %d\n", result);

    return 0;
}

C++

#include <stdio.h>

#define MAX_NODES 100

int adjacency_list[MAX_NODES][MAX_NODES];
int travel_times[MAX_NODES][MAX_NODES];

int dfs(int node, int parent, int skip_node, int n) {
    int total_time = 0;

    for (int i = 0; i < n; ++i) {
        if (i != parent && adjacency_list[node][i]) {
            total_time += dfs(i, node, skip_node, n);
        }
    }

    // 如果当前节点不是要跳过的节点，累加其摆渡车时间
    if (node != skip_node) {
        total_time += travel_times[node][parent] + travel_times[parent][node];
    }

    return total_time;
}

int calculate_travel_time(int n, int k, int skip_node) {
    int total_time = 0;

    for (int i = 1; i < k; ++i) {
        total_time += dfs(i, -1, skip_node, n);
    }

    return total_time;
}

int main() {
    int n = 6;
    int k = 4;
    int skip_node = 2;

    // 示例邻接列表和摆渡车时间
    int adjacency_list[6][6] = {{0, 1, 1, 0, 0, 0},
                                {1, 0, 0, 1, 1, 0},
                                {1, 0, 0, 0, 0, 1},
                                {0, 1, 0, 0, 0, 0},
                                {0, 1, 0, 0, 0, 0},
                                {0, 0, 1, 0, 0, 0}};

    int travel_times[6][6] = {{0, 3, 2, 0, 0, 0},
                              {3, 0, 0, 1, 4, 0},
                              {2, 0, 0, 0, 0, 5},
                              {0, 1, 0, 0, 0, 0},
                              {0, 4, 0, 0, 0, 0},
                              {0, 0, 5, 0, 0, 0}};

    int result = calculate_travel_time(n, k, skip_node);
    printf("If skip node %d, total travel time: %d\n", skip_node, result);

    return 0;
}

C++

#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 1000

// 表示树的邻接列表
int adjacency_list[MAX_NODES][MAX_NODES];
// 标记边是否被访问过
bool visited[MAX_NODES][MAX_NODES];
// 结果数组，记录断开的边的编号
int result[MAX_NODES];
// 当前断开的边的编号
int result_index;

// 深度优先搜索函数
void dfs(int node, int parent, int a, int b, int n) {
    for (int i = 0; i < n; ++i) {
        if (adjacency_list[node][i] && !visited[node][i]) {
            visited[node][i] = visited[i][node] = true;

            // 如果当前边的两个端点分别为a和b，说明这条边需要断开
            if ((node == a && i == b) || (node == b && i == a)) {
                result[result_index++] = i + 1; // 存储边的编号（从1开始）
            }

            dfs(i, node, a, b, n);
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化邻接列表和visited数组
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adjacency_list[u - 1][v - 1] = adjacency_list[v - 1][u - 1] = 1;
        visited[u - 1][v - 1] = visited[v - 1][u - 1] = false;
    }

    // 遍历每个数对，进行DFS判断是否可以断开
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);

        // 重置结果数组和结果索引
        result_index = 0;

        // 进行DFS遍历
        dfs(0, -1, a - 1, b - 1, n);

        // 如果结果索引为0，说明没有找到需要断开的边
        if (result_index == 0) {
            printf("-1\n");
        } else {
            // 输出断开的边的编号
            for (int j = 0; j < result_index; ++j) {
                printf("%d ", result[j]);
            }
            printf("\n");
        }
    }

    return 0;
}

C++

三、十四届C/C++程序设计A组试题

#include <stdio.h>

// 检查一个数字是否是幸运数字的函数
int is_lucky_number(int num) {
    char num_str[20]; // 用于将数字转换为字符串以便处理
    sprintf(num_str, "%d", num);
    int length = strlen(num_str);

    // 如果数字的位数为奇数，则不是幸运数字
    if (length % 2 != 0) {
        return 0; // 返回假
    }

    int half_length = length / 2;
    int first_half_sum = 0, second_half_sum = 0;

    // 计算前半部分数字的和
    for (int i = 0; i < half_length; i++) {
        first_half_sum += num_str[i] - '0'; // 将字符转换为数字
    }

    // 计算后半部分数字的和
    for (int i = half_length; i < length; i++) {
        second_half_sum += num_str[i] - '0';
    }

    // 判断前半部分和后半部分是否相等
    return first_half_sum == second_half_sum;
}

// 计算在给定范围内的幸运数字的数量
int count_lucky_numbers(int start, int end) {
    int count = 0;

    // 遍历给定范围内的所有数字
    for (int num = start; num <= end; num++) {
        // 如果是幸运数字，增加计数
        if (is_lucky_number(num)) {
            count++;
        }
    }

    return count;
}

int main() {
    int start_range = 1;
    int end_range = 100000000;

    // 调用函数计算幸运数字的数量
    int result = count_lucky_numbers(start_range, end_range);

    // 打印结果
    printf("There are %d lucky numbers between %d and %d.\n", result, start_range, end_range);

    return 0;
}

C++

#include <stdio.h>

// 定义最大题目数和最大分数
#define MAX_QUESTIONS 30
#define MAX_SCORE 100

// 计算小蓝所有可能的答题情况数量的函数
long long count_possible_ways() {
    int target_score = 70;
    int num_questions = 30;

    // 初始化动态规划数组
    long long dp[MAX_QUESTIONS + 1][MAX_SCORE + 1] = { 0 };
    dp[0][0] = 1;

    // 遍历每一道题目
    for (int i = 1; i <= num_questions; i++) {
        for (int j = 0; j <= target_score; j++) {
            // 如果不答这道题
            dp[i][j] += dp[i - 1][j];

            // 如果答对这道题，分数增加10
            if (j >= 10) {
                dp[i][j] += dp[i - 1][j - 10];
            }
        }
    }

    return dp[num_questions][target_score];
}

int main() {
    // 调用函数计算小蓝所有可能的答题情况数量
    long long possible_ways = count_possible_ways();

    // 打印结果
    printf("小蓝所有可能的答题情况有 %lld 种。\n", possible_ways);

    return 0;
}

C++

#include <stdio.h>
#include <math.h>

// 判断是否存在整数y和z，使得x = y^2 - z^2
int has_yz(int x) {
    int limit = (int)sqrt(x);

    // 遍历y的可能取值
    for (int y = 1; y <= limit; y++) {
        int z_square = y * y - x;

        // 如果z的平方为非负数且是完全平方数
        if (z_square >= 0 && sqrt(z_square) == (int)sqrt(z_square)) {
            return 1; // 存在满足条件的y和z
        }
    }

    return 0; // 不存在满足条件的y和z
}

// 计算满足条件的x的数量
int count_x(int L, int R) {
    int count = 0;

    // 遍历给定范围内的所有x
    for (int x = L; x <= R; x++) {
        // 如果存在整数y和z，使得x = y^2 - z^2
        if (has_yz(x)) {
            count++;
        }
    }

    return count;
}

int main() {
    int L, R;

    // 输入L和R的值
    printf("Enter the values of L and R: ");
    scanf("%d %d", &L, &R);

    // 调用函数计算满足条件的x的数量
    int result = count_x(L, R);

    // 输出结果
    printf("There are %d numbers x in the range [%d, %d] satisfying the condition.\n", result, L, R);

    return 0;
}

C++

#include <stdio.h>
#include <string.h>

// 计算满足条件的不同子串选择方案的数量
int count_substring_choices(char num_str[]) {
    int n = strlen(num_str);
    int num = atoi(num_str);
    int choices = 0;  // 记录不同的选择方案数量
    char substring[20];  // 假设数字最大长度为20

    // 从左往右遍历，找到第一个递减的位置
    for (int i = 0; i < n - 1; i++) {
        if (num_str[i] > num_str[i + 1]) {
            // 在递减位置及其左侧选择子串
            strncpy(substring, num_str, i + 1);
            substring[i + 1] = '\0';  // 添加字符串结束符
            printf("选择子串: %s\n", substring);
            choices++;
        }
    }

    return choices;
}

int main() {
    char num_str[20];  // 假设数字最大长度为20

    // 输入数字字符串
    printf("请输入数字字符串: ");
    scanf("%s", num_str);

    // 调用函数计算满足条件的不同子串选择方案数量
    int result = count_substring_choices(num_str);

    // 输出结果
    printf("不同的子串选择方案数: %d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>

#define MAX_COLORS 1001

// 结点的定义
struct TreeNode {
    int color;
    struct TreeNode* children[1001];
    int num_children;
};

// 创建一个新的结点
struct TreeNode* createNode(int color) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->color = color;
    node->num_children = 0;
    return node;
}

// DFS遍历并统计子树颜色个数
void dfs(struct TreeNode* root, int color_count[MAX_COLORS], int* balanced_trees) {
    int i;
    color_count[root->color]++;

    // 递归地处理子结点
    for (i = 0; i < root->num_children; i++) {
        dfs(root->children[i], color_count, balanced_trees);
    }

    // 检查当前子树是否是颜色平衡树
    int min_count = color_count[root->color];
    int max_count = color_count[root->color];
    for (i = 0; i < MAX_COLORS; i++) {
        if (color_count[i] > 0) {
            if (color_count[i] < min_count) min_count = color_count[i];
            if (color_count[i] > max_count) max_count = color_count[i];
        }
    }

    if (max_count == min_count) (*balanced_trees)++;
    color_count[root->color]--;
}

int main() {
    int n, i;
    int color_count[MAX_COLORS] = {0}; // 记录每种颜色的个数
    int balanced_trees = 0; // 颜色平衡子树的数量

    // 读取结点个数
    scanf("%d", &n);

    struct TreeNode* nodes[n + 1]; // 结点数组
    // 初始化结点数组
    for (i = 1; i <= n; i++) {
        int color;
        scanf("%d", &color);
        nodes[i] = createNode(color);
    }

    // 构建树
    for (i = 2; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
        nodes[parent]->children[nodes[parent]->num_children++] = nodes[i];
    }

    // DFS遍历树并统计颜色平衡子树的数量
    dfs(nodes[1], color_count, &balanced_trees);

    printf("%d\n", balanced_trees);

    return 0;
}

C++

#include <stdio.h>

// 定义最大瓜的数量和最大重量
#define MAX_N 100
#define MAX_WEIGHT 1000

// 动态规划函数，返回最少需要劈的瓜的数量
int minimumCutting(int weights[], int n, int targetWeight) {
    // 定义动态规划数组
    int dp[MAX_N + 1][MAX_WEIGHT + 1] = {0};

    // 初始化动态规划数组
    dp[0][0] = 1;

    // 填充动态规划数组
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= targetWeight; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] |= dp[i - 1][j - weights[i - 1]];
            }
        }
    }

    // 如果无法得到总重为targetWeight的瓜，返回-1
    if (dp[n][targetWeight] == 0) {
        return -1;
    }

    // 回溯找到最少需要劈的瓜的数量
    int cuts = 0;
    int currentWeight = targetWeight;
    int currentMelon = n;

    while (currentWeight > 0 && currentMelon > 0) {
        if (dp[currentMelon - 1][currentWeight]) {
            currentMelon--;
        } else {
            currentWeight -= weights[currentMelon - 1];
            cuts++;
        }
    }

    return cuts;
}

int main() {
    // 示例用法
    int weights[] = {2, 3, 5, 7};
    int n = sizeof(weights) / sizeof(weights[0]);
    int target = 10;

    int result = minimumCutting(weights, n, target);
    printf("%d\n", result);  // 输出 2

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义无穷大值
#define INF INT_MAX

// 定义设备和连接的结构体
struct Edge {
    int to;
    int weight;
};

// 定义图的结构体
struct Graph {
    int vertices;           // 设备的数量
    struct Edge** adjMatrix; // 邻接矩阵表示的图
};

// 初始化图
struct Graph* initializeGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;

    // 为邻接矩阵分配内存
    graph->adjMatrix = (struct Edge**)malloc(vertices * sizeof(struct Edge*));
    for (int i = 0; i < vertices; ++i) {
        graph->adjMatrix[i] = (struct Edge*)malloc(vertices * sizeof(struct Edge));
    }

    // 初始化邻接矩阵
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < vertices; ++j) {
            graph->adjMatrix[i][j].to = -1; // 表示没有连接
            graph->adjMatrix[i][j].weight = INF; // 初始化为无穷大
        }
    }

    return graph;
}

// 添加无向边到图
void addEdge(struct Graph* graph, int from, int to, int weight) {
    graph->adjMatrix[from][to].to = to;
    graph->adjMatrix[from][to].weight = weight;

    // 由于是无向图，需要添加反向边
    graph->adjMatrix[to][from].to = from;
    graph->adjMatrix[to][from].weight = weight;
}

// Dijkstra算法计算从源节点到所有其他节点的最短路径
void dijkstra(const struct Graph* graph, int source, int* dist) {
    int visited[graph->vertices];

    // 初始化距离数组和访问数组
    for (int i = 0; i < graph->vertices; ++i) {
        dist[i] = INF;
        visited[i] = 0;
    }

    dist[source] = 0; // 源节点到自身的距离为0

    for (int count = 0; count < graph->vertices - 1; ++count) {
        int u = -1;

        // 选择未访问的节点中距离最小的节点
        for (int i = 0; i < graph->vertices; ++i) {
            if (!visited[i] && (u == -1 || dist[i] < dist[u]))
                u = i;
        }

        visited[u] = 1; // 标记节点为已访问

        // 更新未访问节点的距离
        for (int v = 0; v < graph->vertices; ++v) {
            if (!visited[v] && graph->adjMatrix[u][v].to != -1 &&
                dist[u] + graph->adjMatrix[u][v].weight < dist[v]) {
                dist[v] = dist[u] + graph->adjMatrix[u][v].weight;
            }
        }
    }
}

// 计算两个设备之间的通信稳定性
int calculateStability(const int* dist, int destination) {
    if (dist[destination] == INF) {
        return -1; // 如果没有路径，则返回-1
    }

    return dist[destination];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m); // 输入设备数量和连接数量

    struct Graph* graph = initializeGraph(n);

    // 输入物理连接的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(graph, u - 1, v - 1, w); // 设备编号从1开始，转换为0开始的索引
    }

    int q;
    scanf("%d", &q); // 查询数量

    for (int i = 0; i < q; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);

        int* distFromX = (int*)malloc(n * sizeof(int));
        dijkstra(graph, x - 1, distFromX);
        int stability = calculateStability(distFromX, y - 1);

        printf("%d\n", stability);

        free(distFromX);
    }

    // 释放内存
    for (int i = 0; i < n; ++i) {
        free(graph->adjMatrix[i]);
    }
    free(graph->adjMatrix);
    free(graph);

    return 0;
}

C++

#include <stdio.h>

// 计算数组中每个子段的异或和并求和
int main() {
    int n;
    scanf("%d", &n); // 输入数组长度

    int A[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &A[i]); // 输入数组元素
    }

    int result = 0;

    // 计算每个子段的异或和并求和
    for (int i = 0; i < n; ++i) {
        int XOR_sum = 0;
        for (int j = i; j < n; ++j) {
            XOR_sum ^= A[j]; // 计算子段的异或和
            result += XOR_sum; // 将每个子段的异或和累加到结果中
        }
    }

    printf("%d\n", result);

    return 0;
}

C++

#include <stdio.h>

#define N 4
#define M 4

// 检查当前位置是否合法
int is_valid(int board[N][M], int i, int j, int target_color) {
    // 检查是否越界
    if (i < 0 || i >= N || j < 0 || j >= M) {
        return 0;
    }

    // 检查当前位置是否已填充
    if (board[i][j] != -1) {
        return 0;
    }

    // 统计周围黑色方格的数量
    int count_black = 0;
    for (int x = i - 1; x <= i + 1; x++) {
        for (int y = j - 1; y <= j + 1; y++) {
            if (x >= 0 && x < N && y >= 0 && y < M && board[x][y] == 1) {
                count_black++;
            }
        }
    }

    // 检查是否符合数字约束
    return count_black == target_color;
}

// 填充周围的方格
void fill_pixels(int board[N][M], int i, int j, int color) {
    if (i < 0 || i >= N || j < 0 || j >= M || board[i][j] != -1) {
        return;
    }

    board[i][j] = color;

    // 递归填充周围的方格
    fill_pixels(board, i - 1, j, color);
    fill_pixels(board, i + 1, j, color);
    fill_pixels(board, i, j - 1, color);
    fill_pixels(board, i, j + 1, color);
}

// 解决像素放置问题
void solve_puzzle(int board[N][M]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] != -1) {
                // 如果当前方格有数字约束，则进行DFS填充
                if (is_valid(board, i, j, board[i][j])) {
                    fill_pixels(board, i, j, 1);
                } else {
                    fill_pixels(board, i, j, 0);
                }
            }
        }
    }
}

int main() {
    int initial_board[N][M] = {
        {-1,  2, -1, -1},
        {-1, -1,  3, -1},
        { 4, -1,  0, -1},
        {-1, -1, -1, -1}
    };

    // 解决问题
    solve_puzzle(initial_board);

    // 打印填充后的棋盘
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            printf("%d ", initial_board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

C++

#include <stdio.h>

// 函数声明
int min_operations(int n);

int main() {
    // 例如，假设有10个硬币
    int n = 10;

    // 调用函数计算最少需要多少次操作
    int result = min_operations(n);

    // 打印结果
    printf("最少需要 %d 次操作\n", result);

    return 0;
}

// 求最少需要多少次操作使所有硬币朝上
int min_operations(int n) {
    int count = 0;  // 记录操作次数

    // 从第2个硬币开始，依次判断每个位置的硬币朝上还是朝下
    for (int i = 2; i <= n; i++) {
        // 如果当前位置的硬币朝下，则需要翻转
        if (n % i == 0) {
            count++;  // 记录操作次数增加
        }
    }

    return count;
}

C++

四、十三届C/C++程序设计C组试题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 比较函数用于qsort
int compareChars(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

int main() {
    // 原始字符串
    char originalString[] = "WHERETHEREISAWILLTHEREISAWAY";

    // 获取字符串长度
    int length = strlen(originalString);

    // 使用qsort按字母表顺序排序字符串
    qsort(originalString, length, sizeof(char), compareChars);

    // 输出排序后的字符串
    printf("排列之后的字符串：%s\n", originalString);

    return 0;
}

C++

#include <stdio.h>

int isInterestingTime(int year, int month, int day, int hour, int minute) {
    // 将年份、月日、时分拼接成一个数字
    int combinedNumber = year * 1000000 + month * 10000 + day * 100 + hour * 1 + minute * 0.01;

    // 统计数字2和数字0的个数
    int count2 = 0, count0 = 0;
    while (combinedNumber > 0) {
        int digit = combinedNumber % 10;
        if (digit == 2) {
            count2++;
        } else if (digit == 0) {
            count0++;
        }
        combinedNumber /= 10;
    }

    // 检查是否符合条件
    return count2 == 3 && count0 == 1;
}

int main() {
    int count = 0;

    // 遍历年份
    for (int year = 1000; year <= 9999; year++) {
        // 遍历月份
        for (int month = 1; month <= 12; month++) {
            // 遍历日期
            for (int day = 1; day <= 31; day++) {
                // 遍历小时
                for (int hour = 0; hour <= 23; hour++) {
                    // 遍历分钟
                    for (int minute = 0; minute <= 59; minute++) {
                        // 检查是否符合条件
                        if (isInterestingTime(year, month, day, hour, minute)) {
                            count++;
                        }
                    }
                }
            }
        }
    }

    printf("符合条件的时间总数：%d\n", count);

    return 0;
}

C++

#include <stdio.h>

void getPaperSize(const char *paperName, int *width, int *height) {
    // 解析纸张名称
    char sizeChar;
    int foldCount;
    sscanf(paperName, "A%c%d", &sizeChar, &foldCount);

    // 根据A纸张的尺寸计算大小
    *width = 1189;
    *height = 841;
    for (int i = 0; i < foldCount; i++) {
        if (*width > *height) {
            *width /= 2;
        } else {
            *height /= 2;
        }
    }
}

int main() {
    char paperName[10];
    printf("输入纸张名称（例如：A0, A1, A2）: ");
    scanf("%s", paperName);

    int width, height;
    getPaperSize(paperName, &width, &height);

    printf("%s纸张的大小为：%dmm x %dmm\n", paperName, width, height);

    return 0;
}

C++

#include <stdio.h>

long long calculate_sum(int arr[], int n) {
    long long S = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            S += (long long)arr[i] * arr[j];
        }
    }

    return S;
}

int main() {
    // 替换这里的实际整数值和数组大小
    int numbers[] = {a1, a2, /*...*/, an};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    long long result = calculate_sum(numbers, size);

    printf("The sum is: %lld\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>

// 计算数字的数位之和
int digitSum(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

// 比较两个数字，按照问题描述中的规则进行比较
int compare(const void *a, const void *b) {
    int digitSumA = digitSum(*(int *)a);
    int digitSumB = digitSum(*(int *)b);

    if (digitSumA != digitSumB) {
        return digitSumA - digitSumB;
    } else {
        return *(int *)a - *(int *)b;
    }
}

// 找到排序后的第m个元素
int findMthElement(int n, int m) {
    int *numbers = (int *)malloc(n * sizeof(int));

    // 初始化数组
    for (int i = 0; i < n; i++) {
        numbers[i] = i + 1;
    }

    // 使用qsort进行排序，使用自定义的比较函数
    qsort(numbers, n, sizeof(int), compare);

    // 排序后的第m个元素
    int result = numbers[m - 1];

    free(numbers);  // 释放动态分配的内存

    return result;
}

int main() {
    // 替换这里的实际整数值
    int n = 100; // 假设排序范围是1到100
    int m = 10;  // 找排序后的第10个元素

    int result = findMthElement(n, m);

    printf("The %dth element after sorting is: %d\n", m, result);

    return 0;
}

C++

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 100000

int prefixXor[MAX_N + 1];

// 计算前缀异或数组
void computePrefixXor(int arr[], int n) {
    prefixXor[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
    }
}

// 判断是否存在异或等于 x 的两个数
bool hasXorPair(int l, int r, int x) {
    return (prefixXor[r] ^ prefixXor[l - 1]) == x;
}

// 查询阶段
bool query(int arr[], int n, int l, int x) {
    for (int r = 1; r <= n; r++) {
        if (hasXorPair(l, r, x)) {
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int arr[MAX_N];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // 预处理阶段
    computePrefixXor(arr, n);

    // 查询阶段
    for (int i = 0; i < m; i++) {
        int l, x;
        scanf("%d %d", &l, &x);

        if (query(arr, n, l, x)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }

    return 0;
}

C++

#include <stdio.h>
#include <string.h>

#define MAX_LEN 100

// 删除边缘字符的函数
void removeEdgeChars(char s[]) {
    int len = strlen(s);
    int i, j;

    for (i = 0; i < len; i++) {
        // 检查当前字符是否为边缘字符
        if (i - 1 >= 0 && i + 1 < len && s[i] != s[i - 1] && s[i] != s[i + 1]) {
            // 删除当前边缘字符
            for (j = i; j < len - 1; j++) {
                s[j] = s[j + 1];
            }
            s[len - 1] = '\0';
            len--;
            i--; // 回退一步，重新检查当前位置
        }
    }
}

int main() {
    char s[MAX_LEN];
    scanf("%s", s);

    // 进行24次操作
    for (int i = 0; i < 24; i++) {
        removeEdgeChars(s);
    }

    if (strlen(s) == 0) {
        printf("EMPTY\n");
    } else {
        printf("%s\n", s);
    }

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>

// 比较函数用于排序
int compare(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

// 计算查询结果的总和
long long calculateSum(int arr[], int n, int queries[][2], int numQueries) {
    long long sum = 0;

    // 计算原始数组的和
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }

    // 遍历每个查询范围
    for (int i = 0; i < numQueries; i++) {
        int L = queries[i][0];
        int R = queries[i][1];

        // 将查询范围内的元素设置为当前数组中的最大值
        for (int j = L - 1; j < R; j++) {
            sum += (arr[j] - arr[0]);  // 增加差值
        }
    }

    return sum;
}

int main() {
    int n, numQueries;
    scanf("%d %d", &n, &numQueries);

    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // 对数组进行排序
    qsort(arr, n, sizeof(int), compare);

    int queries[numQueries][2];
    for (int i = 0; i < numQueries; i++) {
        scanf("%d %d", &queries[i][0], &queries[i][1]);
    }

    // 计算查询结果的总和
    long long result = calculateSum(arr, n, queries, numQueries);

    printf("%lld\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 技能结构体
typedef struct {
    int A;
    int B;
} Skill;

// 比较函数用于排序技能
int compare_skills(const void *a, const void *b) {
    return ((Skill*)b)->A - ((Skill*)a)->A;
}

// 计算最大攻击力提升
int max_attack_increase(int N, int M, Skill skills[]) {
    // 按攻击力提升排序
    qsort(skills, N, sizeof(Skill), compare_skills);

    int total_attack_increase = 0;
    for (int i = 0; i < N; ++i) {
        int max_upgrades = ceil((double)skills[i].A / skills[i].B);
        int upgrades = fmin(max_upgrades, M);
        total_attack_increase += upgrades * skills[i].A;
        M -= upgrades;
    }

    return total_attack_increase;
}

int main() {
    // 示例输入
    int N = 3;
    int M = 5;
    Skill skills[] = {{10, 2}, {7, 1}, {5, 1}};

    // 计算最大攻击力提升
    int result = max_attack_increase(N, M, skills);

    // 输出结果
    printf("最多可以提高的攻击力: %d\n", result);

    return 0;
}

C++

#include <stdio.h>
#include <stdlib.h>

// 哈希表节点
typedef struct Node {
    int value;
    int count;
    struct Node* next;
} Node;

// 哈希表
typedef struct {
    Node** table;
    int size;
} HashMap;

// 初始化哈希表
HashMap* createHashMap(int size) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->size = size;
    map->table = (Node**)malloc(sizeof(Node*) * size);

    for (int i = 0; i < size; ++i) {
        map->table[i] = NULL;
    }

    return map;
}

// 插入哈希表节点
void insertHashMap(HashMap* map, int value) {
    int index = abs(value) % map->size;

    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->count = 1;
    newNode->next = map->table[index];
    map->table[index] = newNode;
}

// 查询哈希表节点
int queryHashMap(HashMap* map, int value) {
    int index = abs(value) % map->size;
    Node* current = map->table[index];

    while (current != NULL) {
        if (current->value == value) {
            return current->count;
        }
        current = current->next;
    }

    return 0;
}

// 计算区间内出现ki次的数的数量
int countOccurrences(int* prefixSum, int left, int right, HashMap* map, int k) {
    if (left > right) {
        return 0;
    }

    int count = 0;
    if (left == 0) {
        count = queryHashMap(map, prefixSum[right]);
    } else {
        count = queryHashMap(map, prefixSum[right] - prefixSum[left - 1]);
    }

    return count == k ? 1 : 0;
}

int main() {
    int n = 6;
    int A[] = {1, 2, 1, 2, 3, 1};

    // 计算前缀和
    int* prefixSum = (int*)malloc(sizeof(int) * n);
    prefixSum[0] = A[0];
    for (int i = 1; i < n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + A[i];
    }

    // 构建哈希表
    HashMap* map = createHashMap(n);

    // 插入前缀和到哈希表
    for (int i = 0; i < n; ++i) {
        insertHashMap(map, prefixSum[i]);
    }

    // 示例查询
    int queries[][3] = {{0, 2, 2}, {1, 4, 1}, {2, 5, 1}};

    // 处理查询
    for (int i = 0; i < 3; ++i) {
        int left = queries[i][0];
        int right = queries[i][1];
        int k = queries[i][2];

        int result = countOccurrences(prefixSum, left, right, map, k);
        printf("在区间[%d, %d]内出现%d次的数有%d个\n", left, right, k, result);
    }

    // 释放内存
    free(prefixSum);
    free(map->table);
    free(map);

    return 0;
}

C++

五、十三届C/C++程序设计B组试题

六、十三届C/C++程序设计A组试题

七、十二届C/C++程序设计C组试题

八、十二届C/C++程序设计B组试题

九、十二届C/C++程序设计A组试题

十、十一届C/C++程序设计C组试题

版权声明：本文为博主作者：慢了半拍i原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/weixin_56641478/article/details/135726057