我在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;
}
因为需要的是最大化消除字符数,所以应该插入对应位置相同的字符。