poj 1850 Code

点击打开链接poj 1850

思路：组合数学+排列组合
分析：
1 题目要求的是给定一个字符串判断是否满足题目的要求，如果是输出第几个，如果不是则输出-1.
2 那么首先我们应该先判断这个字符串是否是符合题目的字符串，如果不符和直接输出-1.
3 在字符串符合的情况下，那么我们就可以知道长度小于len的字符串都是符合条件的。
   现在长度为n的字符串最多可以到达的编号就是num = C(26,1)+C(26,2)+......+C(26,n);
   那么我们只要把不合法的全部扣除即可找到这个ans
4 现在假设字符串为"bcdg",不合法的序列有：1以'c'-'z'开头的长度为4的字符串即C(26-2,4)  2以b开头第二个字母大于c的长度为4的字符串即C(26-3 , 3)  
   3以bc开头然后第三个字母大于d的所有长度为4的字符串即C(26-4,2) 4以bcd开头然后第四个字母大于g的所有长度为4的字符串即C(26-7 , 1);
5 只要求出总的然后减去所有的不合法的即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 15

int len;
char ch[N];

/*判断输入的字符串是否符合*/
bool judge(){
   for(int i = 1 ; i < len ; i++)
      if(ch[i] <= ch[i-1])
         return false;
   return true;
}

long long sum(int num , int n){
   long long tmpx = 1;
   long long tmpy = 1;
   int i , j;
   i = num , j = n;
   for(; j ; j-- , i--){
     tmpx = tmpx*i;
     tmpy = tmpy*j;
   }
   return tmpx/tmpy;
}

int main(){
   while(scanf("%s" , ch) != EOF){
      len = strlen(ch);

      if(!judge()){
        printf("0\n");
        continue;
      }
      long long count = 0;
      for(int i = 1 ; i <= len ; i++)
         count += sum(26 , i);
      /*扣除不合法*/
      for(int i = 0 ; i < len ; i++){
         int n = 'z'-ch[i];
         count -= sum(n , len-i);
      }
      printf("%lld\n" , count);
   }
   return 0;
}