做盗版电影网站问题/网络营销论文5000字

题目描述
设R={r1，r2，……，rn}是要进行排列的n个元素。其中元素r1，r2，……，rn可能相同。使设计一个算法，列出R的所有不同排列。
给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。
输入
第1行：元素个数n（1<=n<500）
第2行：一行字符串，待排列的n个元素,都是小写字母
输出
计算出的n个元素的所有不同排列（按字典序），最后一行是排列总数。
样例输入

4
aacc

样例输出

aacc
acac
acca
caac
caca
ccaa
6

一、使用STL-set的暴力做法（TLE AC 45%）

#include<bits/stdc++.h>
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;int n;
string input;
int data[1000],vst[1000];
string ans;
set <string> s;
void dfs(int p,int step){ans[step]=input[p];if(step==n-1){s.insert(ans);return;}FOR(i,0,n-1){if(vst[i]<vst[p]){vst[i]++;dfs(i,step+1);vst[i]--;}}
}int main(){cin>>n>>input;ans=input;FOR(i,0,n-1){mem(vst);vst[i]=1;dfs(i,0);}set<string>::iterator it;string t;for(it=s.begin();it!=s.end();it++){printf("%s\n",(*it).c_str());}cout<<s.size()<<endl;return 0;
}

二、使用STL-vector的暴力做法（MLE AC 18%）

#include<bits/stdc++.h>
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;int n;
string input;
int data[1000],vst[1000];
string ans;
vector<string> v;
int pv=0;
void dfs(int p,int step){ans[step]=input[p];if(step==n-1){v.push_back(ans);return;}FOR(i,0,n-1){if(vst[i]<vst[p]){vst[i]++;dfs(i,step+1);vst[i]--;}}
}int main(){cin>>n>>input;ans=input;FOR(i,0,n-1){mem(vst);vst[i]=1;dfs(i,0);}sort(v.begin(),v.end());pv=unique(v.begin(),v.end())-v.begin();FOR(i,0,pv-1){printf("%s\n",v[i].c_str());}cout<<pv<<endl;return 0;
}

三、不使用STL容器的正确做法（AC 100%）

#include<bits/stdc++.h>
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;int n,sum,cnt[1000]={};
string data;
char ans[1000];void dfs(int step){FOR(i,0,25){if(cnt[i]>0){ans[step]=char(i+'a');if(step==n-1){sum++;printf("%s\n",ans);}else{cnt[i]--;dfs(step+1);cnt[i]++;}}}
}int main(){cin>>n>>data;FOR(i,0,n-1){cnt[data[i]-'a']++;}dfs(0);cout<<sum<<endl;return 0;
}