2019-team0x03-0018

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(Standings.png)]][[BR]][[Image(Submissions.png, 500px)]]
== 概述 ==
八月集训第十场(sds+lmh双打)

== 流水账 ==
开场各自看题。sds有一个H的idea上机写，WA了一发，sds叉掉自己的做法并提了新的一个，让lmh上机写，lmh也WA了一发，改了细节错误后'''H3y45'''。lmh验了一个E题idea但是WA了。sds和lmh讨论后上机写B，'''B1y83'''。随后sds验了一个E题idea也WA了。sds转头看I，和lmh讨论后上机写，由于小问题WA了一发，'''I2y128'''。lmh提出了一个复杂度不优秀的E题做法，sds用unordered_map优化后T了两发，sds写了个四模数hash，WA了两发后依然T，lmh优化了暴力枚举后就过了，'''E8y178'''。sds写放了很久的J，'''J2y191'''。两人看A看了3h+没有想法，lmh转头看F。sds试了A的暴力无果，lmh开出F，但是没有写完。

== 总结 ==
=== SidneySun ===
 * 好迷啊，这场打下来感觉基本功都有点没打好。是这个暑假都没睡好吗？感觉这个难度的题目打得还没我去年好。
 * Bitset的_Find_next(pos)函数不包含当前位置。
 * 事实上F这个前缀和也不是很难，补题大概用了四十分钟，场内应该一个小时能搞完。但是当时好像脑子已经疲倦了，不想去思考这个题目了。

=== lichangdongtw ===
=== ntwbvdbl_oe ===
 * 就算是签到题lmh也要仔细检查一遍代码
 * 如果lmh果断放弃他根本不会的A，说不定他就能把F写完(虽然写完也过不了)
 * (UPD:lmh赛场上写的F题算法是假的，因为lmh写了这么多年数据结构连前缀和转化都不会
 * E题优化的过程很艰辛，在这个过程中每一个idea都值得考虑
 * (感谢lcd在*天前的场外援助

== 题解 ==
 * A: Bitset._Find_nxt()
 * B: 对于每个连通块求最大生成树的补集
 * C:
 * D:
 * E: 打表发现答案为i%6或i%6+6，当且仅当i/6不能被i%6个n*(n+1)/2数列中的数之和表示，注意到3个该数列中的数之和可以表示所有自然数，当i%2=2时，对于k=i/2，枚举从k/2到k中所有该数列的数aj，用hash判断k-aj是否在数列里，复杂度O(\sqrt n * T)
 * F: 二维前缀和+树状数组
 * G:
 * H: 从前往后枚举长度为k的区间，若区间第一个值不是区间内最小值就排序
 * I: 设每个节点的权值为它到根的路径上最大的depthi+ai，以它为第二关键字(权值大优先)对内向树进行拓扑排序
 * J:

[wiki:2019-team0x03 Back]

概述

八月集训第十场(sds+lmh双打)

流水账

开场各自看题。sds有一个H的idea上机写，WA了一发，sds叉掉自己的做法并提了新的一个，让lmh上机写，lmh也WA了一发，改了细节错误后H3y45。lmh验了一个E题idea但是WA了。sds和lmh讨论后上机写B，B1y83。随后sds验了一个E题idea也WA了。sds转头看I，和lmh讨论后上机写，由于小问题WA了一发，I2y128。lmh提出了一个复杂度不优秀的E题做法，sds用unordered_map优化后T了两发，sds写了个四模数hash，WA了两发后依然T，lmh优化了暴力枚举后就过了，E8y178。sds写放了很久的J，J2y191。两人看A看了3h+没有想法，lmh转头看F。sds试了A的暴力无果，lmh开出F，但是没有写完。

总结

SidneySun

  • 好迷啊，这场打下来感觉基本功都有点没打好。是这个暑假都没睡好吗？感觉这个难度的题目打得还没我去年好。
  • Bitset的_Find_next(pos)函数不包含当前位置。
  • 事实上F这个前缀和也不是很难，补题大概用了四十分钟，场内应该一个小时能搞完。但是当时好像脑子已经疲倦了，不想去思考这个题目了。

lichangdongtw

ntwbvdbl_oe

  • 就算是签到题lmh也要仔细检查一遍代码
  • 如果lmh果断放弃他根本不会的A，说不定他就能把F写完(虽然写完也过不了)
  • (UPD:lmh赛场上写的F题算法是假的，因为lmh写了这么多年数据结构连前缀和转化都不会
  • E题优化的过程很艰辛，在这个过程中每一个idea都值得考虑
  • (感谢lcd在*天前的场外援助

题解

  • A: Bitset._Find_nxt()
  • B: 对于每个连通块求最大生成树的补集
  • C:
  • D:
  • E: 打表发现答案为i%6或i%6+6，当且仅当i/6不能被i%6个n*(n+1)/2数列中的数之和表示，注意到3个该数列中的数之和可以表示所有自然数，当i%2=2时，对于k=i/2，枚举从k/2到k中所有该数列的数aj，用hash判断k-aj是否在数列里，复杂度O(\sqrt n * T)
  • F: 二维前缀和+树状数组
  • G:
  • H: 从前往后枚举长度为k的区间，若区间第一个值不是区间内最小值就排序
  • I: 设每个节点的权值为它到根的路径上最大的depthi+ai，以它为第二关键字(权值大优先)对内向树进行拓扑排序
  • J:

Back

附加文件