竞争性编程-代码在线编译器提供不同的答案

我试图在codeforces上解决问题811C.我开始编写sublime-text编码,并设法在一段时间后提出解决方案.当我运行该程序时,它给了我正确的答案但是当我提交代码时,出于某种原因我得到了代码强制的不同答案.我检查了数组是否超出范围,但这似乎不是原因.这是代码:

/* Code Readability Credit : Max Vollmer */
#include 
#include 
#include 
#include 
#include 

// terms[] stores the value of all the terms. leftMosts[i] and rightMosts[i] store the leftmost and rightmost occurrences of the ith element in terms[]. 
//solvedValues[] stands for dynamic programming and stores the pre calculated terms of the function solve()
int numberOfTerms;
int terms[5005];
int leftMosts[5005];
int rightMosts[5005];
int solvedValues[5005];

int comf(int left,int right)// comf = comfort (see problem statement if you do not understand this)
{ 
    std::set track;
    int ret = 0;
    for(int i = left; i <= right; i++)
    {
        if (!track.count(terms[i]))
        {
            ret = (ret^terms[i]);
            track.insert(terms[i]);
        }
    }
    return ret;
}

// below, solve stands for 'solve', it is terms recursive memoized function
// returns max sequence from i to (numberOfTerms-1). to find max, call solve(0, -1) so i=0,lefmost=-1. leftmost keeps track of the position of last index of last chosen set.
int solve(int i, int leftmost)
{
    if (i >= numberOfTerms)
    {
        return 0;
    }

    if (solvedValues[i] != -1)
    {
        return solvedValues[i];
    }

    if (leftMosts[i] <= leftmost)
    {
        return solve(i+1, leftmost);// we cant go choose leftMosts[i] to rightMosts[i] so we move on
    }

    // decide if it is better to choose current leftMosts[i] to rightMosts[i] or better to simply move on and skip this.
    return solvedValues[i] = std::max(comf(leftMosts[i], rightMosts[i]) + solve(rightMosts[i]+1, rightMosts[i]), solve(i+1, leftmost));
}

void init()
{
    scanf("%d", &numberOfTerms);
    for(int i = 0; i  i; rightIndex--)
        {
            if (terms[rightIndex] == terms[i])
            {
                rightMosts[i] = rightIndex;
                break;
            }
        }

        if (leftMosts[i] == -1)
        {
            leftMosts[i] = i;// if there is no leftmost occ, then leftmost is current
        }

        if (rightMosts[i] == -1)
        {
            rightMosts[i] = i;// same as above for rightmost
        }
    }

    printf("%d\n", solve(0, -1));

    return 0;
}

这是测试用例:

100 931 4584 2116 3004 3813 62 2819 2998 2080 4906 3198 2443 2952 3793 1958 3864 3985 3169 3134 4011 4525 995 4163 308 4362 1148 4906 3092 1647 244 1370 1424 2753 84 2997 1197 2606 425 3501 2606 683 4747 3884 4787 2166 3017 3080 4303 3352 1667 2636 3994 757 2388 870 1788 988 1303 0 1230 1455 4213 2113 2908 871 1997 3878 4604 1575 3385 236 847 2524 3937 1803 2678 4619 1125 3108 1456 3017 1532 3845 3293 2355 2230 4282 2586 2892 4506 3132 4570 1872 2339 2166 3467 3080 2693 1925 2308

正确的输出应该是:

227685

Codeforces的错误输出:

245849

再次,在我的机器上,代码工作正常并输出227685但是当它在线运行时,代码输出245849由于某种原因.代码可以在这里在线测试. 这是在本地计算机上运行的代码的图像.

我很想知道造成这种情况的原因.

更新: 此错误是由于最终计算值设置为时未考虑leftmost函数中的变量引起的.这是对问题的错误/不正确的方法,并导致诸如影响代码输出的顺序之类的问题.solve(int i,int leftmost)solvedValues[i]std::max()

结果不同的原因

您使用的参数std::max在线和本地计算机上以不同的顺序执行.当comf(leftMosts[i], rightMosts[i]) + solve(rightMosts[i]+1, rightMosts[i])被执行之前solve(i+1, leftmost),你得到想要的结果.如果交换订单,则会得到错误的结果.

有效的重构代码

这是我重构的代码,以提高可读性.我所做的一件事就是打破长期的回报slv.如果切换线的顺序int a =...和int b =...你会得到错误的结果:

#include 
#include 
#include 
#include 
#include 

// terms[] stores the value of all the terms. leftMosts[i] and rightMosts[i] store the leftmost and rightmost occurrences of the ith element in terms[]. 
//solvedValues[] stands for dynamic programming and stores the pre calculated terms of the function solve()
int numberOfTerms;
int terms[5005];
int leftMosts[5005];
int rightMosts[5005];
int solvedValues[5005];

int comf(int left,int right)
{ 
    std::set track;
    int ret = 0;
    for(int i = left; i <= right; i++)
    {
        if (!track.count(terms[i]))
        {
            ret = (ret^terms[i]);
            track.insert(terms[i]);
        }
    }
    return ret;
}

// below, solve stands for 'solve', it is terms recursive memoized function
// returns max sequence from i to (numberOfTerms-1). to find max, call solve(0, -1) so i=0,lefmost=-1. leftmost keeps track of the position of last index of last chosen set.
int solve(int i, int leftmost)
{
    if (i >= numberOfTerms)
    {
        return 0;
    }

    if (solvedValues[i] != -1)
    {
        return solvedValues[i];
    }

    if (leftMosts[i] <= leftmost)
    {
        return solve(i+1, leftmost);// we cant go choose leftMosts[i] to rightMosts[i] so we move on
    }

    // decide if it is better to choose current leftMosts[i] to rightMosts[i] or better to simply move on and skip this.
    int a = comf(leftMosts[i], rightMosts[i]) + solve(rightMosts[i]+1, rightMosts[i]);
    int b = solve(i+1, leftmost);
    return solvedValues[i] = std::max(a, b);
}

void init()
{
    scanf("%d", &numberOfTerms);
    for(int i = 0; i  i; rightIndex--)
        {
            if (terms[rightIndex] == terms[i])
            {
                rightMosts[i] = rightIndex;
                break;
            }
        }

        if (leftMosts[i] == -1)
        {
            leftMosts[i] = i;// if there is no leftmost occ, then leftmost is current
        }

        if (rightMosts[i] == -1)
        {
            rightMosts[i] = i;// same as above for rightmost
        }
    }

    printf("%d numberOfTerms", solve(0, -1));

    return 0;
}

我们从中学到了什么？

可读,干净的代码不仅对你的程序员(和你自己)很好,它还可以降低bug的风险.