题目大意：一些相同的01串被打碎成两半，现在给出这些打碎了之后的串，要求求出原串。
首先，原串的长度一定是打碎了之后的串中最长的长度加上最短的长度。设打碎之后的串中最长串组成集合S，最短串组成集合T，那么原串肯定为ST或TS中的某种。由于S、T中元素个数必定小于等于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 阅读(1019)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构 、
题目分类：排序