zcmimi's blog
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

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

点击跳转

ABCDEF top: 0

\frac{a \times b + c}d -e = f

a \times b + c = de+df

我们可以先搜索a+b+c可能的结果和de+df可能的结果,然后合并即可

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

点击跳转

我们可以发现gcd(a_l,...,a_r)是单调递减的,而or(a_l,...,a_r)是单调递增的

所以我们可以两次二分来找到合法区间

至于求gcd(a_l,...,a_r),or(a_l,...,a_r)我们可以用rmq来求

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

点击跳转

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

点击跳转

f[i][k]为第i位,分成k

f[i][k] = MAX(f[j][k-1] + cnt[j+1][i])

这样的话肯定复杂度爆炸

既然看到MAX,那是不是可以用线段树优化呢?

记录每个点贡献的范围,更新时把这个范围的点++就可以了。

相信看代码可以看懂

其实我还加了滚动数组OwO

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

点击跳转

其实一点stl什么的都不用用到

区间交也就是[\max(l_i),\min(r_i)]

我们要求的就是每次删掉某个区间后其他区间的区间交

我们只需要记录最大l_i和次大l_i还有最小r_i和次小r_i

若当前要删掉的区间[l_i,r_i],l_i为最大L,那我们就取次大L

R同理

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

点击跳转

61/73
Search
search