Codeforces Round #331 (Div. 2)

A

8min -1

日常WA签到题。看清数据范围啊。

B

7min

(ans=sum |a_i-a_{i-1}|)

C

33min

  • 对于每个(y-x=w)的条件,建一个堆。从大到小,依次分配编号,每次取出(w)对应的堆顶元素。
  • 接下来我们check得到的解是否合法。解合法只需任何点,左下方所有点编号的最大值,都小于这个点的编号。
  • 然后对所有点先按(x),再按(y)排序,遍历数组的同时,按(y)将点的编号,插入BIT。用这个BIT维护前缀最大值即可。

D

109min

  • (dp[l][r][0/1][0/1])表示,区间([l,r]),第(l-1)棵树倒的方向,第(r+1)棵树,倒的方向。对答案的贡献。
  • 考虑转移。分为四种情况
    • 左边的树,向左倒。
    • 左边的树,向右倒。
    • 右边的树,向左倒。
    • 右边的树,向右倒。

emmmm一开始我为什么会觉得区间dp复杂度是(O(N^3))的吖!
然后老想着统计每棵树对答案的贡献,拿期望的可加性来做。耽误了不少时间。

E

YY了一下,很可做。懒死了,不想写。

  • 建图后,我们会得到一个基环森林。
  • 我们尝试着拿每一颗基环树去匹配它给的字符串。我们将基环树边反向,然后将需要匹配的字符串倒着匹配。
  • 先在环上狂转,能转掉几个字符是几个,基环树去掉环后是一片森林。我们在每棵树上继续匹配即可。

有空补补吧。基环树的题,细节都比较多的啊!

稍微总结一下。

  • 看到n个点,n条边,出于本能也该想到基环树啦!
  • 看到n个点,n-1条边,出于本能也该想到树啦!

基环树有个很好玩的性质,边和点可以完全一一匹配CF1027F

比如这个问题,每条边可以看做一场考试,每个点可以看出,一天。
如果是个基环树的话,那主角就得到施展了。

然后,基环树经常是先在环上玩,在环上完玩了,去树上玩。

原文地址:https://www.cnblogs.com/RUSH-D-CAT/p/9737426.html