【多题合集】【loliの模拟赛】排列组合大套餐

有兴趣的同学可以去下数据包自己做一下
——————————————————————————————————————————————————————
1、 输入一行字母（长度小于等于10），输出：第一行输出全排列个数，从下一行开始按字典序输出这些字母所有可能的排列，每行一个。
思路：个数为长度阶乘，直接暴力即可，注意读入and输出的优化，不然长度为10时会爆

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[200],l,k,c[200];
char b[200];
char s[30];
void ja()
{
    int ans=1;
    for (int i=1;i<=k;i++) ans*=i;
    printf("%d\n",ans);
}
void f(int x)
{
    if (x==k) 
        puts(b);
    else 
        for (int i=1;i<=c[0];i++)
        if (a[c[i]]) 
        {
            b[x]=c[i];
            a[c[i]]=0;
            f(x+1);
            a[c[i]]=1;
        }
}
main()
{
    gets(s);
    l=strlen(s);
    for (int i=0;i<=l-1;i++) 
    {
        if (a[s[i]]==0) k++;
        a[s[i]]=1;
    }
    for (int i=65;i<=125;i++) 
    if (a[i]>0) c[++c[0]]=i;
    ja();
    f(0);
}

2、 第一行输入一个字符串，（长度小于等于15）第二行输入一个数字m,输出：第一行输出从这个字符串里面选出m个的组合数，从下一行开始按字典序输出可能的组合（每个组合也要把字母按字典序排好，每行一个。）
思路：组合数，排序后直接搞就可以了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char s[30],b[30];
int l,m,a[300],c[300],k;
long long jc(int x)
{
    long long k=1;
    for (int i=2;i<=x;i++) k*=i;
    return k;
}
void ja()
{
    long long a1=1,a2=1,a3=1;
    a1=jc(m);
    a2=jc(l-m);
    a3=jc(l);
    printf("%lld\n",a3/(a2*a1));
}
void f(int x,int y)
{
    if (y==m) puts(b);
    else 
    for (int i=x+1;i<=k;i++)
        {
            b[y]=c[i];
            f(i,y+1);
        }
}
main()
{
    gets(s);l=strlen(s);
    scanf("%d",&m);
    ja();
    for (int i=0;i<l;i++) a[s[i]]++;
    for (int i=65;i<=130;i++)
        while (a[i]>0) {c[++k]=i;a[i]--;}
    f(0,0);
}

3、输入一行字母（长度小于等于26）,输出它所有的全排列里面，按字典序排在它后面的那个。
思路：（如果有同学愿意用STL模版也没问题）我的想法是从末尾开始找，找到有一个位置i，它(s[i])的后面有比它更大的字母，然后在后面这些比它大的字母中找出最小的一个字母s[j]，将两者交换，然后对位置i后的字母进行降序排列就可以了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char s[30],s1[30];
int l,a[200];
bool flag=false;
string c="";
void ff(int x)//排序
{
    if (x>=l) return;
    int t=x;
    for (int i=x+1;i<l;i++)
    if (s[i]<s[t]) t=i;
    char ge;
    ge=s[x];
    s[x]=s[t];
    s[t]=ge;
    ff(x+1);
}
void f(int x)//找字母
{
    int t=x;
    for (int i=x+1;i<l;i++)
    if (s[i]>=s[x]&&(s[t]>=s[i]||t==x)) t=i;  
    if (t!=x) 
    {
        char ge;
        ge=s[x];
        s[x]=s[t];
        s[t]=ge;
        flag=true;
        ff(x+1);
    }
    else  f(x-1);
}
main()
{
    gets(s);
    l=strlen(s);
    f(l-1);
    puts(s);
}

4、第一行输入一个字符串，第二行输入一个数字m,输出这些字母的全排列里面按字典序排名m的序列。
思路：我们可以对原字符串进行排序，存到一个新字符串中，然后对原字符串从头到尾的每一位进行判断，由此可以判断出它的序号。
比如（ans初始值为1）排序后为abc，则序号应该是3！=3*2！（字符串长度），若第一位为a，那么序号应该在1~1*2！；若为b则序号在(1*2！+1)~2*2！；若c则在(2*2！+1)~3*2！，以此类推，每确定一位后将长度–，逐个累加即可

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long m,l,num=1;
char s[300],s2[300];
string s1="";
long long jia(long long x)
{
    long long t=1;
    for (int i=2;i<=x;i++)
    t*=i;
    return t;
}
void solve(int x)
{
    if (x==strlen(s)) return;
    for (int i=1;i<=l;i++)
    if (m>=(i-1)*jia(l-1)+1&&m<=i*jia(l-1))//在这个范围内
    {
        putchar(s1[i-1]);
        for (int j=i;j<l;j++) s1[j-1]=s1[j];
        m-=(i-1)*jia(l-1);
        l--;
        solve(x+1);
        break;
    }
}
main()
{
    gets(s);
    l=strlen(s);
    scanf("%lld",&m);
    for (int i=0;i<l;i++) s2[i]=s[i];
    sort(s+0,s+l);
    for (int i=0;i<l;i++) s1+=s[i];
    solve(0);
}

