zcmimi's blog

arrow_back计数共3篇文章

avatar
zcmimi
2019-12-01

划分dp

题意

每组输入是两个整数nk(1\le n \le 50, 1 \le k \le n)

输出

对于输入的n,k;

第一行: 将n划分成若干正整数之和的方案数。

第二行: 将n划分成k个正整数之和的方案数。

第三行: 将n划分成最大

avatar
zc
2020-04-25 16:51:00
查看原题

点击跳转

枚举右端点r,当前颜色x

lst_x为颜色x上一次出现的位置

假设我们已经得知了f(l,r-1),l\in [1,r-1]

那么f(l,r),l\in [lst_x+1,r]=f(l,r-1)+1

也就是说我们把[lst_x+1,r]区间+1就可以了

于是这题就变成了线段树(或树状数组)维护区间平方和

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们考虑两个断点(设为l,r)符合的条件:

每种颜色的珠子只能出现在其中一条链中

也就是若[l,r]中出现了某种颜色[l,r]也就包含了所有的这种颜色

我们可以记录颜色出现的前缀和

记录前i个位置每种颜色的出现次数,如果位置i是 颜色a[i]的最后一个位置, 就把颜色 a[i] 的结果清零。

这样若两个位置的前缀和相同,就是合法的

可以通过hash来判断,记录所有hash值,排序后统计

两个分割点 l,r 要尽可能满足 r−l 接近 \frac n2

可以用类似双指针的方式维护

这题卡hash,要双hash

1/1
Search
search