POJ 1850 code(组合数学)

POJ 1850 code

题目大意

将字母和单词(全部小写并且按照字典序递增)按照字典序编号，比如 a-1 b-2 … z-26 ab-27 … az-51 … 给你一个字母或单词，问你它的编号

分析

以树状的结构来分析这道题会比较直观。 按照树的节点依次编号，每个字母或单词就落在一个节点上。要求一个单词的编号，比较直接的想法是分别求出该 单词上一层的最大编号和该单词在当前层中所处的位置。（根节点为第0层）

下面分别进行讨论

上一层的最大编号

某一层的节点数是有规律可循的，而某一层的最大编号则是该层及之前所有层的节点数之和。

令第i层的节点数为 Fi

数学公式 Cmn=∑n−1i=1Cm−1i(1)

F1 =26

F2 =25+24+…+1= ∑25i=1i = C226 = C125+C124+...+C11 = ∑25i=1C1i

F3 = ∑24i=1(∑ij=1C1j) = ∑24i=1C2i+1 = C326

同理 F4 = C426 （求出前三个第四个也可以猜出来了）

…

某一层k的最大编号则是 F1+F2+...+Fk​ ，找不到化简公式也可以直接用循环直接求出来。

当前层中所处的位置

求在当前层中所处的位置则要复杂一些了，看似不是规则的树状结构，但仔细观察后发现这棵树是具有自相似性的，比如以编号为1的节点为根节点的子树具有和原树一样的性质。基于这一条启发式信息，问题就可以求解了.

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; #define LL long long int char s[11];//输入 int bj[30];//标记之前某个字母是否被访问过 LL f[27][11];//f[i][j]表示对于根节点有i个分支第j层的节点数, 根节点是第0层 LL A[11]; int Find_loc(char c0,char c,int bj[])//在某些字母被标记的情况下询问字母c处于字母树中的第几个分支,c0是前一个字母 { int cnt=0; for(int i=(int)c0-96+1;i<=26;i++) { if(bj[i]==0)cnt++; if(i==(int)c-96){return cnt;} } } void Get_A() { LL t=1; for(int i=1;i<=10;i++){t=t*i;A[i]=t;} } void Get_f() { LL x; for(int i=1;i<=26;i++) { f[i][0]=1; x=1;//保存当前层的节点数 for(int j=1;j<=min(10,i);j++) { x=(i-j+1)*x; f[i][j]=x/A[j]; } } } bool Check(char s[]) { int lenth=strlen(s); if(lenth>10)return 0; for(int i=1;i<lenth;i++)if(s[i]<s[i-1])return 0; return 1; } void Work() { LL ans=0; int lenth=strlen(s); if(Check(s)==0){cout<<0<<endl;return ;} int loc; LL node=26;//保存当前的节点的父亲的分支数 for(int i=1;i<=lenth-1;i++)ans+=f[26][i];//求上一层的最大编号 //cout<<"before_ans: "<<ans<<endl; for(int i=0;i<lenth;i++) { if(i==0)loc=(int)s[i]-96; else loc=Find_loc(s[i-1],s[i],bj); bj[(int)s[i]-96]=1; for(int j=1;j<loc;j++)ans+=f[node-j][lenth-i-1]; node=node-loc;//更新node } ans+=1; cout<<ans<<endl; } int main() { Get_A(); Get_f(); while(scanf("%s",s)!=EOF) { Work(); } }