2017-Sp95-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场cjb读了H，用Treap秒了，决定上去敲个板子艹了，然后J有人过，sub上机'''J1y32'''。cjb敲完，yzc补充了一点就交了结果wa，怀疑人生，只好对拍，一直不知道怎么错的，怀疑起了板子。sub表示会了L，上机'''L2y111'''。最后终于发现H的问题了，板子有个小地方炸了，'''H2y136'''，惨失一血。cjb上机写后缀数组，然后和yzc搞了起来，sub孤独开题，cjb和yzc又wa了，最后sub加入，三个人开始乱搞，最后完场前4min过了，'''B3y296'''。
== 总结 ==
=== chenjb ===
gtm我的一血啊啊啊啊啊啊啊啊！！！！！！
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：sub

 * B：后缀数组排序后统计。

 * C：循环节为6，模拟即可。

 * D：sub

 * E：sub

 * F：首先要读懂题意，显然同一个强连通分量里的可以随意取，处理出ff[x][i]，在同一个强连通分量里取i个的最优值，也就是i-1个w1和1个w2，然后缩点在dag上跑dp，f[x][i+j]=ff[x][i]+f[p][j]。

 * G：对于只有一对group的情况直接贪心即可，否则枚举删除一条边及两端点，假如这个边的端点恰为一对group的组长，则显然图会不连通，反之则肯定连通。分完组之后暴力枚举所有人分进组里，对于每一组显然可以分类讨论后贪心分队伍。

 * H：可持久化Treap模板题。

 * I：观察可以发现，当有两个相邻的和平城市，肯定是平局，所以和平城市肯定是独立集。先预处理出每一个城市作为和平城市(周围都是战争城市)的sg值，对于每一个局面即判断把和平城市sg值异或起来即可。考虑把点集分成A和B，|A|*2^A^得到关于A的所有独立集及其对应的sg值sumsg，然后对于每一个合法的状态处理出其对应B的独立集S(只考虑A对B的关系)，对于S将f[sumsg][S]++。显然B的合法点集只能和S是子集关系才能产生贡献。紧接着用|B|*2^B^也处理出基于B的合法状态，用|B|*2^|B|^计算出总独立集个数，之后枚举所有B合法状态的父状态mask(取反后和枚举子集相同)，将对应sg值的f[sg][mask]加入后手答案中，这里是3^B^的，经过测试，取B=17时能够在0.8s内出解。

 * J：显然代价是每个逆序对的物品重量乘积的和，考虑f[mask]代表目前mask中的物品已被移到序列最左，状压dp即可。

 * K：sub

 * L：把同一变量视为点，每个or视为一条边，发现图上只有单链或单环，单链直接dp，单环枚举某一元素状态，dp两次即可。

 * M：十字链表。
== 补题 ==

流水账

开场cjb读了H，用Treap秒了，决定上去敲个板子艹了，然后J有人过，sub上机J1y32。cjb敲完，yzc补充了一点就交了结果wa，怀疑人生，只好对拍，一直不知道怎么错的，怀疑起了板子。sub表示会了L，上机L2y111。最后终于发现H的问题了，板子有个小地方炸了，H2y136，惨失一血。cjb上机写后缀数组，然后和yzc搞了起来，sub孤独开题，cjb和yzc又wa了，最后sub加入，三个人开始乱搞，最后完场前4min过了，B3y296。

总结

chenjb

gtm我的一血啊啊啊啊啊啊啊啊！！！！！！

oipotato

subconscious

题解

  • A：sub
  • B：后缀数组排序后统计。
  • C：循环节为6，模拟即可。
  • D：sub
  • E：sub
  • F：首先要读懂题意，显然同一个强连通分量里的可以随意取，处理出ff[x][i]，在同一个强连通分量里取i个的最优值，也就是i-1个w1和1个w2，然后缩点在dag上跑dp，f[x][i+j]=ff[x][i]+f[p][j]。
  • G：对于只有一对group的情况直接贪心即可，否则枚举删除一条边及两端点，假如这个边的端点恰为一对group的组长，则显然图会不连通，反之则肯定连通。分完组之后暴力枚举所有人分进组里，对于每一组显然可以分类讨论后贪心分队伍。
  • H：可持久化Treap模板题。
  • I：观察可以发现，当有两个相邻的和平城市，肯定是平局，所以和平城市肯定是独立集。先预处理出每一个城市作为和平城市(周围都是战争城市)的sg值，对于每一个局面即判断把和平城市sg值异或起来即可。考虑把点集分成A和B，|A|*2A得到关于A的所有独立集及其对应的sg值sumsg，然后对于每一个合法的状态处理出其对应B的独立集S(只考虑A对B的关系)，对于S将f[sumsg][S]++。显然B的合法点集只能和S是子集关系才能产生贡献。紧接着用|B|*2B也处理出基于B的合法状态，用|B|*2|B|计算出总独立集个数，之后枚举所有B合法状态的父状态mask(取反后和枚举子集相同)，将对应sg值的f[sg][mask]加入后手答案中，这里是3B的，经过测试，取B=17时能够在0.8s内出解。
  • J：显然代价是每个逆序对的物品重量乘积的和，考虑f[mask]代表目前mask中的物品已被移到序列最左，状压dp即可。
  • K：sub
  • L：把同一变量视为点，每个or视为一条边，发现图上只有单链或单环，单链直接dp，单环枚举某一元素状态，dp两次即可。
  • M：十字链表。

补题

附加文件