zcmimi's blog

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

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

点击跳转

看了看数据范围,可以知道是状态压缩+区间dp

我们设f[i][j][t]表示[i,j]合并后状态为t获得的分数

f[i][j][t] = f[i][k][t'] + f[k+1][j][t''] (t'|t'' = t)

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

点击跳转

f(i,k)表示将前i个分k次的分数

我们可以dpk次就可以了

f_i为前i个,g_i为上一次dp的结果

f_i=\max_{j=1}^{i-1}(g_j+s_j\times(s_i-s_j))

取任意0\le k<j <i且从j转移比从k更优,那么

g_j+s_j\times(s_i-s_j)\ge g_k+s_k\times(s_i-s_k) 展开得

g_j+s_is_j-{s_j}^2\ge g_k+s_is_k-{s_k}^2 移项得 s_i(s_j-s_k) \ge {s_j}^2-{s_k}^2+g_k-g_j 整理得 s_i\ge \frac{({s_j}^2-g_j)-({s_k}^2-g_k)}{s_j-s_k}

注意s_j-s_k有可能为0,要特判

因为要求的是最大值,所以我们维护一个上凸壳就可以了

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

点击跳转

考虑如何快速找出拥有(与它的前缀相同的)后缀的串。这个东西可以通过把字符串放到Trie里面。 分类两种情况,短串+长串长串+短串。对于短串+长串的情况,先将字符串按len排序,然后顺序将字符串倒着插入trie里面,并在trie中的尾节点记录hash。利用当前串作为查询串来找答案,这样能保证当前串一定是长串,并且找到的所有短串都有和它的前缀相同的后缀,所以再利用hash判断一下就可以确定拼出来的是不是回文串了。另外一个情况同理。 复杂度是O(26\sum len)

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

点击跳转

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

点击跳转

同树网的核

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

点击跳转

\sum\limits_{i=l}^{r} a_i - k \lceil \frac{r - l + 1}{m} \rceil

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

点击跳转

61/65
Search
search