題目描述
如果用a b c d這4個字母組成一個串，有4!=24種，如果把它們排個序，每個串都對應(yīng)一個序號：
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
現(xiàn)在有不多于10個兩兩不同的小寫字母，給出它們組成的串，你能求出該串在所有排列中的序號嗎？

輸入
一行，一個串。
輸出
一行，一個整數(shù)，表示該串在其字母所有排列生成的串中的序號。注意：最小的序號是0。
樣例輸入
bdca
樣例輸出
11
康托展開和逆康托展開是針對這一問題的，但是我沒有仔細研究過。
思路：
拿樣例來分析：bdca，對于第一個位置來說，是b，它排在第二位。那么以a開頭的就肯定排在它的前面；再分析第二個位置d，它排在第4位，第1個位置就是b了，那么bd前面的就是以ba,bc開頭的了；再分析第三個位置c，它排在第三位，前兩位就是bd了，那么排在bdc前面的就只有bda開頭的了…一直這樣分析下去就可以了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;string s,t; int vis[15];inline ll fcs(int n)//求n的階乘 {ll ans=1;for(int i=1;i<=n;i++) ans*=i;return ans; } inline int judge(int pos)//判斷pos位前面有幾個還沒有被用 {int ans=0;for(int i=0;i<pos;i++) if(vis[t[i]-'a']==0) ans++;return ans; } int main() {cin>>s;t=s;sort(t.begin(),t.end());ll ans=0;memset(vis,0,sizeof(vis));for(int i=0;i<s.length();i++){int pos=lower_bound(t.begin(),t.end(),s[i])-t.begin();pos=judge(pos);ans+=pos*fcs(s.length()-i-1);vis[s[i]-'a']=1;}cout<<ans<<endl;return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][2014年第五届真题]排列序数（思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。