c++ - 竞争性编程 - 代码在在线编译器上给出不同的答案

Question

我试图解决 problem 811C on codeforces 。我开始在 sublime-text 上编码，并在一段时间后设法想出了一个解决方案。当我运行程序时，它给了我正确的答案，但是当我提交代码时，出于某种原因，我在 codeforces 上得到了不同的答案。我检查了数组是否越界，但这似乎不是原因。这是代码:

/* Code Readability Credit : Max Vollmer */
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <set>

// 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<int> 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 < numberOfTerms; i++)
    {
        scanf("%d", &terms[i]);
    }
    // init all as -1
    memset(solvedValues, -1, sizeof(solvedValues));
    memset(leftMosts, -1, sizeof(leftMosts));
    memset(rightMosts, -1, sizeof(rightMosts));
}

int main()
{
    init();

    // calc leftMosts[i] and rightMosts[i] for all 'i in terms
    for (int i = 0; i < numberOfTerms; i++)
    {
        for (int leftIndex = 0; leftIndex < i; leftIndex++)
        {
            if (terms[leftIndex] == terms[i])
            {
                leftMosts[i] = leftIndex;
                break;
            }
        }

        for (int rightIndex = numberOfTerms-1; rightIndex > 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。代码可以是tested online here.这是一个 image of the code working on a local machine.

我很想知道是什么原因造成的。

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

Answer 1

不同结果的原因

您在 std::max 中使用的参数在线和本地机器上以不同的顺序执行。当 comf(leftMosts[i], rightMosts[i]) + solve(rightMosts[i]+1, rightMosts[i]) 在 solve(i+1, leftmost)，你得到了想要的结果。如果调换顺序，您会得到错误的结果。

有效的重构代码

这是我为提高可读性而重构的代码。我所做的其中一件事是分解 slv 中的长返回语句。如果您调换 int a =... 和 int b =... 行的顺序，您将得到错误的结果:

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <set>

// 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<int> 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 < numberOfTerms; i++)
    {
        scanf("%d", &terms[i]);
    }
    // init all as -1
    memset(solvedValues, -1, sizeof(solvedValues));
    memset(leftMosts, -1, sizeof(leftMosts));
    memset(rightMosts, -1, sizeof(rightMosts));
}

int main()
{
    init();

    // calc leftMosts[i] and rightMosts[i] for all 'i in terms
    for (int i = 0; i < numberOfTerms; i++)
    {
        for (int leftIndex = 0; leftIndex < i; leftIndex++)
        {
            if (terms[leftIndex] == terms[i])
            {
                leftMosts[i] = leftIndex;
                break;
            }
        }

        for (int rightIndex = numberOfTerms-1; rightIndex > 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;
}

我们从中学到了什么？

可读、干净的代码不仅对您的程序员同事(和您自己)有好处，而且还能降低出现错误的风险。