思路:看到题的第一反应就是完全背包模型,但是k非常大,抱着侥幸心理交了一发,果然超时了,后面想到其实可以用贪心的思路解,每次用不超过k的斐波那契数去凑k,然后k减去这个数,一直持续到k为0即可.
思路:看到题第一反应就是找规律,先是个数,长度为1的开心串有3个,长度为2的开心串有6个,长度为3的开心串有12个,所以显然长度为k的开心串个数是长度为k-1的开心串的个数的两倍.然后题目要求按字典序找到长度为n的第k个开心串,显然是递推的过程,长度为1时,有 a b c三种,长度为2时是在长度为1的基础上增加的,对于a来说可以加两个字母 bc对b来说可以加两个字母 ac对c来说可以加ab所以长度为2时有6种按字典序分别为
abacbabccacb,长度为3时,是在长度为2的基础上加的,构造过程相同,只需要判断上一个长度(当前长度为3时上个长度为2)的字符串的最后一位是什么就能判断要在上个长度字符串的后面加什么字符构造长度加1的开心串.要注意无解的情况
int cnt=0;
版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议.转载请注明出处!