zcmimi's blog

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

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

点击跳转

先缩点,然后跑最长路

然后更新的时候顺便记录最大亮度就可以了

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

点击跳转

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

点击跳转

记录up[i][j]表示位置(i,j)可以向上多少个#

s[i][j]表示位置(i,j)作为三角形中心可以向左多少个#

S[i][j]表示位置(i,j)作为三角形中心可以向右多少个#

ans = \sum_{i=1}^n\sum_{j=1}^n \min(s[i][j],S[i][j])

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

点击跳转

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

我们可以想到用栈解决

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

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

点击跳转

先将b数组从小到大排序

设选中了xa > b,由总对数为n,由x-(n-x)=k,可以知道x=\frac{n+k}2

我们设f(i,j)为前ia中选中了ja > b的方案数

那么f(i,j)=f(i-1,j)+f(i-1,j-1)\times(l_i-j+1)

(l_i表示b中小于a_i的最后一个位置)

但是还有剩下的n-x

我们可以设g_i表示a>b对数\ge i的方案数

那么g_i = f(n,i) \times (n-i)!(相当于剩下的随便排列组合)

我们设f_i表示a>b对数恰好为i对的方案数

那么g_k = \sum_{i=k}^n f_i \times {i\choose k} (相当于从恰好i个方案中选k对出来)

经过二项式反演可以知道:

f(k)=\sum_{i=k}^n(-1)^{i-k}{i\choose k}g(i)

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

点击跳转

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

点击跳转

可以用并查集把环套树上额外的一条边找出来

然后就是树剖了

用树状数组维护前缀和

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

点击跳转

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

点击跳转

找祖先 top: 0

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

点击跳转

  1. b_i = a_i + 1

    一条链

    直接二分最小值,然后判断即可

  2. m=1

    直接找树的直径

  3. a_i = 1

    记录所有边权,设边权为w,然后排序

    w_1 + w_{2m} , w_2 + w_{2m-1}, ...的最小值

  4. 分支不超过3(基本上就是正解了)

明摆着就是正解嘛

dfs(x,f,w)求出x的子树连接x长度不超过w的最长路径

路径分为两种

一种\ge w,那直接条数++

另一种a+b \ge w

那我们直接用multiset存,每次lowerbound找到最接近的,然后返回

stl,还是太弱了Q\omega Q

54/66
Search
search