hihoCoder week 84-1-Lucky Substrings 题目1 : Lucky Substrings 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters, output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once. 输入 A string consisting no more than 100 lower case letters. 输出 Output the lucky substrings in lexicographical order, one per line. Same substrings should be printed once. 样例输入 aabcd 样例输出 a aa aab aabc ab abc b bc bcd c cd d
如果一个字符串中不同字母的个数是斐波那契数，则称这个字符串是Lucky的，问字符串S中哪些子串是Lucky子串。 要正确理解Lucky的定义，是不同字母的个数，而不是不同字母的个数序列。比如aabc是Lucky的，因为其有a,b,c共3种字母，而3在斐波那契数列中，所以aabc是Lucky的。不能理解为aabc中a出现2次，b,c分别出现1次，构成1,1,3是斐波那契数列，所以aabc是Lucky的。 所以只能枚举所有子串，判断每个子串是否为Lucky的。如果知道了S[i,…,j]中不同字母的个数，判断S[i,…,j+1]时，只要判断S[j+1]这个字母是否在之前出现过。所以通过保存之前不同字母的个数，可以快速判断S[i,…,j+1]的情况。 完整代码如下： [cpp] #include<iostream> #include<string> #include<set> #include<vector> using namespace std; set<int> FIB_NUM = { 1,2,3,5,8,13,21 }; int main() { string s; cin >> s; set<string> ans; int n = s.size(); for (int i = 0; i < n; i++) { vector<bool> alphabet(26, false); int cnt = 0; for (int j = i; j < n; j++) { if (!alphabet[s[j] – ‘a’]) { alphabet[s[j] – ‘a’] = true; cnt++; } if (FIB_NUM.find(cnt) != FIB_NUM.end()) { ans.insert(s.substr(i, j – i + 1)); } } } set<string>::iterator it = ans.begin(); while (it != ans.end()) { cout << *it << endl; it++; } return 0; } [/cpp] 本代码提交AC，用时17MS，内存0MB。]]>