模板
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進(jìn)行的操作
return;
}
//針對perm的第pos個位置，究竟使用0~n-1中的哪一個進(jìn)行循環(huán)
for(int i=0;i<n;i++){
if(!used[i]){
perm[pos]=i;
//i已經(jīng)被使用了缘琅，所以把標(biāo)志設(shè)置為true
used[i]=true;
permutation1(pos+1,n);
//返回后將標(biāo)志復(fù)位粘都；
used[i]=false;
}
}
return;
}
第二種：用STL的函數(shù)next_permutation函數(shù)
#include <algorithm>
//即使有重復(fù)的元素也會生成所有的排列
//next_permutation是按照字典序來生成下一個排序的
int perm2[MAX_N];
void permutation2(int n){
for(int i=0;i<n;i++){
perm2[i]=i;
}
do{
//這里編寫需要對perm2進(jìn)行的操作
}while(next_permutation(perm2,perm2+n));
//所有的排序都生成后，next_permutation會返回false
return;
}
真實感想
這個模板一開始看的時候覺得有點(diǎn)像中大的A題刷袍，但看得我一臉懵逼翩隧，然后就上網(wǎng)找了模板題
描述
小明十分聰明，而且十分擅長排列計算呻纹。比如給小明一個數(shù)字5堆生，他能立刻給出1-5按字典序的全排列专缠，如果你想為難他，在這5個數(shù)字中選出幾個數(shù)字讓他繼續(xù)全排列淑仆，那么你就錯了涝婉，他同樣的很擅長。現(xiàn)在需要你寫一個程序來驗證擅長排列的小明到底對不對蔗怠。
輸入
第一行輸入整數(shù)N（1<N<10）表示多少組測試數(shù)據(jù)墩弯，每組測試數(shù)據(jù)第一行兩個整數(shù) n m (1<n<9,0<m<=n)
輸出
在1-n中選取m個字符進(jìn)行全排列，按字典序全部輸出,每種排列占一行寞射，每組數(shù)據(jù)間不需分界渔工。如樣例
樣例輸入
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個數(shù)
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個數(shù)
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會重新排序，不建議用此種方法桥温，會重復(fù)
return;
}
int main(){
int cas;
cin>>cas;
while(cas--){
cin>>n>>r;
permutation(n);
}
return 0;
}
Min-Max
搞了幾天的題目終于想清楚了引矩，看了permutation按照自己的邏輯打了一下，不確定對不對侵浸，畢竟沒有按題解來
期望其實就是每次排列得出的結(jié)果之和脓魏，因為期望=b[m]/n!，結(jié)果是所有b[m]之和/n!*n!,結(jié)果就是所有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;
}