Codeforces 1744B代码处理大数输入时输出异常求助

问题描述 #

针对Codeforces Contest 1744B编写的C语言代码，常规测试用例运行正常，但处理包含1000000000这类大数的输入时，输出出现负数等错误值，与预期结果不符。

测试用例 #

常规测试用例1 #

输入：

1
1 1
1
1 1

输出：

2

常规测试用例2 #

输入：

1
3 3
1 2 4
0 2
1 3
0 5

输出：

11
14
29

常规测试用例3 #

输入：

1
6 7
1 3 2 4 10 48
1 6
0 5
0 4
0 5
1 3
0 12
0 1

输出：

80
100
100
100
118
190
196

大数测试用例 #

输入：

1
6 7
1000000000 1000000000 1000000000 11 15 17
0 17
1 10000
1 51
0 92
0 53
1 16
0 1

预期输出：

3000000094
3000060094
3000060400
3000060952
3000061270
3000061366
3000061366

实际输出：

-1294967202
-1294967202
-1294906896
-1294906344
-1294906026
-1294905930
-1294905930

原代码 #

#include<stdio.h>

int odd_even_incre(long long a[], int x, int y,int n)
{
    int i,j;
    long long sum=0;

    if(x%2==0){
        for(i=0; i<n ;i++){
            if(a[i]%2==0){
                a[i]= a[i]+y;
            }
        sum = sum+a[i];
        }
    }
    else{
        for(i=0; i<n ;i++){
            if(a[i]%2!=0){
                a[i]= a[i]+y;
            }
        sum = sum+a[i];
        }
    }
    return sum;
}

int main()
{
    int n,q,t, i,j,x,y;
    long long a[100000],result;

    scanf("%d", &t);

    for(i=0; i<t; i++)
    {
        scanf("%d %d", &n, &q);
        for(j=0 ; j<n ; j++)
        {
            scanf("%lld", &a[j]);
        }
        for (j=0; j<q; j++)
        {
            scanf("%d %d", &x, &y);
            result = odd_even_incre(a,x,y,n);
            printf("%lld\n",  result);
        }
    }

    return 0;
}

问题定位 #

核心错误是函数返回值类型不匹配导致的整数溢出：

• odd_even_incre函数声明的返回类型是int，但函数内部计算的sum是long long类型。
• 当处理大数输入时，sum的值会超过int类型的最大值（2^31-1=2147483647），发生有符号整数溢出，导致返回值被截断为负数（未定义行为的典型表现）。
• 此外，函数内定义的j变量未使用，属于冗余代码。

修复方案 #

1. 将odd_even_incre函数的返回类型从int改为long long，确保返回值能容纳大数总和。
2. 移除未使用的冗余变量j。
3. （可选优化）预先统计数组初始总和、奇数元素数量和偶数元素数量，避免每次操作遍历整个数组求和，将时间复杂度从O(tqn)优化为O(t*(n+q))，提升效率。

基础修复后的代码 #

#include<stdio.h>

// 修改返回类型为long long
long long odd_even_incre(long long a[], int x, int y, int n)
{
    int i;
    long long sum = 0;

    if(x % 2 == 0){
        for(i = 0; i < n ; i++){
            if(a[i] % 2 == 0){
                a[i] += y;
            }
            sum += a[i];
        }
    }
    else{
        for(i = 0; i < n ; i++){
            if(a[i] % 2 != 0){
                a[i] += y;
            }
            sum += a[i];
        }
    }
    return sum;
}

int main()
{
    int n, q, t, i, j, x, y;
    long long a[100000], result;

    scanf("%d", &t);

    for(i = 0; i < t; i++)
    {
        scanf("%d %d", &n, &q);
        for(j = 0 ; j < n ; j++)
        {
            scanf("%lld", &a[j]);
        }
        for (j = 0; j < q; j++)
        {
            scanf("%d %d", &x, &y);
            result = odd_even_incre(a, x, y, n);
            printf("%lld\n", result);
        }
    }

    return 0;
}

优化后的高效代码 #

#include<stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, q;
        scanf("%d %d", &n, &q);
        long long total = 0;
        int count_odd = 0, count_even = 0;
        long long a;
        for(int i = 0; i < n; i++)
        {
            scanf("%lld", &a);
            total += a;
            if(a % 2 == 0)
                count_even++;
            else
                count_odd++;
        }
        while(q--)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            if(x == 0)
            {
                // 给所有偶数加y
                total += (long long)count_even * y;
                // 如果y是奇数，偶数变奇数
                if(y % 2 != 0)
                {
                    count_odd += count_even;
                    count_even = 0;
                }
            }
            else
            {
                // 给所有奇数加y
                total += (long long)count_odd * y;
                // 如果y是奇数，奇数变偶数
                if(y % 2 != 0)
                {
                    count_even += count_odd;
                    count_odd = 0;
                }
            }
            printf("%lld\n", total);
        }
    }
    return 0;
}

验证结果 #

修复后的代码处理大数测试用例时，输出与预期完全一致，无溢出错误。优化后的代码在处理大规模输入时，运行效率显著提升。

内容的提问来源于stack exchange，提问作者Zannatul Ferdousi Hema