• 20220810NOI模拟赛--考后总结


    时间安排

    7:30–7:35 读题。T3 非常鬼畜。

    7:35–9:10 T1,对于同一棵树的情况可以 DP ,但当有两个棵树时 DP 就显得不那么优秀了。这种子树限制个数的和某道 PR 的 守卫 很像,想到可以建图解决限制问题。依照想法建图,调试。

    9:10–9:30 T2, 显然可以数位 DP ,问题在于如何快速求满足 abcd 的方案数,这玩意可以 DP ,但是复杂度很高没什么优化的空间,想到可能有更妙的方法。部分分可能可以用 DP 做,然而时间和空间都不允许,写个暴力滚粗。

    9:30–11:00 T3,莫名想到分开时间段,这样每个鸽子时一个函数,三分应该可以求其峰值,用拉格朗日插值可以求出有关点值,想法很模糊。看了几个部分分不知道有什么用, 对于 m = 2 m=2 m=2 可以按上述方法做,分段三分,细节较多调试半天。猜了几个拓展的结论不过都是假的。

    11:00–12:30 看T2,T3。

    回顾&反思

    T1: 场上算是过掉了。一个更优秀的建图是,对于每个子树选择点个数的限制,分别对应一个关键点和他控制的集合,由于树上子树与子树之间要么包含要么不交,那么求出有祖先关系的集合差,集合与集合之间不交,可以分别想对应普通点连边。

    T2:看出是数位 DP 了,瓶颈在于不能快速求限制了 01、10、00、11 子串个数的串数量。考虑将每一段的 0 或 1 缩成一个 0 或 1 ,那么 01、10 的个数只与这些缩后的 0、1 有关,往里加 1、0 等价于增加 11、00 ,那么就变成分配问题可以直接组合数求解。还是要多分析性质。
    总结一下见过的 01 串性质的题的常见套路 :1. 将连续的 0 或 1 缩成一个 0 或 1 ,然后考虑加其他 0 ,1 ;2. 将 0、1 的一些特征串看成一个整体,考虑不同整体的关系 ; 3. 考虑 0,1 的移动。

    T3: n < m n < m n<m 的部分分没拿到有些可惜,将 m 个点放在 n 条边 n 个点的简单回路上, n < m n < m n<m ,那么根据鸽巢原理,必有两点在一条边上。正解是拆分时间段,解函数方程。

  • 相关阅读:
    员工停薪留职协议(模板)
    Tomcat安装及配置(Windows环境)
    创建线程的4种方法
    类和对象(跑路人笔记)<完>
    Linux下基于ffmpeg音视频解码
    【供应链】全面分析供应链类型
    STM32G070RBT6基于Arduino框架GPIO外部中断
    halcon 车牌识别
    python刷算法的一些骚操作(一)
    Nmap列举远程机器开放的端口
  • 原文地址:https://blog.csdn.net/Cafarde/article/details/126275120