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

点击跳转

[l,r]之间最小值位置为p,原数组为a

那么左端点在[l,p],右端点在[p,r]的区间的最小值都是a[p]

那么这部分的贡献为a[p] \times (p-l+1) \times (r-p+1)

接下来还有[l,p-1],[p+1,r]没有处理

pre_ii前第一个比a[i]小的数的位置(用单调栈筛出)

存在x,满足pre_x=p

f[l][r]表示以r为右端点,左端点在[l,r]的区间的答案

那么f[l][r]=f[l][pre_r]+a_r\times(r-pre_r)

因为f的变化只与r有关,所以可以删掉一维

那么f_r= a_r \times (r-pre_r) +f_{pre_r}

所以[p+1,r]的答案就是f_r-f_{p-1}

[l,p-1]求法类似

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
查看原题

点击跳转

蒟蒻懒得学马拉车,于是就用hash写了。

预处理出每个点作为回文串的左端点和右端点时回文串最长为多少

然后枚举断点,统计答案就可以了

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

点击跳转

关于同一张图上的最小生成树,有一些性质:

对于任意权值的边,所有最小生成树中这个权值的边的数量是一定的

对于任意正确加边方案,加完小于某权值的所有边后图的连通性是一样的

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

点击跳转

好题

思路很妙

L[i][j]表示区间[i,j-1]作为j的左儿子是否合法

R[i][j]表示区间[i+1,j]作为i的右儿子是否合法

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

点击跳转

思路很妙

我们可以先求出n到每个点的距离

如果直接枚举k个干草堆,然后判断每个点是否可行,\Theta(nk)的复杂度显然TLE

因为一定要经过干草堆,所以可以新建一个节点n+1,向所有干草堆连单向边(边权为这个干草堆的影响)

在从n+1跑一遍最短路就可以了

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

点击跳转

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

点击跳转

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

点击跳转

算法:贪心+堆维护

贪心策略:

我们考虑先按t贪心,中途再更改。 按t从小到大排序之后,开始轮流遍历每个建筑。 如果中途某个建筑i无法在t_it的时间内修复,那么在先前选择修复的建筑中拿出a_j最大的j号建筑。若a_i < a_j,则放弃j转而修i

策略证明:

若第i号出现时间不足,那么前i个建筑中最多修复i-1个建筑 则我们必然选择a_i较小的前i-1个建筑,给后面的修复留下更多的时间 实现方法:

使用堆来维护选择的建筑中a_i最大的。

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

点击跳转

70/73
Search
search