题意:给定一个长度为n的序列,q次查询,每次查询都询问所有长度为L的连续子序列的不同数的个数的和。

思路:对于长度为L的查询来说,递推到L+1,其实就是看看每个数是否可以为前面的L的序列贡献一个1.

如果可以贡献1的话,那么这个数的要求就是和他相同的前一个数的位置之差要大于等于L。

然后减去最后面长度为L的序列的个数就好。大多都可以预处理。。 想了好长时间一直以为要用树状数组优化的dp。最终还是看的题解。。也是简单。。

 

HDU 5550 Game Rooms(dp)

题意:有n层楼,每层楼要建一个游泳池或者乒乓球馆,每层楼的人都有一些想去打乒乓球或者游泳的人,问怎么建立这些 体育设施,可以使得所有楼层的人去自己想...

阅读全文

Aizu 2595 Cookie Counter(dp+Lucas定理+树状数组优化)

题意:有n个饼干,分day天吃完,每天吃的饼干数量要小于m,问有多少种吃法可以把这n个饼干吃完。 思路:因为day为10^14,而n只有2000,所以我们如果把饼干全...

阅读全文

HDU 3450 Counting Sequences(dp+离散化+树状数组)

题意:给定一串数,问有多少种子串(非连续),他们相邻两个元素的差值小于等于d。 思路:d[i] 来表示以第i个数为结尾的方法数。那么我们在访问第i个元素的时...

阅读全文

欢迎留言

*