hiho problemset 1014 问题测试出错求助

0
0

大家好，我在hihocoder做problemset中1014 Tire树的题目时，我的代码对于题目中给的测试数据和我自己尝试构造的一些数据测试都能输出正确结果，但提交未能通过，"Wrong Answer"。 这种情况下，接下来调试不知如何调试了。希望大家能帮助看下，指出下现思维漏洞，谢谢。 附代码：

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <locale>

using namespace std;

struct Node {
    wchar_t value; 
    int branch_count;
    vector<Node *> childs;
};

void addWordIntoTree(Node & tree, wstring & word, int index){
    bool isExist = false;
    if (index >= word.size())
        return;
    if (tree.childs.size() > 0){
        for (vector<Node *>::iterator it = tree.childs.begin(); it != tree.childs.end(); ++it){
            Node * branch = *it;
            if (branch->value == word[index]){
                isExist = true;
                branch->branch_count++;
                addWordIntoTree(*branch, word, index+1);
                break;
            }   
        }
    }
    if (!isExist){
        //if no existing braches match the word, create new branch
        Node * parent = &tree;
        for (int i = index; i < word.size(); ++i){
            Node * child = new Node();
            child->value = word[i];
            child->branch_count = 1;
            parent->childs.push_back(child);
            parent = child;
        }

    }
}

int queryPrefixWordCount(Node & tree, wstring & prefix, int index){
    if (index < prefix.size()){
        for (vector<Node *>::iterator it = tree.childs.begin(); it != tree.childs.end(); ++it){
            Node * branch = *it;
            if (branch->value == prefix[index]){
                return queryPrefixWordCount(*branch, prefix, index+1);
            }
        }
        return 0;//not match
    }
    else{
        //all prefix match
        return tree.branch_count;
    }
}

int main(void) {
    int N, M;
    Node tree;
    ios_base::sync_with_stdio(false);
        wcin.imbue(locale("en_US.UTF-8"));
        wcout.imbue(locale("en_US.UTF-8"));


    cin >> N;
    for(int i = 0; i < N; ++i){
        wstring word;
        //wcin >> word;
        getline(wcin, word);
        addWordIntoTree(tree, word, 0);
    }

    cin >> M;
    for(int i = 0; i< M; ++i){
        wstring prefix;
        //wcin >> prefix;
        getline(wcin, prefix);
        cout << queryPrefixWordCount(tree, prefix, 0)<<endl;
    }

    return 0;
}

2 answer(s)

0

我觉得还是IO的问题。自己测试的话最好写一个输入文件data.txt，然后用 < data.txt重定向进行测试。
我不太了解wcin，不清楚wcin和cin混用会不会有些什么诡异问题。我把你的程序都改成了cin，是能AC的。（注意cin>>N 和 cin>>M 之后需要getline()一次吃掉后面的换行符）

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <locale>

using namespace std;

struct Node {
    char value; 
    int branch_count;
    vector<Node *> childs;
};

void addWordIntoTree(Node & tree, string & word, int index){
    bool isExist = false;
    if (index >= word.size())
        return;
    if (tree.childs.size() > 0){
        for (vector<Node *>::iterator it = tree.childs.begin(); it != tree.childs.end(); ++it){
            Node * branch = *it;
            if (branch->value == word[index]){
                isExist = true;
                branch->branch_count++;
                addWordIntoTree(*branch, word, index+1);
                break;
            }   
        }
    }
    if (!isExist){
        //if no existing braches match the word, create new branch
        Node * parent = &tree;
        for (int i = index; i < word.size(); ++i){
            Node * child = new Node();
            child->value = word[i];
            child->branch_count = 1;
            parent->childs.push_back(child);
            parent = child;
        }

    }
}

int queryPrefixWordCount(Node & tree, string & prefix, int index){
    if (index < prefix.size()){
        for (vector<Node *>::iterator it = tree.childs.begin(); it != tree.childs.end(); ++it){
            Node * branch = *it;
            if (branch->value == prefix[index]){
                return queryPrefixWordCount(*branch, prefix, index+1);
            }
        }
        return 0;//not match
    }
    else{
        //all prefix match
        return tree.branch_count;
    }
}

int main(void) {
    int N, M;
    Node tree;
//    ios_base::sync_with_stdio(false);
//        wcin.imbue(locale("en_US.UTF-8"));
//        wcout.imbue(locale("en_US.UTF-8"));


    string tmp;
    cin >> N; getline(cin, tmp);
    for(int i = 0; i < N; ++i){
        string word;
        //wcin >> word;
        getline(cin, word);
        addWordIntoTree(tree, word, 0);
    }

    cin >> M; getline(cin, tmp);
    for(int i = 0; i< M; ++i){
        string prefix;
        //wcin >> prefix;
        getline(cin, prefix);
        cout << queryPrefixWordCount(tree, prefix, 0)<<endl;
    }

    return 0;
}

  • 谢谢！ 我当时使用wcin，主要考虑是题目中提到“（不保证是英文单词，也有可能是火星文单词哦）”。

  • 添加评论
  • ✖reply
0

我自己的操作系统是：Ubuntu 16.04.1 LTS, g++ version 5.4.0 20160609

write answer 切换为英文 切换为中文

转发分享

▲