转载请注明出处:http://tokitsukaze.live/

题目链接:https://codeforces.com/contest/1082


Solved:6/7

 

A.Vasya and Book

3种情况。

1.x->y

2.x->1->y

3.x->n->y

 

B.Vova and Trophies

维护两串G。注意中间不能有两个S。

 

C.Multi-Subject Competition

sum[i]表示每种科目选i个人的最大值。对于每种科目,从水平大的开始加,如果当前和是正的,就加入sum[]。

最后遍历一遍sum[],取max即可。

 

D.Maximum Diameter Graph

判断度的和小于树的度的和,就是NO。否则答案为非叶子节点数-1+min(叶子节点数,2)。

把叶子节点拿出来,非叶子节点连成一条链,然后叶子节点往上接即可。

 

E.Increasing Frequency

对于等于c的数的个数,做一个前缀和pre[]与后缀和suf[]。

mx[i]表示第i个数必选的前缀最大值。last[a[i]]表示上一次a[i]出现的位置。

mx[i]=max(pre[i-1],max[last[a[i]]])+1。

ans=max{mx[i]+suf[i+1]}。

 

G.Petya and Graph

最大权闭合子图裸题。

 

 

代码:

https://github.com/tokitsu-kaze/ACM-Solved-Problems/tree/master/Codeforces/Educational%20Codeforces%20Round%2055