題目地址:
POJ 1496 Word Index
POJ 1850 Code
題意:
1. 每個詞是自增的
2. 同樣長度的詞是按字典序排練的
3. 我們把這些詞標序
求某個詞的序號
分析:
組合數學...
推出公式然後用楊輝三角打表出組合數,具體看http://blog.csdn.net/lyy289065406/article/details/6648492。
我還是太弱Orz...
代碼:
1496:
/* * Author: illuz* File: 1496.cpp * Create Date: 2014-05-24 23:38:54 * Descripton: */ #include #include #include const int N = 27; int c[N][N], len, sum; char str[11]; void init() { for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++) if (!j || i == j) c[i][j] = 1; else c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; c[0][0] = 0; } int main() { init(); while (~scanf("%s", str)) { len = strlen(str); bool flag = true; for (int i = 1; i < len; i++) if (str[i - 1] >= str[i]) { puts("0"); flag = false; } if (!flag) continue; sum = 1; for (int i = 1; i < len; i++) { sum += c[26][i]; } for (int i = 0; i < len; i++) { char ch = (0 == i) ? 'a' : str[i - 1] + 1; while (ch <= str[i] - 1) { sum += c['z' - ch][len - i - 1]; ch++; } } printf("%d\n", sum); } return 0; }
1850:
/* * Author: illuz* File: 1850.cpp * Create Date: 2014-05-24 23:10:11 * Descripton: */ #include #include #include const int N = 27; int c[N][N], len, sum; char str[11]; void init() { for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++) if (!j || i == j) c[i][j] = 1; else c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; c[0][0] = 0; } int main() { init(); scanf("%s", str); len = strlen(str); for (int i = 1; i < len; i++) if (str[i - 1] >= str[i]) { puts("0"); return 0; } sum = 1; for (int i = 1; i < len; i++) { sum += c[26][i]; } for (int i = 0; i < len; i++) { char ch = (0 == i) ? 'a' : str[i - 1] + 1; while (ch <= str[i] - 1) { sum += c['z' - ch][len - i - 1]; ch++; } } printf("%d\n", sum); return 0; }