Codeforces Round #408 (Div. 2)做题记录

A. Buying A House

题意:略。

扫一遍好了。

B. Find The Bone

题意:略。

模拟一下好了。注意特判第一个是洞的情况。

C. Bank Hacking

题意:给出一个n个点的树,每次砍掉一个点可以让和他相连的点+1,孙子点+2(但是儿子节点必须存在)。问在这个过程中点权的最大值是多大。

发现最大值要么是一开始的最大值,最大值+1,最大值+2中的一个。所以枚举一下所有点好啦,在这个过程中用两个set维护一下好了。大概是\(O(nlogn)\)吧。。。

D. Police Stations

题意:给出一颗树让删除最多的边,使得所有点到关键点的距离都小于等于d。

考虑bfs,从所有的关键点开始bfs。因为题目保证有解,所以每个点都可以在d步内被关键点抵达。需要删除的边一定是某个关键点u可以通过一条边到v但是v已经被别的关键点访问过了,所以这个边需要删去。

不可以dfs!!!因为dfs走d步,是盲目性的,对于某个点来说关键点到他的路径不一定是最短的,那么会出现反例的,比如删边后发现有的点到达别的点距离大于d了。。。而bfs走的一定是最短路径,最短路径一定保证解不会更差。所以bfs才可以。。。

E. Exam Cheating

题意:现在有n个题目,你有p次机会看左右两个人,每次可以抄连续k道题目,告诉你每个人会的题目,最多可以做对多少道题目。\(n \leq 1000,p \leq 1000,k\leq min(50,n)\)

感觉和之前gym里一个抽牌的题目很像。考虑\(dp[i][j][k][l]\)代表现在做到第\(i\)题,已经用了\(j\)次机会,\(k\)表示在左边的人在这次机会中还剩多少道可以让你抄,\(l\)是指右边的。

那么对于对于第\(i\)道题目,如果我不使用新的机会,假如我现在还可以看左边的或者右边的题目也就是\(k>0\)或者\(l>0\),那么就是左边和右边人是否能答对就可以了。那么\(dp[i][j][k-1][l-1]=max(dp[i][j][k-1][l-1],dp[i-1][j][k][l]+((k&&a[i])||(l&&b[i]))\)。

假如我使用机会的话,就需要分左右两边考虑了。dp过程与上面的类似分析一下就可以了。。。

但是这样时间复杂度和空间复杂度都爆炸了。。。空间可以滚动数组,时间优化的话就是发现,每条线段上的n个点,每次覆盖k个点,一定可以通过\(ceil(n/k)\)次覆盖完全。所以时间复杂度为\(O(n*2*ceil(n/k)*k^{2})\)就可以了。

 

发表评论

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