交错的字符串
(string.cpp)
【问题描述】
Mark Douglas是一名律师。他的客户Yuri Ball在一场车祸中不幸去世。为了帮助Yuri的亲属拿到他的遗产，Mark需要得到一个密码。在Yuri的笔记本上，有一个长为2n的只包含小写字母的字符串，Mark知道密码恰好是将这个字符串分解为两个长度为n的子序列且它们构成的字符串恰好相反的方案数。我们认为两种分解方法是不同的，当且仅当两个下标集合构成的集合{S1, S2}是不同的，注意{S1, S2}和{S2, S1}我们认为是相同的分解方法。如cabaacba的合法分解共有cabaacba和cabaacba两种。Mark希望你能帮助他计算出密码，事成之后他决定分给你six million five hundred thousand dollars并邀请你去柬埔寨度假。
【输入格式】
输入文件名为string.in。
第一行为一个正整数n。
第二行为一个长度为2n的字符串，仅包含小写字母。
【输出格式】
输出文件名为string.out。
输出仅一行表示答案。
【样例输入与输出】
|
example_string1.in |
example_string1.out |
|
4 cabaacba |
2 |
更多样例请见example/string/目录。
【数据范围】
对于1~7号测试点（28%）：n<=10。
对于8~10号测试点（12%）：字符串中仅有小写字母a。
对于11~14号测试点（16%）：字符串中除去两个b外其余全是a。
对于15~18号测试点（16%）：字符串中仅有a, b两种字符。
对于所有测试点（100%）：n<=18。
这个数据范围容易使人想到折半搜索。
我们将字符串分为前后两部分。如果前半部分中搜得的前缀串为{S1, S2}，那么后半部分中搜得的后缀串必须为{rev(S2), rev(S1)}，且为有序对。
对于两侧分别枚举每个字符的归属情况，hash后用map计数即可。
code:
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<algorithm> 5 #include<map> 6 using namespace std; 7 string S,S1,S2; 8 map<string,int>check; 9 long long ans,n; 10 int main(){ 11 cin>>n>>S; 12 int all=(1<<n); 13 for(int i=0;i<all;i++){ 14 S1.clear(); 15 S2.clear(); 16 for(int j=0;j<n;j++){ 17 if((i>>j)&1)S1.push_back(S[j]); 18 else S2.push_back(S[j]); 19 } 20 reverse(S2.begin(),S2.end()); 21 check[S1+'^'+S2]++; 22 } 23 for(int i=0;i<all;i++){ 24 S1.clear(); 25 S2.clear(); 26 for(int j=0;j<n;j++){ 27 if((i>>j)&1)S1.push_back(S[j+n]); 28 else S2.push_back(S[j+n]); 29 } 30 reverse(S1.begin(),S1.end()); 31 ans+=check[S1+'^'+S2]; 32 } 33 cout<<ans/2; 34 return 0; 35 }
over