2017-Sp138-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，sub上机写G，然后cjb和yzc讨论出F，'''F1y21'''。之后sub '''D1y31'''，yzc上机'''L1y48'''，yzc和sub讨论之前写得不太行的A，cjb上机写M，之后'''A1y95'''。cjb把H的做法给了yzc，yzc上机'''H2y117'''。之后sub上机C获得tle，cjb和yzc搞了M获得tle，卡了卡常数微调了一下'''M3y158'''，sub换了更稳妥的做法'''C1y198'''。然后大家回头看G，发现bug，'''G2y221'''，最后sub''' I1y257'''。之后yzc尝试写大数据结构J，没写完。最后终榜rk8。
== 总结 ==
=== chenjb ===
感觉手速慢， 上M有点犹豫，A和M都在卡常边缘，感觉现场就过不了啦....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：从后往前扫做单调队列。

 * B：cjb

 * C：把无向边看成单独的项，一共有45项，维护答案多项式，每次是a+=b或者a-=b的形式。

 * D：除了1 2 3 4 6以外都是。

 * E：yzc

 * F：异或和=0是平局，否则先手胜。

 * G：跑凸包，重点只留最小值，贡献按单调升序留即可。

 * H：考虑有根树，每个点x要在父亲之后才能取，先不考虑先后顺序，塞进堆里，第一个如果可以取就取，否则把其和父亲合并。

 * I：枚举可以发现状态只有1471种，f[i][j][k]表示末尾3个gcd是i，2个是j，1个是k，加些小剪枝。

 * J：考虑分治，对于那些跨过分治点的区间，切成两段，则每一段变成了对应区间的前缀或后缀信息维护，直接sort后用线段树维护即可。

 * K：sub

 * L：模拟。

 * M：考虑按100分块，维护邻接矩阵的p次方，预处理出100、200...次方的矩阵A[i]，然后再预处理出1..100次方的矩阵B[i]，把B[i]和floyd结果合并得到新B[i]，之后每个询问枚举中间点把A和B合并就好。

流水账

出门各自看题，sub上机写G，然后cjb和yzc讨论出F，F1y21。之后sub D1y31，yzc上机L1y48，yzc和sub讨论之前写得不太行的A，cjb上机写M，之后A1y95。cjb把H的做法给了yzc，yzc上机H2y117。之后sub上机C获得tle，cjb和yzc搞了M获得tle，卡了卡常数微调了一下M3y158，sub换了更稳妥的做法C1y198。然后大家回头看G，发现bug，G2y221，最后sub I1y257。之后yzc尝试写大数据结构J，没写完。最后终榜rk8。

总结

chenjb

感觉手速慢， 上M有点犹豫，A和M都在卡常边缘，感觉现场就过不了啦....

oipotato

subconscious

题解

  • A：从后往前扫做单调队列。
  • B：cjb
  • C：把无向边看成单独的项，一共有45项，维护答案多项式，每次是a+=b或者a-=b的形式。
  • D：除了1 2 3 4 6以外都是。
  • E：yzc
  • F：异或和=0是平局，否则先手胜。
  • G：跑凸包，重点只留最小值，贡献按单调升序留即可。
  • H：考虑有根树，每个点x要在父亲之后才能取，先不考虑先后顺序，塞进堆里，第一个如果可以取就取，否则把其和父亲合并。
  • I：枚举可以发现状态只有1471种，f[i][j][k]表示末尾3个gcd是i，2个是j，1个是k，加些小剪枝。
  • J：考虑分治，对于那些跨过分治点的区间，切成两段，则每一段变成了对应区间的前缀或后缀信息维护，直接sort后用线段树维护即可。
  • K：sub
  • L：模拟。
  • M：考虑按100分块，维护邻接矩阵的p次方，预处理出100、200...次方的矩阵A[i]，然后再预处理出1..100次方的矩阵B[i]，把B[i]和floyd结果合并得到新B[i]，之后每个询问枚举中间点把A和B合并就好。
附加文件