请选择 进入手机版 | 继续访问电脑版

2021.01.01【NOI2021冬令营】模拟赛 比赛总结

[复制链接]
唐少琼 发表于 2021-1-3 12:13:47 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
总结

第一次在纪中跨年。
本日早上原来计划                               7                      :                      25                          7:25               7:25 才起来的,闹钟都调好了。效果昨晚睡觉前没有关宿舍的灯的开关,                               6                      :                      30                          6:30               6:30 直接就被 灯光+铃声+晨歌 弄醒了……
到机房后切了昨晚的T1,然后做角逐。
T1

一开始看错题了,以为是求                               A                          A               A 有多少个子串可以由                               B                          B               B 的某个前缀颠末若干使用得到。以为可以                               O                               (                         ∣                         A                                   ∣                            2                                  )                                  O\left(|A|^2\right)               O(∣A∣2)                               D                      P                          DP               DP 已往。设                                        f                                   i                            ,                            j                                           f_{i,j}               fi,j​ 体现                               A                          A               A 的                               [                      i                      ,                      j                      ]                          [i,j]               [i,j] 能否由                               B                          B               B 的前                               j                      −                      i                      +                      1                          j-i+1               j−i+1 个字符使用得到。
效果打完之后连样例都过不了……手玩一下才发现看错题了。
事实上,要盘算的是                               A                          A               A 有多少个子串的某一个 子序列 可以由                               B                          B               B 整个串使用得到。
只要在上面的                               D                      P                          DP               DP 上略加修改就好了,设                                        f                                   i                            ,                            j                            ,                            k                                           f_{i,j,k}               fi,j,k​ 体现                               A                          A               A 的                               [                      i                      ,                      j                      ]                          [i,j]               [i,j] 能否由                               B                          B               B 的前                               k                          k               k 个字符使用得到。然后优化……不能优化吧。
时间复杂度为                               O                               (                         ∣                         A                                   ∣                            2                                  ∣                         B                         ∣                         )                                  O\left(|A|^2|B|\right)               O(∣A∣2∣B∣) ,嗯,估计能拿到                               60                          60               60 分的好效果。
T2

看起来不可做。估计是希奇的 计数 + 数论 吧。
T3

弄了10分钟左右才搞明白 外向树 是什么意思:由有向边构成的,所有边的方向都是从父亲到儿子的有根树。
很容易发现最佳的遍历肯定是根据 dfs序 由小到大跑的,因此设                                        f                                   i                            ,                            j                            ,                            k                                           f_{i,j,k}               fi,j,k​ 以                               i                          i               i 为根的子树中最多同时使用                               j                          j               j 个分身,                               i                          i               i 的祖先中离                               i                          i               i 最近的分身点是                               k                          k               k 的最小时间。
转移有两种:                               i                          i               i 这个点是否成为新的分身。还要思量当走到儿子后不再上来时大概会删除一些上面的分身。
科场上没有调出来,痛失                               60                          60               60 分!
  题解

T1

实在是可以优化的……
直接发现如果                               D                      P                          DP               DP 数组只存                               0                      /                      1                          0/1               0/1 的话就太浪费了,因此把                               k                          k               k 那一维酿成                               D                      P                          DP               DP 数组的数值。
设                                        f                                   i                            ,                            j                                           f_{i,j}               fi,j​ 体现                               A                          A               A 的                               [                      i                      ,                      j                      ]                          [i,j]               [i,j] 最多能由                               B                          B               B 的前多少个字符使用得到。
时间复杂度                               O                               (                         ∣                         A                                   ∣                            2                                  T                         )                                  O\left(|A|^2 T\right)               O(∣A∣2T) ,因为另有一个                                        1                         2                                  \frac{1}{2}               21​ 的常数,因此就                               900                          900               900 多毫秒卡已往了。

来源:https://blog.csdn.net/huangzihaoal/article/details/112061776
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )