zcmimi's blog

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

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

点击跳转

直接边bfs边判断就可以了

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

点击跳转

思路剧毒无比

f[i][j]表示在i的子树中,i所在的连体块大小为j\frac{\text{最大得分}}{j}

f[i][j] = \max(f[i][k] \times f[to][j-k])

f[i][0] = \max(f[i][0],f[i][j] \times j)

还没完

吐血的是还要写高精

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

点击跳转

可以用带权并查集维护

s_x表示x到父亲的异或值

当合并的时候

l=l-1

fl,fr分别为l,r的父亲

合并后应该是:s_r \bigoplus s_l = x

\because s_r' = x \bigoplus s_l, s_r' = s_r \bigoplus s_{fr}',

\therefore s_{fr}' = x \bigoplus s_l \bigoplus s_r

我们又看到0 \leq i < 2^{30}

我们可以用hash或map离散化

注意l,r可以为0,所以实际操作时应该++r

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

点击跳转

f[i][j]表示状态为i,上一个吃的是第j道菜

f[i'][k]=\max(f[i'][k],f[i][j]+a[j]+d[j][k]) (d[j][k]表示连续吃j,k能额外获得多少满意度)

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

点击跳转

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

点击跳转

如果没有时间限制那就是一个裸的完全背包

我们可以先按时间从大到小排序,保证如果选了后面作业能选的话不会影响当前作业

接着背包求出每天的最小花费

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

点击跳转

那个只要有 10000…… 11000…… …… 就可以一直搞下去 直到为0

但是也有特殊情况:

比如k \le 4

不过这种情况特判和dfs都可以解决

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

点击跳转

记录每个单词的hash值

然后按照题目所说操作

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

点击跳转

f_i为前i个最小代价

s_i为前i个字符串总字符数

f_i=\min(f_j+|(s_i-s_j)+(i-j-1)-L|^p)

可以发现这个方程有决策单调性

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

点击跳转

构造1 \times n的矩阵X

矩阵满足

\because A \times B = C

\therefore X \times A \times B = X \times C

53/66
Search
search