zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

动态规划

f[n][k]表示n个节点,高度为k

根节点是固定不变的

左右子树可以自由变换

那么:

f[n][k] = \sum_{i=1}^n f[i][k-1] \times f[n-i-1][k-1]

挺好的题

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Favorite-Dice top: 0

我是没看题解和标签写出来的,完全不知道这是期望

假设你已经取了i个面,你取到没取过的一个面,概率是\frac {n-i}n

把所有概率加起来就是答案啦,也就是\sum_{i=0}^{n-1} \frac {n-i}n

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先预处理出以i结尾最长多少个连续

然后rmq预处理

查询的时候要先查以左端点开始最长多少,然后再求剩下的那段区间

注意多组数据

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Robotic-Sort top: 0

同排序机械臂

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

D-query top: 0

就是莫队的板子题

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Rainbow-Ride top: 0

用并查集合并联通块,然后背包

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

GCD-Extreme top: 0

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

$$

\sum{i=1}^{n-1} \sum{j=i+1}^n \gcd(i,j)

\\

= \sum_{i=1}^n g(i)

$$

$$

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

\\

= \sum{d|n}d \sum{i=1}^{n-1}[gcd(i,n)=d]

\\

= \sum{d|n}d \sum{i=1}^{\frac nd - 1}[gcd(i,n)=1]

\\

= \sum_{d|n}d \times \varphi(\frac nd);

$$

求出g的前缀和

可以用筛的方式求g

O(n \sqrt n + T);

不能用之前的套路,否则会tle

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

ABCDEF top: 0

\frac{a \times b + c}d -e = f

a \times b + c = de+df

我们可以先搜索a+b+c可能的结果和de+df可能的结果,然后合并即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Fake-tournament top: 0

tarjan强连通分量缩点一下

最多只有一个入度为0的点,

否则就是没有符合条件的点

72/74
Search
search