5、输入一行字母输出它在这些字母的全排列里面按字典序的序号。
思路：把上面的讨论倒过来用就可以了，这里我们可以对字符串进行字符删除操作

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
long long num=1,ans=1;
long long  m,l,ja[30000];
char s[30000],s2[30000];
bool flag[30000];
string s1="";
void f()
{
    ja[0]=1;
    for (int i=2;i<=l;i++)
    {
        ja[i-1]=num;
        num*=i;
    }
    ja[l]=num;
}
void pd(int x)
{
    if (x==strlen(s2)) return;
    int k=s1.find(s2[x],0);
    int sum=0;
    ans+=(k*ja[(strlen(s2)-x-1)]);
    for (int i=k+1;i<l;i++)
    s1[i-1]=s1[i];
    l--;
    pd(x+1);
}
main()
{
    gets(s);l=strlen(s);
    for (int i=0;i<l;i++) s2[i]=s[i];
    sort(s+0,s+l);
    for (int i=0;i<l;i++) s1+=s[i];
    f();
    pd(0);
    cout<<ans;
} 

6、输入一行字母（长度小于等于9，可能有重复字母），输出：第一行输出全排列个数，从下一行开始按字典序输出这些字母所有可能的排列，每行一个。
思路：把全排列数算出来，然后除以(sum(c[1])!sum(c[2])!..sum(c[n])!)(sum()是该元素出现个数)。
至于重复，我们可以加一个flag判断一下blabla，我说不下去了，自己看吧

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[200],l,c[200],jia[200],ans;
char b[200];
char s[30];
bool flag[300];
int ja(int x)
{
    int ans=1;
    jia[0]=1;
    for (int i=2;i<=x;i++) 
    {jia[i-1]=ans;ans*=i;}
    jia[x]=ans;
    return ans;
}
void f(int x)
{
    if (x==l) 
        puts(b);
    else 
        for (int i=1;i<=c[0];i++)
        if (!flag[i]&&(c[i-1]!=c[i]||!flag[i-1]))
        {
            flag[i]=true;
            b[x]=c[i];
            f(x+1);
            flag[i]=false;
        }
}
main()
{
    gets(s);
    l=strlen(s);
    for (int i=0;i<=l-1;i++) 
    a[s[i]]++;
    ans=ja(l);
    for (int i=65;i<=125;i++) 
    {
        int p=a[i];
        while (p>0) {c[++c[0]]=i;p--;}      
        ans/=jia[a[i]];
    }
    printf("%d\n",ans);
    f(0);
}

7、第一行输入一个字符串（长度小于等于15可能有重复字母），第二行输入一个数字m,输出：第一行输出从这个字符串里面选出m个的组合数，从下一行开始按字典序输出可能的组合（每个组合也要把字母按字典序排好，每行一个。）
思路：最后一题懒得仔细想了，直接STL狗，重复两次，第一次算数目，第二次输出，暴力解决︿(￣︶￣)︽(￣︶￣)︿

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;
char s[30],b[30];
int l,m,a[300],c[300],k,ans;
map<string,bool> flag,hh;
long long jc(int x)
{
    long long k=1;
    for (int i=2;i<=x;i++) k*=i;
    return k;
}
void f(int x,int y)
{
    if (y==m) 
    {
        string s="";
        for (int i=0;i<m;i++) s+=b[i];
        if (!flag[s])
        {
            flag[s]=true;
            ans++;
        }
    }
    else 
    for (int i=x+1;i<=k;i++)
        {
            b[y]=c[i];
            f(i,y+1);
        }
}
void fff(int x,int y)
{
    if (y>=m) 
    {
        string s="";
        for (int i=0;i<m;i++) s+=b[i];
        if (!hh[s])
        {
            hh[s]=true;
            puts(b);
        }
    }
    else 
    for (int i=x+1;i<=k;i++)
        {
            b[y]=c[i];
            fff(i,y+1);
        }
}
main()
{
    gets(s);
    l=strlen(s);
    scanf("%d",&m);
    for (int i=0;i<l;i++) a[s[i]]++;
    for (int i=65;i<=130;i++)
        while (a[i]>0) {c[++k]=i;a[i]--;}
    f(0,0);
    printf("%d\n",ans);
    fff(0,0);
}