zcmimi's blog

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

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

点击跳转

同树网的核

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

点击跳转

第一问:

数列中肯定有些是合法的,有些是不合法的

如果a_i-a_j < j-i就无法同时保留两者

那么a_i-a_j \ge j-i

所以a_i-i < a_j-j

b_i = a_i -i

b的最长不下降子序列长度就是最多能保留个数

第二问:

a变成严格单调上升等同于把b变成单调不降

唉,实在不会

https://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411

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

点击跳转

m \le 5000

数据这么小,直接把边排序一下,然后暴力枚举,用kruskal就可以了

42/66
Search
search