题意：
给出一个十进制数，数位两两可以交换，给出最多能交换多少次，以及交换后的数不能有前缀0，问能形成最小和最大的数
尝试的思路
- 贪心，将字符串先排出最大以及最小的情况，然后按一定顺序将对应位置换过去，不知道为什么wa
- 枚举全排列，将验证能否在规定步数能换过去，假如可以则更新最小最大值，
不会判断能否换过去，计算循环节，循环节内的交换次数为（循环节长度-1）
- 通过观察发现，一个长为n的串，假如最多能交换n-1次，它就能变成任何的串，那么就缩小了k的范围。然后解决枚举的问题，想了一个办法，枚举每一位，每一位只和后面的交换， 这样能大大地减少重复次数
枚举全排列写法
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
const int maxn = 1e5+10;
const int mod=1<<30;
#define inf 0x3f3f3f3f
int c[maxn];
char s[20];
int n;
bool vis[20];
int k;
bool check()
{
memset(vis,0,sizeof(vis));
int tmp=0;
for(int i=0;i<n;i++)
{
if(vis[i]) continue;
int x=0;
while(vis[i]==0)
{
x++;
vis[i]=1;
i=c[i];
}
tmp+=x-1;
if(tmp>k) return 0;
}
return tmp<=k;
}
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T;
cin>>T;
while(T--)
{
scanf("%s%d",s,&k);
int Min=1e9+7;
int Max=0;
n=strlen(s);
for(int i=0;i<n;i++)
{
c[i]=i;
}
do
{
if(s[c[0]]!='0'&&check())
{
ll ans=0;
for(int i=0;i<n;i++)
{
ans=ans*10+(s[c[i]]-'0');
}
if(ans>Max)
{
Max=ans;
}
if(ans<Min)
{
Min=ans;
}
}
}while(next_permutation(c,c+n));
cout<<Min<<" "<<Max<<endl;
}
return 0;
}
dfs枚举步数
#include<bits/stdc++.h>
using namespace std;
int cnt,k,a[15],mi,ma,t,n,b[15],i;
void dfs(int p,int d){
if(p>=cnt)return;
if(d>k)return;
if(a[0]==0)return;
int tp=0;
for(int i=0;i<cnt;i++){
tp*=10;tp+=a[i];
}
mi=min(tp,mi);ma=max(tp,ma);
for(int i=p;i<cnt;i++){
swap(a[p],a[i]);
if(i==p)dfs(p+1,d);
else dfs(p+1,d+1);
swap(a[p],a[i]);
}
}
int main(){
cin>>t;
while(t--){
scanf("%d%d",&n,&k);
cnt=0;
while(n){
b[cnt++]=n%10;n/=10;
}
for(i=0;i<cnt;i++)a[i]=b[cnt-1-i];
k=min(k,cnt-1);
mi=1e9+1;
ma=0;
//cout<<"hi"<<endl;
dfs(0,0);
printf("%d %d
",mi,ma);
}
}