zcmimi's blog

categories/刷题记录/共659篇文章

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

点击跳转

S_i[1,i]\ge w的数的个数

如果一个区间要满足中位数\ge w,那么\frac {S_r-S_{l-1}}{\frac {r-l+1}2} \ge w

化简一下:2S_r-r > 2S_{l-1}-(l-1)

那么二分w然后用树状数组统计之后判断排名是否\ge k就可以了

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

点击跳转

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

点击跳转

求出LCA

如果

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

点击跳转

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

点击跳转

删除完这个字符串后面的就接到前面

我们可以想到用栈解决

然后判断剩下的串当前位置是否和目标字符串匹配我们可以用hash来解决

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

点击跳转

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

点击跳转

其实下面给出的a数组没什么鸟用

列出方程:

E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E)

解方程: E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E) \\\\ E = \sum_{i=0}^{n-1} \frac in + (1 - \frac mn)E \\\\ \frac mnE = \frac {\frac 12n(n-1)}n \\\\ E = \frac {n(n-1)}{2m}

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

点击跳转

avatar
zcmimi
2019-01-21 18:36:18

LG 3953 逛公园

题意: 求dis(1,n)<=MinDis(1,n)+K的路径数

用拓扑啊什么的一想就很麻烦。

有一种玄学的做法:记忆化搜索

f[x][k]表示dis(x,n)<=MinDis(x,n)+k的路径数。

先跑一般反向的最短路,然后dfs

考虑边(x,y,w),

\because Mindis[x]-Mindis[y]+w<k

\therefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)]

\therefore f[x][k] = \sum f[y][k-(Mindis[x]-Mindis[y]+w)]

66/66
Search
search