Codeforces Round #627(Div.3) 解题报告

脑抽辣~~~~~~

比赛页面(1324)

A – Yet Another Tetris Problem

这题一开始看错题了啊啊啊啊啊

总的来说就是看所有 $a_i$ 的奇偶性相不相同就行……

B – Yet Another Palindrome Problem

做法比较多,$O(n)$ 或者 $O(n^2)$ 的都可以。我用的 $O(n^2)$,直接枚举每个数,看这个数出现在最左边或者最右边的位置,不相邻就行。

C – Frog Jumps

直接统计最长的连续L就行,答案就是长度+1

D – Pair of Topics

写了个离散化+BIT……cjj写了个Treap2333

E – Sleeping Schedule

一道比较裸的dp…

设 $dp(i,j)$ 表示当前到第 $i$ 个数,总和对 $h$ 取模为 $j$ 的最大值,然后转移就两种情况取最大值。当 $j$ 在 $[l,r]$ 内时 $dp(i,j)++$ 。

F – Maximum White Subtree

比较板的换根dp辣

我们将这棵树转成有根树,以 $1$ 为根

设 $f_u$ 表示 $u$ 从 $u$ 开始往下的 $u$ 的子树的最大值,$g_u$ 表示从 $u$ 往父亲走(不包括 $u$ )的最大值。

翻译一下就是把含 $u$ 的子树搞成两部分,一部分是 $u$ 的子树内(含 $u$ ),一部分是 $u$ 的子树外(不含 $u$ ),然后两次dfs,第一次统计 $f_u$,即 $f_u=\sum max(0,f_v)$ ,然后第二次dfs就统计 $g_u$,即 $g_u=max(f_{fa}+g_{fa}-max(f_u,0),0)$

最后答案就是 $f_u+g_u$。

 

发表评论