hiho problemset 1039 问题测试出错咨询

0
0

　　我在hihocoder做problemset中1039字符消除的题目时，我的代码对于题目中给的测试数据和我自己尝试构造的一些数据测试都能输出正确结果，但提交未能通过，"Wrong Answer"。 　　目前情况，调试无从下手。不知道是否能拿到该题的测试数据，以便帮助我发现思维漏洞，谢谢。 附代码：

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;


pair<vector<int>, string> eliminateStr(const string & strInput){
        int ret = 0;
        int size = strInput.size();
        vector<int> indexVec(size);
        for (int i=0; i<size;++i){
                indexVec[0] = i;
        }

        bool isChanged=true;
        string strWork(strInput);
        while(isChanged){
                isChanged = false;
                vector<int> indexToRemove;

                if(strWork.size() <= 1){ 
                        break;
                }

                //mark repeated index
                for(int i=1; i<strWork.size(); ++i){
                        if (strWork[i]==strWork[i-1]){
                                if(indexToRemove.empty() || indexToRemove.back()!=(i-1)){
                                        indexToRemove.push_back(i-1);
                                }
                                indexToRemove.push_back(i);
                        }
                }

                //remove repeated index
                for(vector<int>::reverse_iterator rit=indexToRemove.rbegin(); rit !=indexToRemove.rend();++rit){
                        strWork.erase(strWork.begin() + *rit);
                        indexVec.erase(indexVec.begin() + *rit);
            isChanged = true;
                }
        }
        return make_pair(indexVec, strWork);
}


/*
 * Here enumerate all brutely (skip the obviously to-eliminate positions);
 * May check symbol(A,B,C) symmetric characteristicsi alternatively:
 *  1, eliminate without insert one new char;(ABCBCCCAA => ABCB)
 *  2, the position of longest symmetric substr (ABCB => BCB => C's position)
 *  3, end
 */
int calMaxEliminateByInsertOneChar(const string & strInput){
    int size = strInput.size();
    int max = size+1;

    //eliminate the already repeated str
    pair<vector<int>, string> initRet = eliminateStr(strInput);
    if (initRet.first.size() == 0){//special case: the initial string all can be eliminated 
        return max;
    }

    int min = initRet.first.size();
    for (int i=0; i<initRet.first.size(); i++)
    {
        pair<vector<int>, string> itRet;
        string strWork(initRet.second);
        //strWork.insert(i, &initRet.second[i]);
        strWork.insert(i, &initRet.second[i],1);
        itRet = eliminateStr(strWork);
        if (itRet.first.size() < min){
            min = itRet.first.size();
            if (min==0)
                return max;
        }
    }
    return max - min;
}

int main(void) {
    int num;
    cin >> num;
    for (int i=0; i<num; ++i){
        string strLine;
        int ret = 0;
        cin >> strLine; 
        ret = calMaxEliminateByInsertOneChar(strLine);
        cout << ret << endl;
    }
    return 0;
}

6 answer(s)

0

WA是真的感觉没问题··· G++ c++

#include <iostream>
#include <string>

using namespace std;
string del(string str);

int main()
{
int T,max=0;
cin>>T;
while(T--){
max = 0;
string str0,str;
cin>>str0;
int num = 0,stlen = str0.length();
str0.append("#");
for(int k=0;k<stlen;k++){
    str = str0;
    str = str.insert(k,1,str.at(k));
    str = del(str);
    str = str.substr(0,str.length()-1);
    num = stlen - str.length();
    if(num>max) max = num;
}
cout<<max+1<<endl;
}
return 0;
}

string del(string str){
char temp;
bool flag = false,flag1 = false;
for(unsigned i=0,count = 0;i<str.length();i++){
    temp = str.at(i);
    if(temp == '@')continue;
    for(unsigned j=i+1;j<str.length();j++){
        if(temp == str.at(j)){
            flag = true;
            flag1 = true;
            count++;
        }else if(flag&&flag1){
            string st1 = str.substr(0,i);
            string st2 = str.substr(j);
            st1 = st1.append("@");
            str = st1.append(st2);
            flag1 = false;
            i--;
            j=j-count-1;
            count = 0;
        }
        else break;
    }
}
if(flag) {
    int fuck = str.find("@");
    while(fuck != -1){
        string st1 = str .substr(0,fuck);
        string st2 = str.substr(fuck+1);
        str = st1.append(st2);
        fuck = str.find("@");
    }
    str = del(str);
}
return str;
}
0

这是我写的能想到的例子我都试了感觉没问题，但是WA````

include

include

using namespace std; string del(string str);

