突然听说要考试捏(
没有复习(
T1 是 P1434 [SHOI2002] 滑雪。草这不一眼......等下好像不太会写。一开始脑抽了。暴力建图给每个点跑spfa最长路。明显地,不是正解。直接跳掉了。
T2 是 P4170 [CQOI2007] 涂色。草这真的是一眼题。10min秒掉。
T3 是 CF161D Distance in Tree。一眼淀粉质,可惜不会写。首先想到计数dp。推了个扇贝式子。于是放弃。过了5min,发现这不一眼简单树形dp吗?设 \(dp_{i,j}\) 表示以 \(i\) 为根的子树内从 \(i\) 开始长度为 \(j\) 的路径数量。设当前节点为 \(x\),一个邻接点为 \(y\),贡献即为 \(\sum_{i=0}^{k-1} dp_{y,i} dp_{x,k-i-1}\)。对于一个 \(1 \le j \le k\),每次转移将 \(dp_{x,j}\) 加上 \(dp_{y,j-1}\) 即可。
T4 是 CF1073E Segment Sum。一眼计数dp。但又不会写。于是骗分。
T5 是 LibreOJ #6039「NAIPC2016」Jewel Thief,骗分。
最后看回T1。真的傻了。直接敲个记搜。应该能过。
预计得分:[70,100]+100+100+20+10=[300,330]
实际得分:100+100+100+20+0=320
暴力打错了。于是 班rk5 总rk19/59。
标签:骗分,le,23,2024,dp,100,小结,一眼 From: https://www.cnblogs.com/HAM-qwq/p/18320008