首页 > 代码库 > poj1850(Code)
poj1850(Code)
题目地址：Code
题目大意：
按照字典序的顺序从小写字母a开始按顺序给出序列
a - 1
b - 2
...
z - 26
ab - 27
...
az - 51
bc - 52
...
vwxyz - 83681
...
输入字符串由小写字母a-z组成字符串为升序，根据字符串输出在字典里的序列号为多少。
解题思路：
排列组合，记住公式：
先看字符的长度一个字符的时候是26为C（26，1），两个字符的时候分别从以a开头的计算出25个，b开头的有24个...可以计算出C（26，2） 依次三个字符的时候C（26，3）....
所以给出的字符串先算比它长度小的字符串的总和再算和它长度相等的字符串有多少个，算相等的时候注意要始终算它的前一个字符的总和，这样才能保证正确性，算出的总和最后+1.就是这个字符串的序列号。
附详细解答：（转）http://hi.baidu.com/you289065406/blog/item/d0900ff85e4b0b71024f563a.html#0
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 //#include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 #define PI 3.141592721 /***************************************/22 const int INF = 0x7f7f7f7f;23 const double eps = 1e-8;24 const double PIE=acos(-1.0);25 const int d1x[]= {0,-1,0,1};26 const int d1y[]= {-1,0,1,0};27 const int d2x[]= {0,-1,0,1};28 const int d2y[]= {1,0,-1,0};29 const int fx[]= {-1,-1,-1,0,0,1,1,1};30 const int fy[]= {-1,0,1,-1,1,-1,0,1};31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1};32 const int diry[]= {-2,-2,-1,-1,1,1,2,2};33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/34 /***************************************/35 void openfile()36 {37 freopen("data.in","rb",stdin);38 freopen("data.out","wb",stdout);39 }40 priority_queue<int> qi1;41 priority_queue<int, vector<int>, greater<int> >qi2;42 /**********************华丽丽的分割线,以上为模板部分*****************/43 int C[30][30];44 int zuhe()45 {46 int i,j;47 for(i=0;i<30;i++)48 {49 C[i][0]=1;50 C[i][i]=1;51 for(j=1;j<i;j++)52 {53 C[i][j]=C[i-1][j-1]+C[i-1][j];54 }55 }56 }57 int main()58 {59 char s[15];60 zuhe();61 while(scanf("%s",s)!=EOF)62 {63 int sum=0;64 int len=strlen(s);65 int i;66 int ce=0;67 for(i=0;i<len-1;i++)68 if (s[i+1]<s[i])69 ce=1;70 if (ce)71 {72 printf("0\n");73 continue;74 }75 for(i=1;i<len;i++)76 sum+=C[26][i];77 char c;78 for(i=0;i<len;i++)79 {80 if(i)81 c=s[i-1]+1;82 else83 c=‘a‘;84 while(c<s[i])85 {86 sum+=C[‘z‘-c][len-1-i];87 c++;88 }89 }90 printf("%d\n",++sum);91 memset(s,0,sizeof(s));92 }93 return 0;94 }
poj1850(Code)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。