2017-Sp213-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
出门sub写了个假的F wa了，cjb写了个假的C wa了。之后各自开题，决定上一发G的决策单调性，然后过了。sub做I，cjb和yzc做C和F，sub上机也把I过了。cjb丢了F做法给sub，sub上机开始wa 22，cjb和yzc决定上复杂度不太对的C，tle了。最后C疯狂卡常，tle 20,36,42来回翻滚，评测机估计还有轮班，就是不能像现场队伍那样卡过去。sub最后改了改枚举顺序艹过了F，最后3题爆炸rk19，jsb他们3题rk18，咖啡鸡5题。
== 总结 ==
=== chenjb ===
感觉被活活坑死了啊？这什么jb题啊？这个C不是小学生都知道是错题吗？？？现场怎么爆过去的啊？？？
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：数据结构题@yzc

 * B：观察性质后六边形上模拟？@yzc

 * C：假题！f[i][j][k]表示从i出发，匹配到j，在trie树上节点k的最小步数，各种剪枝+卡常。题解n^4^做法显然是错的(acacb和aab,c)。

 * D：纳什均衡+单纯型@sub

 * E：楠楠的几何.......不明白

 * F：画出展开图后可以发现如果答案不在对端点上，则可以确定答案在某一个面上，进而对这个面展开起点后通过模拟退火求解(实际上三分套三分应该是错的)。

 * G：写出dp：f[i][j]=min(f[i-1][p]+w[i,p])，每一层都具有决策单调性，上一波糙快猛O(n^2^logn)即可。实际上根据题解，有opt[i-1,j]<=opt[i,j]<=opt[i,j+1]，可以做到O(n^2^)，注意这也是四边形不等式(当w满足时f也满足)的另一种形式。

 * H：几何@sub

 * I：答案是不可被因式分解的项数，经过一番推导可以求得是p^n^=Σ(i|n)i*ans[i]，莫比乌斯反演，模数是n*m，最后除n即可。

 * J：构造题@sub

流水账

出门sub写了个假的F wa了，cjb写了个假的C wa了。之后各自开题，决定上一发G的决策单调性，然后过了。sub做I，cjb和yzc做C和F，sub上机也把I过了。cjb丢了F做法给sub，sub上机开始wa 22，cjb和yzc决定上复杂度不太对的C，tle了。最后C疯狂卡常，tle 20,36,42来回翻滚，评测机估计还有轮班，就是不能像现场队伍那样卡过去。sub最后改了改枚举顺序艹过了F，最后3题爆炸rk19，jsb他们3题rk18，咖啡鸡5题。

总结

chenjb

感觉被活活坑死了啊？这什么jb题啊？这个C不是小学生都知道是错题吗？？？现场怎么爆过去的啊？？？

oipotato

subconscious

题解

  • A：数据结构题@yzc
  • B：观察性质后六边形上模拟？@yzc
  • C：假题！f[i][j][k]表示从i出发，匹配到j，在trie树上节点k的最小步数，各种剪枝+卡常。题解n4做法显然是错的(acacb和aab,c)。
  • D：纳什均衡+单纯型@sub
  • E：楠楠的几何.......不明白
  • F：画出展开图后可以发现如果答案不在对端点上，则可以确定答案在某一个面上，进而对这个面展开起点后通过模拟退火求解(实际上三分套三分应该是错的)。
  • G：写出dp：f[i][j]=min(f[i-1][p]+w[i,p])，每一层都具有决策单调性，上一波糙快猛O(n2logn)即可。实际上根据题解，有opt[i-1,j]<=opt[i,j]<=opt[i,j+1]，可以做到O(n2)，注意这也是四边形不等式(当w满足时f也满足)的另一种形式。
  • H：几何@sub
  • I：答案是不可被因式分解的项数，经过一番推导可以求得是pn=Σ(i|n)i*ans[i]，莫比乌斯反演，模数是n*m，最后除n即可。
  • J：构造题@sub
附加文件