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

点击跳转

我们可以发现如果p\le x,那么x\mod p \le \frac x2

所以取模最多\log x

记录区间最大值,如果小于p那么直接返回

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

点击跳转

解释见代码

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

点击跳转

详见四边形不等式优化

最小值有单调性,可以使用四边形不等式优化

但是最大值没有

但是最大值有个性质:

一定是一直把其他石子合并到某堆石子

那么我们可以f[l][r]=\max(f[l][r-1],f[l+1,r])+S_r-S_{l-1}

相当于一直向左边的石子合并或右边

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

点击跳转

一个区间合法,仅当这个区间中包含的颜色没在区间外出现过

我们可以把每种颜色出现的每个位置都赋值使得这些位置上的值加起来为0

这样我们就可以用前缀和的方式统计了

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

点击跳转

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想到AC自动机最短路(貌似是最短哈密顿路径?)

每个字符串长度都小于50,如果用AC自动机可能就核弹打蚊子

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

点击跳转

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

然后就是树剖了

用树状数组维护前缀和

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

点击跳转

题意:

给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选, 给出每个节点的选择方案数,求总方案数

解法

考虑到限制是每列选择的不能超过一半,我们可以想到不合法的最多只有一列

我们可以用总方案数减去不符合的

s_i=\sum_{j=1}^m a_{ij}

总方案数:\prod_{i=1}^n (s_i+1) - 1

\because k=\frac {tot}2

所以我们有一个很妙的方法:

设选中目标行之外的权值+1,不选+0,选中目标行权值位+2

最后只要权值> n,那么目标行一定被选了超过\frac n2

f(i,k)表示总共选了i次(也就是选到第i行)权值为k的方案数

f(i,k) += f(i-1,k)*(s_i-a_{ij})(当前行不选目标列

f(i,k+1) += f(i-1,k)(当前行完全不选

f(i,k+2) += f(i-1,k)\times a_{ij}(当前行选中目标列

ans = \prod_{i=1}^n (s_i+1) - 1 - \sum_{i=n+1}^{2n} f(n,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
查看原题

点击跳转

因为边权为1,所以直接跑奇偶最短路即可

但是当x=y时,我们需要判断x是否有向外连边

67/73
Search
search