題目沒有給出具體的規模，因此沒有用枚舉。我的做法是維護一棵Trie，把01串按長度從大到小的次序插入，這樣就可以在插入時判斷是否為之前某個長度更大串的前綴。盡管如此，依然用了0.408s的時間，可能與用cin/cout輸入輸出有關。
以下是我的代碼：
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
const int kMaxn(10007);
bool cmp(const string &sa,const string &sb)
{
return (sa.size()>sb.size() || (sa.size()==sb.size() && sa<sb));
}
struct TreeNode
{
TreeNode():left_(NULL),right_(NULL) {}
TreeNode *left_,*right_;
};
class Trie
{
public:
Trie()
{
father_=new TreeNode;
}
bool Insert(const string &s)
{
bool re(false);
TreeNode *p(father_);
for(int i=0;i<s.size();i++)
{
if(s[i]=='0' && !p->left_)
{
p->left_=new TreeNode;
if(i==s.size()-1)
re=true;
}
else if(s[i]=='1' && !p->right_)
{
p->right_=new TreeNode;
if(i==s.size()-1)
re=true;
}
if(s[i]=='0')
p=p->left_;
else
p=p->right_;
}
return re;
}
private:
TreeNode *father_;
};
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T(0);
string t;
while(cin>>t)
{
vector<string> r;
while(t!="9")
{
r.push_back(t);
cin>>t;
}
sort(r.begin(),r.end(),cmp);
Trie trie;
bool success(true);
for(vector<string>::iterator i=r.begin();i!=r.end();i++)
if(!trie.Insert(*i))
{
success=false;
break;
}
T++;
if(success)
cout<<"Set "<<T<<" is immediately decodable"<<endl;
else cout<<"Set "<<T<<" is not immediately decodable"<<endl;
}
return 0;
}
posted on 2011-04-07 20:07
lee1r 閱讀(457)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：字符串處理 、
題目分類：數據結構