【水题合集】2.18考试

向总的评测机有毒。。本来310的能给卡成210。。

1.题目一

求最长公共上升子序列

枚举a[i], b[o]

用f[o]表示以b[o]结尾能匹配的最大长度(要求此时b[o]=a[i])

那么f[o]=max(f[k])+1, k<o, b[k]<b[o]

枚举b[o]的时候记一下最大值即可将转移复杂度降到O(1)

2.题目二

一个略麻烦的贪心

从下往上贪心,每个点记录c[i]【离它最远的没有消防站的点的距离】和f[i]【最近的消防站的距离】

那么当f[i]+c[i]<=d时说明这个点子树上都没问题了

否则如果c[i]==d在该点设置消防站

【听说可能会爆栈写了个手写栈 但善良的出题人并没有卡栈【却被向总的机子卡T掉30分

3.题目三

树分治?。。

好吧%王队给我们讲了一下

还算简单吧 就是不断找重心删重心

【然后就是最后一个点要开无限栈/写BFS

4.题目四

裸的求树的直径

【听说DFS会爆栈于是写了个BFS 但善良的出题人并没有卡栈【却被向总的机子卡T掉70分

【DFS版】

【BFS版】

说点什么

2 评论 在 "【水题合集】2.18考试"

提醒
排序:   最新 | 最旧 | 得票最多
游客

农炸了

游客

%

wpDiscuz