題目大意：一些相同的01串被打碎成兩半，現(xiàn)在給出這些打碎了之后的串，要求求出原串。
首先，原串的長度一定是打碎了之后的串中最長的長度加上最短的長度。設打碎之后的串中最長串組成集合S，最短串組成集合T，那么原串肯定為ST或TS中的某種。由于S、T中元素個數(shù)必定小于等于2，所以可能的結果最多只有8種。枚舉這8種結果，然后檢測是否符合要求即可。
檢測的時候，對于某個長度為L的串，要快速檢索到長度為（maxlength+minlength-L）的串，使用multimap<int,string>可以很方便地做到。
以下是我的代碼：
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<cstdio>
using namespace std;
bool cmp(const string &a,const string &b)
{
return (a.size()<b.size() ||(a.size()==b.size() && a<b));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T;
cin>>T;
cin.get();
cin.get();
bool first(true);
while(T--)
{
int minl(0x7f7f7f7f),maxl(0);
vector<string> a;
string t;
while(getline(cin,t) && !t.empty())
{
a.push_back(t);
minl=min(minl,(int)(t.size()));
maxl=max(maxl,(int)(t.size()));
}
sort(a.begin(),a.end(),cmp);
a.erase(unique(a.begin(),a.end()),a.end());
multimap<int,string> r;
for(int i=0;i<a.size();i++)
r.insert(make_pair(a[i].size(),a[i]));
string ans;
multimap<int,string>::iterator
ibegin=r.begin(),
iend=r.upper_bound(minl),
jend=r.end(),
jbegin=r.lower_bound(maxl);
for(multimap<int,string>::iterator i=ibegin;i!=iend;i++)
for(multimap<int,string>::iterator j=jbegin;j!=jend;j++)
{
string now(i->second+j->second);
bool success(true);
for(multimap<int,string>::iterator k=r.begin();k!=r.end();k++)
{
multimap<int,string>::iterator
pbegin=r.lower_bound(minl+maxl-k->first),
pend=r.upper_bound(minl+maxl-k->first);
bool can(false);
for(multimap<int,string>::iterator l=pbegin;l!=pend;l++)
{
if(k->second+l->second==now || l->second+k->second==now)
can=true;
}
if(!can)
{
success=false;
break;
}
}
if(success)
ans=now;
now=j->second+i->second;
success=true;
for(multimap<int,string>::iterator k=r.begin();k!=r.end();k++)
{
multimap<int,string>::iterator
pbegin=r.lower_bound(minl+maxl-k->first),
pend=r.upper_bound(minl+maxl-k->first);
bool can(false);
for(multimap<int,string>::iterator l=pbegin;l!=pend;l++)
{
if(k->second+l->second==now || l->second+k->second==now)
can=true;
}
if(!can)
{
success=false;
break;
}
}
if(success)
ans=now;
}
if(first)
first=false;
else
cout<<endl;
cout<<ans<<endl;
}
return 0;
}
posted on 2011-05-20 15:44
lee1r 閱讀(1052)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結構 、
題目分類：排序