全部评论 9

  • T1的话,我的思路是进行dp,dp[i]的定义为前 i 个数的方案数,再维护一个邻接表l表示这一位可合并的区间左下标。转移: dpi←∑i=1ndp[l[i][j]−1]dp_i \leftarrow \sum _ {i = 1}^{n} dp[l[i][j] - 1] , 至于去重......(本人刚过七级,这着实有点难)这里应该是一个渐进时间复杂度O(n log n)O(n\ log\ n)

    T2我感觉要先建一个二分搜索树,再对比一下原本的满二叉树,用贪心的方法求出在修改以前的总值(对于每一个点,找到他的父节点,与他父节点的子树交换)。
    对于每一次修改,我们先将两点直接交换,对比交换的两点在二分搜索树可能出现的情况:
    1)交换之后两个点都到了应该到的地方,此时总值-2 ;
    2)交换之后有一个点到了应该到的地方,另一个点任然不匹配,此时总值-1;
    3)交换之后有一个点到了应该到的地方,另一个点原本匹配而现在不匹配,此时总值不变。
    4)交换之后两个点都由匹配变成不匹配,此时总值+2 ;
    5)交换之后有一个值原本匹配而现在不匹配,另一个值任然不匹配,此时总值+1 。
    这样的话时间复杂度应该是O(n \log \n \+ \q) .
    我还只是一个刚过七级的小学生,恳求大佬给点意见

    2天前 来自 浙江

    1
    • dsa

      2天前 来自 广东

      0
    • dsa,但是 T2 是树形 dp。我看过题目讲解了但还是 thx

      2天前 来自 湖北

      0
  • 2

    2天前 来自 浙江

    0
  • 这妈的能发吗

    3天前 来自 湖北

    0
  • 我直接把题给你偷走了(

    3天前 来自 湖北

    0
  • T1的口胡(
    对于每个点位 kk维护所有以 kk 结尾的可合并后缀,用这些后缀的起始位置 ii 做转移、
    转移推了一个 dpk←dpk+dpidp_k \leftarrow dp_k + dp_i、

    3天前 来自 上海

    0
  • 使唤了一下 AI,AI 钦定是蓝紫,我认为 AI 做法是青蓝

    3天前 来自 广东

    0
  • 鉴赏了一下T1发现是DP,然后不会了、

    3天前 来自 上海

    0
  • T1就放我不会的

    3天前 来自 广东

    0
  • d

    3天前 来自 湖北

    0

热门讨论