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

A. Vladik and flights

trick:发现如果a和b的字符是相同的,那么答案就是0.否则的话答案就是1.因为我们总可以找到一个相邻的0和1,飞到那里去在花费一块钱交换即可。

B. Chloe and the sequence

发现一个数字如果是第一次加入的话,一定是在中间的位置。n才50,所以写了个丑陋的dfs,中间还爆long long 了。

C. Vladik and fractions

样例非常良心。,发现n<1e4,所以不用考虑超过1e9的无解情况,特判掉1.因为N=1会出现x,y,z相同的情况。

D. Chloe and pleasant prizes

题意:给出一个n个节点的树,节点权值有正有负,问是否可以选出两棵不相交的子树让他们权值和最大。

树形dp。因为节点权值有正有负,所以我们可以先求出所有节点包括自己在内的子树权值和。接下来我们只需要计算出每个节点的最大子树权值和,这个用dp[a]表示。计算过程中,对于父亲u来说,dp[u]=max(dp[v])。v是u的儿子。当我们每计算出一个dp[v]就和之前的dp[u]相加一下更新答案。因为这个时候的dp[v]是另一个u的儿子的dp值。这两个肯定是不相交的。最后要记得dp[u]和sum[u]比较一下,看是不是把整个u这棵子树都取可以让子树权值最大权值和更优。同时在更新答案的时候要判断一下当前的dp[u]是否是一个儿子的子树最大权值和,如果不是就先不更新,先把dp[u]更新了。

E. Vladik and cards

题意:给出n(n<=1000)张卡片,每张卡片都有1~8的一个数字。现在让你选出一个子序列满足:

(1)在这个子序列里,1-8各个数字的出现次数的差值不能超过1.比如假如你选出了1,1,2,2这样一个序列就不是满足条件的。

(2)这个子序列中相同数字应该是在连续一部分的,不能断开。比如:1,1,2,2,7,8,3,4,5,6。这样计算满足条件了。

现在让你选出这个子序列最长。

感谢Q聚教我这个题一个比官方题解好的思路~

首先我们可以二分每个数字出现的长度L,那么每个数字要不然在子序列中出现L次或者L+1次。L越大肯定子序列长度越大,这个推一推就出来了。

然后先预处理出来一个nxt数组,代表,从第i个位置开始j这个数字出现k次的位置。初始化为一个正无穷。

然后check的时候就状压我们已经决策了哪些个数。代表决策了mask这些数,并且这些数中有num个是长度为len+1的时候最靠左边的位置。这个位置是当前需要决策放什么数的。贪心的想,越靠左的话,子序列长度肯定会更优。dp[0][0]初始化为1.这是最初始的状态。

然后我们枚举当前放的是1~8中的哪个数,然后通过nct数组进行转移。

复杂度为:

 

发表评论

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