1001
LUCKY STRING
1872
8254
22%
题目描述
A string s is LUCKY if and only if the number of differentcharacters in s is a fibonacci number. Given a string consisting of only lowercase letters , output all its lucky non-empty substrings in lexicographicalorder. Same substrings should be printed once.
输入描述:
a string consisting no more than 100 lower case letters.
输出描述:
output the lucky substrings in lexicographical order.one perline. Same substrings should be printed once.
输入例子:
aabcd
输出例子:
a
aa
aab
aabc
ab
abc
b
bc
bcd
c
cd
d
看来浙大pat果然比我想的要简单
这一题给你一个字符串，让你输出其所有符合要求的子串，要求为子串中不同的字符数要是一个沉默的奇异果数，且子串要按照字典序输出，相同的子串不能重复输出
沉默的奇异果数为沉默的奇异果数列中的数
这一题要是不使用stl的话确实挺难的，但是可以借助stl中的set数据结构简化过程
Set数据结构具有一个性质，就是其中的所有数都是唯一的，假如插入相同的数，相同的数会被消除掉，并且其中的数会默认按照从小到大的顺序排列，这一点set和map非常像。Map中的成员会按照key从小到大排序，并且会自动消除相同的数据
那么set如何从大到小排序呢，自定义成员如何排序呢
自定义成员可以使用友元操作符重载，（这里需要注意的，对于某个类而言，假如已经在他的定义里面重载了操作符，那么不能再在外面重载操作符，因此在主函数外面重载不是自己定义的类的操作符是不行的）
第二组方法是使用函数对象，即可以像调用函数一样调用的对象，程序封装了两个默认的函数对象，分别为greater<T>，和less<T>，一个是按照从大到小的顺序排列，一个是按照从小到大的顺序排列，不过greater<T>我貌似没有找到，我们也可以自己定义
Struct tmp {
Bool operator ()(const & T a,const & T b)
{
Return a<b;
}
以上这个是按照从小到大排序的自定义函数，这里需要注意的是，当对map定义排序函数的时候，要针对key来定义排序类，而不是像sort一样，是针对线性表里面的成员的类别定义排序函数
Map和set都是使用红黑树来存储的！
#include<iostream>
#include<set>
#include<vector>
using namespacestd;
int main()
{
string theNum;
cin >> theNum;
set<string> theMark;
bool theC[22] = { false };
int one = 1,two=1,tmp;
tmp = one + two;
theC[one] = true; theC[two] = true;
while (tmp < 26)
{
theC[tmp] = true;
one = two;
two = tmp;
tmp = one + two;
}
vector<bool> theTmpMark(26, false);int theAllAlpha = 0;
for (int i = 0; i < theNum.size(); i++)
{
for (int j = i; j <theNum.size(); j++)
{
if(!theTmpMark[theNum[j]-'a'])
{
theAllAlpha++;
theTmpMark[theNum[j] -'a'] = true;
}
if (theC[theAllAlpha])
{
theMark.insert(theNum.substr(i,j - i + 1));
}
}
theAllAlpha = 0;
for (int i = 0; i < 26; i++)
theTmpMark[i] = false;
}
for (auto u : theMark)
{
cout << u<<endl;
}
return 0;
}