int main() { int T,max=0; cin>>T; while(T--){ max = 0; string str0,str; cin>>str0; int num = 0,stlen = str0.length(); str0.append("#"); for(int k=0;kmax) max = num; } cout<

string del(string str){ char temp; bool flag = false,flag1 = false; for(unsigned i=0,count = 0;i

0

做法不对吧
为什么最优解不会是在AB中插入C或者在AA中插入B这样的？

  • 因为需要的是最大化消除字符数，所以应该插入对应位置相同的字符。

  • 也许我这样的想法确实有疏漏，我试下遍历所有插入可能。谢谢！

  • 添加评论
  • ✖reply
0 
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;


pair<vector<int>, string> eliminateStr(const string & strInput){
        int ret = 0;
        int size = strInput.size();
        vector<int> indexVec(size);
        for (int i=0; i<size;++i){
                indexVec[i] = i;
        }

        bool isChanged=true;
        string strWork(strInput);
        while(isChanged){
                isChanged = false;
                vector<int> indexToRemove;

                if(strWork.size() <= 1){ 
                        break;
                }

                //mark repeated index
                for(int i=1; i<strWork.size(); ++i){
                        if (strWork[i]==strWork[i-1]){
                                if(indexToRemove.empty() || indexToRemove.back()!=(i-1)){
                                        indexToRemove.push_back(i-1);
                                }
                                indexToRemove.push_back(i);
                        }
                }

                //remove repeated index
                for(vector<int>::reverse_iterator rit=indexToRemove.rbegin(); rit !=indexToRemove.rend();++rit){
                        strWork.erase(strWork.begin() + *rit);
                        indexVec.erase(indexVec.begin() + *rit);
            isChanged = true;
                }
        }
        return make_pair(indexVec, strWork);
}


/*
 * Here enumerate all brutely (skip the obviously to-eliminate positions);
 * May check symbol(A,B,C) symmetric characteristicsi alternatively:
 *  1, eliminate without insert one new char;(ABCBCCCAA => ABCB)
 *  2, the position of longest symmetric substr (ABCB => BCB => C's position)
 *  3, end
 */
int calMaxEliminateByInsertOneCharBrutelyTotally(const string & strInput){
    int size = strInput.size();
    int max = size+1;

    //eliminate the already repeated str
    int min = size;
    for (int i=0; i<size; i++)
    {
        pair<vector<int>, string> itRet;
        string strWork(strInput);
        strWork.insert(i, strInput, i,1);
        itRet = eliminateStr(strWork);
        if (itRet.first.size() < min){
            min = itRet.first.size();
            if (min==0)
                return max;
        }
    }
    return max - min;
}

int calMaxEliminateByInsertOneCharBrutelySelectively(const string & strInput){
    int size = strInput.size();
    int max = size+1;

    //eliminate the already repeated str
    pair<vector<int>, string> initRet = eliminateStr(strInput);
    if (initRet.first.size() == 0){//special case: the initial string all can be eliminated 
        return max;
    }

    int min = initRet.first.size();
    for (int i=0; i<initRet.first.size(); i++)
    {
        pair<vector<int>, string> itRet;
        string strWork(initRet.second);
        strWork.insert(i, &initRet.second[i],1);
        itRet = eliminateStr(strWork);
        if (itRet.first.size() < min){
            min = itRet.first.size();
            if (min==0)
                return max;
        }
    }
    return max - min;
}

int main(void) {
    int num;
    cin >> num;
    for (int i=0; i<num; ++i){
        string strLine;
        int ret = 0;
        cin >> strLine; 
        ret = calMaxEliminateByInsertOneCharBrutelyTotally(strLine);
        cout << ret << endl;
    }
    return 0;
}
0

对于hihocoder的回复，解释下：我在插入字符前就开始消除，是认为字符插入的位置应该不会是在已经能够消除的位置，这样先消除，再在剩下的可能的位置尝试插入，可以提高效率。也许，这样的思维有漏洞，但我后来提交完全尝试的版本，还是"Wrong Answer"（对于题目中给的示例数据和我自己尝试构造的一些数据测试都能输出正确结果）。附代码：

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;


pair<vector<int>, string> eliminateStr(const string & strInput){
        int ret = 0;
        int size = strInput.size();
        vector<int> indexVec(size);
        for (int i=0; i<size;++i){
                indexVec[0] = i;
        }

        bool isChanged=true;
        string strWork(strInput);
        while(isChanged){
                isChanged = false;
                vector<int> indexToRemove;

                if(strWork.size() <= 1){ 
                        break;
                }

                //mark repeated index
                for(int i=1; i<strWork.size(); ++i){
                        if (strWork[i]==strWork[i-1]){
                                if(indexToRemove.empty() || indexToRemove.back()!=(i-1)){
                                        indexToRemove.push_back(i-1);
                                }
                                indexToRemove.push_back(i);
                        }
                }

                //remove repeated index
                for(vector<int>::reverse_iterator rit=indexToRemove.rbegin(); rit !=indexToRemove.rend();++rit){
                        strWork.erase(strWork.begin() + *rit);
                        indexVec.erase(indexVec.begin() + *rit);
            isChanged = true;
                }
        }
        return make_pair(indexVec, strWork);
}


/*
 * Here enumerate all brutely (skip the obviously to-eliminate positions);
 * May check symbol(A,B,C) symmetric characteristicsi alternatively:
 *  1, eliminate without insert one new char;(ABCBCCCAA => ABCB)
 *  2, the position of longest symmetric substr (ABCB => BCB => C's position)
 *  3, end
 */
int calMaxEliminateByInsertOneChar(const string & strInput){
    int size = strInput.size();
    int max = size+1;

    //eliminate the already repeated str
    pair<vector<int>, string> initRet = eliminateStr(strInput);
    if (initRet.first.size() == 0){//special case: the initial string all can be eliminated 
        return max;
    }

    int min = initRet.first.size();
    for (int i=0; i<initRet.first.size(); i++)
    {
        pair<vector<int>, string> itRet;
        string strWork(initRet.second);
        strWork.insert(i, &initRet.second[i]);
        itRet = eliminateStr(strWork);
        if (itRet.first.size() < min){
            min = itRet.first.size();
            if (min==0)
                return max;
        }
    }
    return max - min;
}

int main(void) {
    int num;
    cin >> num;
    for (int i=0; i<num; ++i){
        string strLine;
        int ret = 0;
        cin >> strLine; 
        ret = calMaxEliminateByInsertOneChar(strLine);
        cout << ret << endl;
    }
    return 0;
}

  • 贴错代码了，但回复内容修改更新提示没有权限。更新的代码见下一个回复。

  • 添加评论
  • ✖reply
0

我简单看了一下你的程序，发现了一个问题。你在插入字符前就开始消除是不符合题意的，题目中说“在消除开始前小Hi有机会在s中任意位置插入任意一个字符”。　-hihoCoder

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

转发分享

▲