DQS DQS

每日刷题记录(update:10.10)

in 人生相关,算法read (153) 文章转载请注明来源!

9.25

打了场CF #436div2
写崩了,各种奇妙的WA…幸亏过题数还能看。

CF864A

##CF864B

CF864C 贪心

车在坐标0和a之间往返k次,坐标f点有加油站(0<f<a),油箱上限b。每次加满油,问最少加多少次油。

情况:

考虑能否到加油站

考虑加油后能否由f点到另一头

若是最后一趟,考虑当前点走到另一头需不需要加油

若不是最后一趟,考虑走过去又走回来时能否走到加油站

贪心即可。

CF864D 贪心

给你一个值在[1,n]的长度为n的序列,问最少改多少个元素使得其成为一个排列,并保证修改次数最小的情况下使排列字典序最小。

取出所有未出现的数,个数即第一问答案。

从前往后遍历数组a,如果当前点x出现次数大于1,对于待填数字y,考虑:

若x>y,则直接修改。否则:

若x是第一次出现,则记录并跳过。

否则则修改。

CF864E DP

给出n个物品,第i个物品在di时刻销毁,拯救它需要花费ti时间,价值为pi。每个时刻只能救一个物品,问获得的最大价值,并给出一个拯救方案。

按di排序,然后01背包DP,开个和f数组平行的数组记录答案。

9.26

bzoj1003 最短路|DP

容易想到DP。我们不必记录每一天的路径(因为记不下来)。用val[i][j]表示i~j天走可走点的最短路。转移方程为f[i]=min{f[j]+val[j+1][i]*(i-j)+k)},即假设在第j+1天更换航线。若第i天及其以前所用航线和第j+1天及其以后相同,那么一定存在一个j'<j使得答案更优,正确性可得。

bzoj1005 树的Prufer序列|数学

给出n个点的度数要求(必须为某个度数或者无限制),问可以产生多少个满足限制的生成树。

树的prufer序列:每次找到一个编号最小的叶子节点,删除并将与其相邻的点加入序列,直到只剩两个点。

容易发现:度数为k的点出现了k-1次。

问题转化为:在长度为n-2的序列上,给定一些数的出现次数限制(必须为某个数或者无限制),求序列总数。

设有sum个点度数无限制,$m=n-2-\sum(d_i-1)​$则答案为:

$$\frac{(n-2)!}{\prod (d_i-1)! * m!}*sum^m$$

即将n-2个空中度数有限制的点填满,剩下的任意填。

C++写的话,为了避免高精除,可以对每个i暴力分解质因数,将左边除号去掉,然后做高精乘就行了。

所以python真好用。

bzoj1007 单调栈

bzoj1009 KMP|DP|矩乘

求一个长度为n的数字串中,不含有给定的长度为m的串作为子串的方案数。$n<=10^9,m<=20$

f[i][j]表示当前串第i为匹配到给定串第j位的方案数。考虑往后添加一个数来转移:

$$f[i][j]=\sum f[i-1][k]*a[k][j]$$

其中a[k][j]表示给定串的第k位添加一个数到第j位的方案数。显然这是kmp的转移问题。

观察递推式:若把i当做阶段的转移,则左边是一个列向量,右边是一个列向量乘一个方阵。并且方阵不变,要转移n次。

于是可以用矩阵优化。答案是最后的列向量各位相加。

9.27

bzoj1010 斜率优化DP

$a[i]=s[i]+i,l=l+1$,可得:$f_i=min{f_j+(a_i-a_j-l)^2}$

设j<k且j比k优,另$y_i=f_i+a_i^2+2la_i$则

$$\frac{y_j-y_k}{a_j-a_k}>2a_i$$

bzoj1012 st表

9.28

bzoj1013 gauss消元

9.29

bzoj1014 Splay+hash

md忘了放乘法标记了……

bzoj1053 dfs

约数个数是$\prod (k_i+1)$。$k_i$是唯一分解后素数的幂。

容易发现素数越小越好。因为前几个小素数连乘没几个就大于20亿了(10个),所以直接爆搜它们的指数,并且尽量选小的。

容易证明,素数的幂是单调不增的。

bzoj1087 状压DP

9.30~10.8 国庆集训

10.10

bzoj1036 树链剖分

bzoj1588 set

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

人生相关算法
最后由DQS修改于2017-10-10 19:52
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