字典序问题.docVIP

#includeiostream #includestring using namespace std; // g_sumi[i] 表示长度为i的总数 const int g_sumi[7] = {0, 26, 325, 2600, 14950, 65780, 230230}; // 返回以start开头，长度为len的总数 int Sum(int start, int len) { if (len == 1) return 1; int sum = 26 - start; for (int i = 26 - start - 1; i 26 - start - len + 1; i--) { sum *= i; } for (int i = len - 1; i 1; i--) { sum /= i; } return sum; } inline int GetNum(char c) { return c - a + 1; } int GetResult(string s) { int len = s.size(); int result = 0; // 小于字符串长度的总数 for (int i = 1; i len; i++) { result += g_sumi[i]; } // 小于首位的总数 for (int i = GetNum(a); i GetNum(s[0]); i++) { result += Sum(i, len); } // 其他情况 for (int i = 1, start = GetNum(s[0]); i len; i++) { // 上一位 + 1 ，当前位 - 1 for (int j = start + 1; j GetNum(s[i]); j++) { result += Sum(j, len - i); } start = GetNum(s[i]); } return result + 1; } bool IsRight(string s) { if (s.size() 6) { cout ERROR: s 长度大于6 endl; return false; } bool flag = true; for (int j = 1; j s.size(); j++) { if (s[j] a || s[j] z) { cout ERROR: s 不合法 endl; flag = false; break; } else if (s[j] s[j - 1]) { cout ERROR: s 不是升序 endl; flag = false; break; } } return flag; } void main() { freopen(input.txt, r, stdin); freopen(output.txt, w, stdout); int num; cin num; for (int i = 0; i num; i++) { string s; cin s; if (IsRight(s)) { cout GetResult(s) endl; } } } /* // 计算长度为len的总数 int SumI(int len) { int sum = 26; for (int i = 26 - 1; i 26 - len; i--) { sum *= i; } for (int i = len; i 1; i--) { sum /= i; } return sum; } */