2020寒假高一集训——动态规划专题

背包问题

https://blog.csdn.net/yandaoqiusheng/article/details/84782655

https://blog.csdn.net/weixin_43693379/article/details/89432283

树形动归
https://blog.csdn.net/Dante__Alighieri/article/details/41826385

https://blog.csdn.net/qq_34777600/article/details/79699688

https://blog.csdn.net/weixin_30814223/article/details/99621708

区间dp
https://blog.csdn.net/qq_40772692/article/details/80183248

https://blog.csdn.net/y752742355/article/details/80051222

https://blog.csdn.net/qq_43472263/article/details/98337401

数位dp总结 之 从入门到模板
https://blog.csdn.net/wust_zzwh/article/details/52100392

https://blog.csdn.net/chenxiaoran666/article/details/82948835

https://www.cnblogs.com/Judge/p/9567971.html

状态压缩动态规划 状压DP
https://www.cnblogs.com/Tony-Double-Sky/p/9283254.html

https://blog.csdn.net/qq_38185591/article/details/90372432

简单的数学期望和概率DP

https://www.cnblogs.com/hua-dong/p/8166093.html

https://blog.csdn.net/myjs999/article/details/81022546

https://blog.csdn.net/wuxiaowu547/article/details/81835800

[模板] 斜率优化Dp详解
https://blog.csdn.net/Bill_Yang_2016/article/details/54667902
https://blog.bill.moe/1d1d-DP-optimization-notes/

2019CSP-J现场回放

T1 number

计算字符的数量就好了。。。。

T2 transfer

模拟,如果是地铁的话,就把它的时间和票价记下来,用数组记下。。。

如果是公交,那就把记下的时间和票价从数组的标记处循环,和公交比,用过了的票标记-1。。。。

如果地铁的票超时了就把标记往前挪。。。当时没有这一步的三行,然后时间超限40。。。

t3 souvenir

当时看到这个就????于是就刷了特例1和2。。。

正在推背包。。。

t4 work

想到是最短路径,但是只打出了30。。。。

总结的蒟蒻

NO.1

hh

NO.2

我我我我我一不小心把一些符合条件的票踢出队列了。

zz

蒟蒻数据毁我青春

这题单纯模拟就好了

没啥好说

NO.3

想不出=骗分=10分

背包是个什么玩意儿

NO.4

大意就是一个人要生产一个型号不为1的零件n,然后叫上传送带上的小伙伴一起生产零件n-1,然后传送带上的小伙伴叫上传送带上的小伙伴一起生产零件n-2......直到生产到原材料为止,然后问轩轩能不能抽空去抠jio蹦迪什么的

我大概是打了个找儿子函数?

挺短但超时了

听Father.汤 说要打堆还是什么鬼玩意儿

反正不会。。。

 

CSP-J 回 放

欢迎来到小学生作文。
一点流水账。

考前跟hjj去买了好多吃的 准备在考场里"野餐"

到了考场 发现右边没人 很宽敞很幸运!!

正题。

T1是字符串 草草打完的同时检查了好几遍。

T3不会做 用得分点t=1骗了10分

T4直接模拟 抱着0分的希望打 因为知道输送带是个环的情况不成立

最后还有25就很幸运

一看到T2就感jio是队列!!

两分钟后

内心OS:woc这不对啊

于是 队列 模拟√

好的 俺和省一 只差俩分钟

立个flag:明年没省一 名字倒着念!!

番外篇。

最后成绩100+35+10+25=170

在香港澳门云南贵州河北新疆等等好多好多好多(*N)省是省一

o俺想改户口!!

csp j 2019

t1

没啥好说的就计算字符的数量就好了

t2
模拟,如果是地铁的话,就把它的时间和票价记下来,用队列记下。

如果是公交,那就把记下的时间和票价公交做比较,用过了的票标记一下。

可以用一个队列,然后如果做地铁的票超时了可以出队。

当时只顾着比时间,忘记了时间没超过还可以再用,直接把票价比公交小的优惠卷给出队了

t3

当时看到这个就想到了背包,但不知道怎么推,于是就刷了样例。

t4

当时打了个宽搜,想到是最短路径,但想着打宽搜会保险一点。

2019东海J-csp欢乐游

110分

卑微

第一题

水题AC

第二题

爆零

主要是标记用过的优惠票出了问题,
我把用过票的钱调到了INF,结果出现了《无限优惠(白嫖记)》,优惠票直到时间过了都可以无限用,然而只要把钱调到-1就好了

第三题

卑微的10分

踩分失误

第四题

爆零

踩分失败

 

省一210
《假如给我题二AC》

CSP-J 2018

T1

简单的判断,八个字符,错了真的也是没有办法了

T2

一道可以暴力的模拟题,我也不知道为什么比赛的时候我会少打队列的一个判断,可能太紧张了。基于此应该想到可以利用优先队列(或类似)的数据结构来维护,每次坐公交,在所有价值大于本次票价的优惠券中优先使用过期时间最早的(不用就过期了!),价值最低的优惠券。一旦票过期了,就删掉,但是如果票只是价值不够,那可能后面还会有用,所以还要压回去。

T3

本题思路可以根据数据范围来想。这是一道动态规划题。
刚开始想到的是建立一张全图,但是后来发现节点数量不是N 而是N*T ,并且总价值也不一定只能走一条路。后来发现可以用动态规划解决,首先设f[x]是第x天能够赚到最多多少钱。那么f[1] = m。重点在于状态转移,f[ i ] 肯定是由f[1]到f[i-1]中推出来的,而且单独一个f[i-1]无法表示所有状态。所以假设当前处于状态j ,将第j 天物品的价格可以看作花费,第i天的物品价格看作价值,就做出了一个完全背包问题,背包容量是当天的金币数f[j] 。

if(f[k]<=f[ k-a[i-1][j] ] - a[i-1][j] + a[i][j])
f[k]=f[k-a[i-1][j]]-a[i-1][j]+a[i][j];

跟完全背包基本一样,就是将其改成了数组。考试的时候想不出来,根据那个数据范围,也可以扣个十分甚至更多。

T4

最短路径把。再判断一个有环无环,有环就跳出来,然后一直往前搜。

CSP-J题目总结(退役博客)

总感觉时间过得好快,初三比完赛信息马上就要告一段落了。

T1:水题。但我还是检查了好几遍文件读写(由于我最近模拟赛的文件读写连错)。

T2:一道要用队列优化的模拟,一开始还以为跟海港一样,还好后来的样例比较良心,让我这个不认真看题的发现漏洞。顺利的就过了大数据。

吸取了去年的经验,我T1T2花了1个多小时。

T3:考试的时候一眼看出DP,但是看到一堆变量就不想推了,索性连贪心都不打(那时候好像忘了有这东西了。。。)傻傻地扔了个空代码上去。。。

T4:我磕了2个小时的正解(显然学长发言都没听),找出了大部分规律——最短路+判断回环,但细节处理不好,民间数据也才30。。。

总结:T1T2AC了,吸取了去年的教训,但时间安排不妥当。省一也由于T3T4(乱打一通)不是很稳。