zcmimi's blog

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

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

点击跳转

LG 1415 拆分数列加强版

复杂度要求减少

我们先来考虑dp方式

f_i = max(j)|(num(f[j],j) < num(j+1,i))

我们把填表式换成刷表式

现在不考虑0:

如果num(f[i],i)<num(i+1,i+1+i-f[i])

那么f(x) = max(f(x),i+1) (x\in[i+1+i-f[i],n])

否则f(x) = max(f(x),i+1) (x\in[i+1+i-f[i]+1,n])

(因为长度+1肯定满足)

于是我们可以令开一个数组来记录或者用线段树优化dp

现在考虑那个毒瘤的0:

要从i推到j

到达i时最小的数字应该是num(f[i],i)

这时候num(f[i],i)可能有前导0

num(i+1,i+1+i-f[i])也可能有前导0

我们用R0[i]表示从i开始有连续几个0

比较的时候就可以排除0的干扰

枚举的时候可以用hash+二分求出最大公共前缀优化到log n

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

点击跳转

原本打算写dp的,但是仔细观察一下,只要第一个点确定了,后面的点也确定了

答案只有可能是0,1,2中的一种

(可能是我扫雷玩太少了)

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

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j} \\ t_i+s\le \frac{f_k-f_j}{w_k-w_j}

维护个下凸壳就可以了

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

点击跳转

还是lct维护最小生成树

先按a变排序,然后b边的处理类似WC2006水管局长

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

点击跳转

f[0] = 0 

i指状态压缩后的二进制数)f[i]=\sum f[i']) 

lowbit可以很快地获取一个数在二进制下第一个1在哪 

一直lowbit和异或就可以把所有1找到 

因为这道题卡常,所以只能用lowbit

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

点击跳转

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

点击跳转

我们设学生1的债务为x

可以根据连边来计算出其他学生债务的表达式(ax+b)

如果出现矛盾,立即输出impossible并输出

最后可以求出x,并推出所有学生的债务

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

点击跳转

f_x表示在x放置且x的子树都被覆盖最少多少

g_x表示不在x放置且x的子树都被覆盖最少多少(x可以不被覆盖)

s_x表示在x放置且x的子树都被覆盖最少多少(x一定被覆盖)

f_u = \sum min(f_v,s_v,g_v)

g_u = \sum min(f_v,s_v)

s_u = (\sum \min(f_v,s_v)) - max(0,min(f_v-s_v))

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

点击跳转

同树网的核

41/65
Search
search