3

我在 CodinGame.com 上解决了这个问题，我设法编写了一个代码，通过了最后一个测试用例（一个非常大的测试用例）的系统测试。但是在我的笔记本电脑上编译时，我得到的输出是 0 而不是 57330892800，这是代码从他们的机器上给我的。我使用 Visual Studio 2012 Express 和 Dev C++ 4.9.9.2 编译。

我使用了递归函数，所以如果堆栈内存用完，我预计会出现堆栈溢出错误，但没有错误，什么都没有，只是输出 0。为什么在我的系统上发生这种情况而它工作得很好网站的机器？是什么原因造成的，因为我怀疑它是堆栈溢出？

#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<vector>

using namespace std;
typedef long long LONG;


string X[]={".-","-...","-.-.","-..",
            ".","..-.","--.","....",
            "..",".---","-.-",".-..",
            "--","-.","---",".--.",
            "--.-",".-.","...","-",
            "..-","...-",".--","-..-",
            "-.--","--.."};
map<string, int> dict;

string morse(const string ret){
        string s;
        for(char c : ret) s+=X[c-'A'];
        return s;
}

LONG decode(int start, string &word, vector<LONG> &mem){
        if(start == word.size()) return 1;
        else if(mem[start] != -1) return mem[start];

        LONG res = 0;
        string s;
        for(int i=0; i<19*4 && start+i<word.size(); i++){
                s+=word[start+i];
                auto curr = dict.find(s);
                if(curr!=dict.end()) res+=curr->second*decode(start+i+1, word, mem);
        }
        mem[start]=res;
        return res;
}

int main(){
        string word;
        cin>>word;
        int n; cin>>n;
        for(int i=0; i<n; i++){
                string s;
                cin>>s;
                dict[morse(s)]++;
        }
        vector<LONG> mem(word.size(), -1);
        cout<<decode(0, word, mem)<<endl;
}
4

2 回答 2

7

我认为我已经设法将您的代码精简为一个最小的程序：

#include<iostream>
#include<string>

using namespace std;

int main(){
        string word;
        cin>>word; // or getline(cin, word);
        cout << word.size() << endl;
}

测试用例输入文件的结果：

  • 在 Codingame（带有test=4）上，它会打印9884（如预期的那样）。
  • prog在我的个人计算机上，从终端命令行（控制台） 将源文件编译为名为“”的二进制文件后：
    1. 如果我运行./prog然后将文件中的文本复制粘贴到控制台中，它会打印4095（错误）。
    2. 如果我./prog < Test_4_input.txt改为运行，那么它会打印9884（好）。

我假设你做了相当于 1.（从你的 IDE 启动程序并将文本粘贴到它的“控制台”选项卡中）而 Codingame“工作方式类似于”2.因此你得到了这里描述的问题：Linux 终端输入：阅读来自终端的用户输入在 4095 个字符限制处截断行（读取缓冲区的大小限制似乎为 4096 个字节（并将最后一个用于换行符，因此在 4095 处截断））。

编辑：至于我是如何发现的：

和你一样，我开始在 IDE (Eclipse) 中运行程序并将文件内容复制粘贴到嵌入式输入控制台中，结果我也得到0了。所以我开始调整代码并在 IDE 中调试它。

我首先添加了一个全局计数器（初始化为 0），该计数器在 的第一行递增decode并在 的末尾打印main，以查看该函数被调用了多少次。它的最终值1254在 Codingame 上，但只541在我的 IDE 中。
所以我在增量之后设置了一个条件断点decode（条件：计数器 == 541），启动调试器并单步执行代码，并看到循环提前终止。然后我观察了局部变量，我注意到word有一个size. 4095我觉得它很“有趣”，因为它是 4096 减 1 并且4096是 2 的幂；你知道，就像你看到的一样255。
所以我打开了一个文本编辑器，只复制粘贴了输入文件的第一行，发现它的长度不是 4095 而是 9884。现在我开始感觉到这个问题了。因此，我将代码剥离到上面显示的最小测试用例，然后切换到命令行终端进行检查（看到 Codingame 使用 显示 Bash 测试脚本solution < in$test.txt），并在网上搜索了一下以找到对类似问题的一些参考（如上面的链接问题）。“谜题解开了。”

希望这将帮助您自己解决未来的问题:)

于 2013-09-05T11:16:56.110 回答
0

我认为在您的情况下， start ==0 和 mem[start] == 0 因此 decode 在第一次被调用时返回 0 。

将以下两行放在 decode 函数的开头以检查是否是这种情况：

cout << start;
if(mem[start] != -1) return mem[start];
于 2013-09-04T22:28:40.850 回答