EOJ 3023 字符组合

3.30更新

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <set>
 5 using namespace std;
 6 int main()
 7 {
 8     int T;cin>>T;
 9     for(int m=0;m<T;m++)
10     {
11         string s;cin>>s;
12         sort(s.begin(),s.end());
13         s.resize(unique(s.begin(),s.end())-s.begin());
14 
15         int ll=s.size();
16         int sum=~((-1)<<ll)+1;
17 
18         set<string> ans;
19         while(sum-->1)
20         {
21             string tmp;
22             for(int d=1,i=0;i<ll;d=d<<1,i++)
23                 if(sum&d) tmp+=s[i];
24             ans.insert(tmp);
25         }
26         printf("case #%d:
",m);
27         for(string x:ans)cout<<x<<endl;
28 
29 
30     }
31     return 0;
32 }

使用位运算更简便，更新排序unique的操作，并且使用set容器。

3.29更新

 1 #include<bits/stdc++.h>
 2 #define ALL(x) x.begin(),x.end()
 3 using namespace std;
 4 set<string> ans;
 5 string s,ss,ret;
 6 void comb(int n,string s){/*我这个也是递归*/
 7 
 8     for(int i=n;i<ss.size();i++){
 9         ans.insert(s+ss[i]);
10         comb(i+1,s+ss[i]);
11     }
12 }
13 int main()
14 {
15     int T;cin>>T;
16     for(int m=0;m<T;m++){
17         cin>>s;
18         ss=ret=string{};
19         ans.clear();
20         sort(ALL(s));
21         unique_copy(ALL(s),back_inserter(ss));
22         comb(0,ret);
23         printf("case #%d:
",m);
24         for(string x:ans)   cout<< x <<endl;
25     }
26     return 0;
27 }

用递归方式实现，核心代码只需3行！

既然题目说明ab和ba等价，每次只需要从上一个指定位置向后看就好了。比如递归b的时候就不会从a开始了。

一开始用回溯，加加减减的没有必要，既然递归的局部变量在函数退出时消亡，干脆直接传进去好了。

输入一个由字母组成的字符串 S(1≤长度≤16)，按字典序输出由 S 中不同字符组成的所有字符组合（每个组合中的字符也按字典序排列）。

例如：“cbaabc” 中的不同字符是 ‘a’、‘b’、‘c’ 共 3 个，则 1 个字符组成的组合是 “a”、“b”、“c”3 种，2 个字符组成的组合是 “ab”、“bc”、“ac”3 种，3 个字符组成的组合是 “abc”1 种。注意：“ab” 和 “ba” 由相同字符组合而成，因此可认为是同一个组合。那么这个例子共有 7 种组合，按序分别为 “a”、“ab”、“abc”、“ac”、“b”、“bc”、“c”。

 1 #include <iostream>
 2 #include <math.h>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 int main()
 7 {
 8     int T;cin>>T;
 9     for(int m=0;m<T;m++)
10     {
11         int flag[52]={0};char c;
12         vector<char> v;
13         string s;cin>>s;
14         for(char x:s) v.push_back(x);
15         sort(v.begin(),v.end());
16         v.resize(unique(v.begin(),v.end())-v.begin());
17 
18         int ll=v.size();
19         long long sum=0;
20         for(int i=0;i<ll;i++)
21             sum+=pow(2,i);
22         vector<string > ans;
23         for(;sum>=1;sum--)
24         {
25             string tmp;
26             for(int i=ll-1,d=1;i>=0;i--,d<<=1)
27                 if(sum&d) tmp.insert(tmp.begin(),v[i]);
28             ans.push_back(tmp);
29         }
30         sort(ans.begin(),ans.end());
31         printf("case #%d:
",m);
32         for(int i=0;i<ans.size();i++)
33             cout<<ans[i]<<endl;
34 
35 
36     }
37     return 0;
38 }

排序去重后二进制枚举即可。