模板
bool used[MAX_N];
int perm[MAX_N];
//生成{0，1，2，3，4……n-1}的n！中排列
void permutation1(int pos,int n){
if(pos==n){
//这里编写需要对perm进行的操作
return;
}
//针对perm的第pos个位置，究竟使用0~n-1中的哪一个进行循环
for(int i=0;i<n;i++){
if(!used[i]){
perm[pos]=i;
//i已经被使用了，所以把标志设置为true
used[i]=true;
permutation1(pos+1,n);
//返回后将标志复位；
used[i]=false;
}
}
return;
}
第二种：用STL的函数next_permutation函数
#include <algorithm>
//即使有重复的元素也会生成所有的排列
//next_permutation是按照字典序来生成下一个排序的
int perm2[MAX_N];
void permutation2(int n){
for(int i=0;i<n;i++){
perm2[i]=i;
}
do{
//这里编写需要对perm2进行的操作
}while(next_permutation(perm2,perm2+n));
//所有的排序都生成后，next_permutation会返回false
return;
}
真实感想
这个模板一开始看的时候觉得有点像中大的A题，但看得我一脸懵逼，然后就上网找了模板题
描述
小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。
输入
第一行输入整数N（1<N<10）表示多少组测试数据，每组测试数据第一行两个整数 n m (1<n<9,0<m<=n)
输出
在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例
样例输入
2
3 1
4 2
样例输出
1
2
3
12
13
14
21
23
24
31
32
34
41
42
43
代码如下【方法1】
#include <bits/stdc++.h>
using namespace std;
int n,r;
bool used[100];
int perm[100];
//从1 2……中选r个数
void permutation(int pos,int r){
if(pos==r){
for(int i=0;i<r;i++)
cout<<perm[i];
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(!used[i]){
used[i]=true;
perm[pos]=i;
permutation(pos+1,r);
used[i]=false;
}
}
}
int main(){
int cas;
cin>>cas;
while(cas--){
cin>>n>>r;
permutation(0,r);
}
return 0;
}
【方法2】
#include <bits/stdc++.h>
using namespace std;
int n,r;
bool used[100];
int perm[100];
//从1 2……中选r个数
void permutation(int n){
for(int i=1;i<=n;i++){
perm[i]=i;
}
do{
for(int i=1;i<=r;i++)
cout<<perm[i];
//cout<<endl;
}while(next_permutation(perm+1,perm+n+1));
//在这里perm会重新排序，不建议用此种方法，会重复
return;
}
int main(){
int cas;
cin>>cas;
while(cas--){
cin>>n>>r;
permutation(n);
}
return 0;
}
Min-Max
搞了几天的题目终于想清楚了，看了permutation按照自己的逻辑打了一下，不确定对不对，毕竟没有按题解来
期望其实就是每次排列得出的结果之和，因为期望=b[m]/n!，结果是所有b[m]之和/n!*n!,结果就是所有b[m]之和啦
代码如下
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
int n,r;
char m1[1001][3];
char f1[1001],f2[1001];
int num1[1001],num2[1001];
int a[1001],b[1001];
int permutation(int n){
int sum=0;
for(int i=1;i<=n;i++){
a[i]=i;
}
do{
if(strcmp("max",m1[0])==0){
b[1]=max(a[num1[1]],a[num2[1]]);
}
else
b[1]=min(a[num1[1]],a[num2[1]]);
for(int i=2;i<=r;i++){
if(strcmp("max",m1[i])==0){
if(f1[i]=='a'&&f2[i]=='a')
b[i]=max(a[num1[i]],a[num2[i]]);
else if(f1[i]=='a'&&f2[i]=='b')
b[i]=max(a[num1[i]],b[num2[i]]);
else if(f1[i]=='b'&&f2[i]=='a')
b[i]=max(b[num1[i]],a[num2[i]]);
else if(f1[i]=='b'&&f2[i]=='b')
b[i]=max(b[num1[i]],b[num2[i]]);
}
else{
if(f1[i]=='a'&&f2[i]=='a')
b[i]=min(a[num1[i]],a[num2[i]]);
else if(f1[i]=='a'&&f2[i]=='b')
b[i]=min(a[num1[i]],b[num2[i]]);
else if(f1[i]=='b'&&f2[i]=='a')
b[i]=max(b[num1[i]],a[num2[i]]);
else if(f1[i]=='b'&&f2[i]=='b')
b[i]=max(b[num1[i]],b[num2[i]]);
}
sum+=b[r];
}
}while(next_permutation(a+1,a+n+1));
return sum;
}
int main(){
int n;
// freopen("data","r",stdin);
cin>>n>>r;
for(int i=1;i<=r;i++){
scanf("%s %c %d %c %d",m1[i],&f1[i],&num1[i],&f2[i],&num2[i]);
}
int sum=permutation(n);
cout<<sum;
return 0;
}
网友评论