文章目录

吐槽

一天普及一天省选,弄到一起就出成了一套提高组试题。

Day1

原题大作战。
然而我一题都没做过。

总的来说 Day1 比去年好像容易点(不然我也不会留出一个多小时给每道题造数据对拍)。

T1

CCF 直接把 2013 的题原封不动搬到了 Day1T1 。

一开始想着递归,发现会被卡成 $O(n^2)$ ,
再想 DP 的时候简化一下式子就直接可以扫一遍出结果。

T2

bzoj 权限题。

如果一种货币能被其它若干货币代替,就扔掉。
设 f[i] 表示价值为 i 的货币是否会被代替,做一遍完全背包就好了。

T3

bzoj 权限题。

听说可以二分加贪心,不过我考场想的比较复杂 是二分答案再 DP ,DP 转移再套一层用链表维护的 DP

首先容易想到二分答案,二分一个答案 mid 后求最多可以有多少条赛道满足长度不小于 mid ,
若有不少于 m 条,则答案可行。

求赛道数量可以 DP ,设 f[u] 为 u 的子树中满足条件的赛道的数量,
g[u] 表示在满足 f[u] 最大的前提下 u 向下不经过赛道的最长路径长。

转移的时候先把 u 的儿子 v 的 f[v] 累加,同时将所有 g[v]+w 存起来(w 表示 u 到 v 的长度)。

对于 g[v]+w 大于等于 mid 的直接把 f[u]++ 然后扔掉,于是只需要考虑小于 mid 的 g[v]+w 的贡献。

两个不同的 g[v]+w 若大于等于 mid 就同样可以作为一条赛道让 f[u]++ ,先排序然后再次 DP 统计这样的赛道数量,
然后若所有的 g[v]+w 都有另外一个构成赛道, g[u]=0 ,否则 g[u] 等于剩下的最大的 g[v]+w 。

Day2

Day1 的比赛对我造成了巨大的影响,Day1 考完后信心爆棚, 以 AKIOI 的自信 走进 Day2 考场。

结果什么题都死磕正解,到最后连暴力都没打全。

看题,WTF?

看完 T1 我以为是个稠密无向图,想了好久感觉是要求一种特殊的生成树,感觉巨不可做。
顿时有点小慌,突然想到考前教练提醒要看完题,说不定后面的题反而简单。

嗯,有道理,直接翻到 T2 ,推了波结论认定是一道状压 DP,松了口气。

不急,再看 T3 ,哦,好像树形 DP ,但是 m 个询问难住了我。

于是认定 T2 比较容易,开始死磕 T2 ,打完状压后跑了遍 2,2 的样例,诶过了。
再跑一遍 3,3 ,输出 144 ,于是手推了 3,3 的样例发现还是 144 ,
意识到推的结论有误,瞬间慌的一批。
推了好久才发现了问题,得到正确的结论后发现对于新结论状压 DP 似乎变得不可行。

这个时候考试已经过了一个小时多了。慌。

换换思路吧,于是去做 T3 , 想了很久 DP 最后写了个平方复杂度的,
跑过了所有样例就没管了,没多少时间了,又回去看 T1 。

往回看了看 T1 里 m 的数据范围我才发现只有树和换套树两种情况。
那还求个鬼生成树,迅速打掉树的 60 部分分,n 看都没看只知道 $O(n)$ 稳了。
再去想换套树,感觉差不多,继续 $O(n)$做。

结果?一直死磕 T1 的 $O(n)$ 做法,直到最后考试结束都没写出来。

考试听别人说直接枚举删边 $O(n^2)$ 就可以过的时候我才意识到 n 只有 5000 ,整个人懵的。

结果 T1 还是 60′ ,T3 不晓得哪里炸掉了爆零,
有意思的是 T2 我错误的打法样例都没过在 ccf 的数据里水到了 45′ 。

分类: 竞赛

发表评论

电子邮件地址不会被公开。 必填项已用*标注