2017-Sp240-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
XIV Open Cup named after E.V. Pankratiev. GP of Baltics
== 流水账 ==
出门各自看题，cjb很快上机写B，然后发现G是随机平面最小生成树，cjb就开始上板子，结果疯狂wa1，发现输出位数不够，之后mle和re。sub推出了I，yzc上机'''I1y45'''。然后yzc接手写B，'''B2y67'''。sub上机写F，wa了之后发现做法错误了。cjb开始调参，最后'''G10y83'''。cjb和yzc随便讨论了下D，yzc上机写D wa了。sub想好做法，上机写F，tle了。之后sub上机'''F3y122'''，cjb和yzc找到了小corner case，但是数组开小又wa一发，'''D3y124'''。sub给出了牛逼猜想，yzc确认做法后上机写C，'''C1y153'''。之后sub写A的遗传，cjb和yzc讨论E，得到了几个做法，中途sub下来随口讲了一个做法，三人决定按着sub的思路结合随机去艹，然后'''E1y242'''。最后1h三个人一起艹A，甚至跑掉了前10个点，但是遗传并不是正路，顺利打出GG。
== 总结 ==
=== chenjb ===
又一次温习了随机平面图最小生成树，感觉还行？可以用分成网格的做法，也可以用kdt找最近p个点，也可以用kdt直接维护每个点最近点跑prim。A挺可惜的，被校赛的遗传题完全限制住了思维，另外今天罚时有点糟糕(主要因为我的G)，sub的C很不错。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：用欧拉回路找到经过所有状态恰好一次的置换(MIPT场上AC方式)，实际上是一个优美的构造@sub。

 * B：从下往上推出每个点可以取的所有颜色，随便取一种打印即可。

 * C：对于每个置换群，如果位置连续，逆序对数量为长度-1，就用交换来做，否则第二种。

 * D：按行拆开，判可行就连边，跑匹配，注意目标矩阵可能不合法。

 * E：取重心，随机取直线，然后删掉和这条直线相交的块，重复直到找到解。

 * F：答案是1/2(1-1/(2^num^)),num是矩阵的秩。

 * G：随机平面图最小生成树，将平面切割成网格图，然后对于每个点，扫周围的网格取最近的点，因为随机可以保证每个网格里点不会很多。用kd树的话，可以维护离每个点最近的k个点，建边跑kruskal；也可以直接动态维护最近的点，跑prim。正确做法是三角剖分，详见06年论文。'''题解：随机选一条直线，投影，按投影排序，按照这个顺序去找K近点。利用投影距离大于K近距离时不需要继续找剪枝。跑kruskal'''。

 * H：实现一个滚动类，里面储存骰子六个面的置换P6和C[1..6]代表每个面朝下多少次，滚动类实现拼接、乘上常数，和减法，分别从横和纵的方向考虑滚动，可以发现(A,B)可以转化为(B,A%B)的问题，用类似于exgcd求解即可。

 * I：推式子。

XIV Open Cup named after E.V. Pankratiev. GP of Baltics

流水账

出门各自看题，cjb很快上机写B，然后发现G是随机平面最小生成树，cjb就开始上板子，结果疯狂wa1，发现输出位数不够，之后mle和re。sub推出了I，yzc上机I1y45。然后yzc接手写B，B2y67。sub上机写F，wa了之后发现做法错误了。cjb开始调参，最后G10y83。cjb和yzc随便讨论了下D，yzc上机写D wa了。sub想好做法，上机写F，tle了。之后sub上机F3y122，cjb和yzc找到了小corner case，但是数组开小又wa一发，D3y124。sub给出了牛逼猜想，yzc确认做法后上机写C，C1y153。之后sub写A的遗传，cjb和yzc讨论E，得到了几个做法，中途sub下来随口讲了一个做法，三人决定按着sub的思路结合随机去艹，然后E1y242。最后1h三个人一起艹A，甚至跑掉了前10个点，但是遗传并不是正路，顺利打出GG。

总结

chenjb

又一次温习了随机平面图最小生成树，感觉还行？可以用分成网格的做法，也可以用kdt找最近p个点，也可以用kdt直接维护每个点最近点跑prim。A挺可惜的，被校赛的遗传题完全限制住了思维，另外今天罚时有点糟糕(主要因为我的G)，sub的C很不错。

oipotato

subconscious

题解

  • A：用欧拉回路找到经过所有状态恰好一次的置换(MIPT场上AC方式)，实际上是一个优美的构造@sub。
  • B：从下往上推出每个点可以取的所有颜色，随便取一种打印即可。
  • C：对于每个置换群，如果位置连续，逆序对数量为长度-1，就用交换来做，否则第二种。
  • D：按行拆开，判可行就连边，跑匹配，注意目标矩阵可能不合法。
  • E：取重心，随机取直线，然后删掉和这条直线相交的块，重复直到找到解。
  • F：答案是1/2(1-1/(2num)),num是矩阵的秩。
  • G：随机平面图最小生成树，将平面切割成网格图，然后对于每个点，扫周围的网格取最近的点，因为随机可以保证每个网格里点不会很多。用kd树的话，可以维护离每个点最近的k个点，建边跑kruskal；也可以直接动态维护最近的点，跑prim。正确做法是三角剖分，详见06年论文。题解：随机选一条直线，投影，按投影排序，按照这个顺序去找K近点。利用投影距离大于K近距离时不需要继续找剪枝。跑kruskal。
  • H：实现一个滚动类，里面储存骰子六个面的置换P6和C[1..6]代表每个面朝下多少次，滚动类实现拼接、乘上常数，和减法，分别从横和纵的方向考虑滚动，可以发现(A,B)可以转化为(B,A%B)的问题，用类似于exgcd求解即可。
  • I：推式子。
附加文件