#UVa:417-Word Index

灆洢 2016-03-15 14:40:38

先將前一項的編號算出再加1即可得解。

利用排列組合將字串長度比較小的部分個數算出,再來對於該字串每一位去算出前面包含的字串個數,將這些個數總和起來即是前一項之編號。

C++(0.000)

/*******************************************************/
/* UVa 417 Word Index                                  */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/03/15                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

bool isValid(string s){
  for( int i = 0 ; i < s.length() ; ++i ){
    if( s[i] <= s[i-1] ){
      return false;
    }
  }

  return true;
}

int main(){
  int C[30][30] = {0};
  C[0][0] = 1;
  for( int i = 1 ; i <= 26 ; ++i ){
    C[i][0] = 1;
    C[i][i] = 1;
    for( int j = 1 ; j < i ; ++j ){
      C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
  }

  string word;
  while( cin >> word ){
    if( !isValid(word) ){
      printf("0\n");
      continue;
    }

    int index = 0;
    for( int i = 1 ; i < word.length() ; ++i ){
      index += C[26][i];
    }

    for( int i = 0 ; i < word.length() ; ++i ){
      int laterLength = word.length() - i - 1;
      for( char c = ((i == 0)? 'a' : word[i-1]+1) ; c < word[i] ; ++c ){
        int canUseAlphabetCount = 'z' - c;
        index += C[canUseAlphabetCount][laterLength];
      }
    }
    printf("%d\n", index+1);

  }

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料