2017-Sp244-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
Western Subregional 2013
== 流水账 ==
出门顺利地'''A1y14'''，'''K1y17'''，'''H1y53'''，'''E1y66'''，'''D1y67'''，'''J1y73'''，之后卡了一下sub上机'''F2y118'''，cjb搞了个错误题意I wa了，之后fix了之后感觉很稳，sub给出构造，'''B1y140'''，sub上机'''L1y161'''。之后yzc上机搞I，wa了之后终于发现结论错了，之后cjb和sub写G没写出来，一直wa就没了。
=== chenjb ===
今天被anti-nim搞了之后就失去战意了，甚至都没有和yzc讲G，不然这个G理应过的，三个人感觉比较疲惫了。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：树状数组维护bitset。

 * B：每次折半然后连满边，继续分治直到只剩1个点。

 * C：分段，每段内考虑每个人的答案，是一个多项式除上每个人自己的那份贡献，这个可以用分治在O(n^2^logn)解决，总复杂度是O(n^3^logn)，注意要改成全正数的加法，这样才能保证精度。

 * D：读入第一个点输出。

 * E：暴力枚举即可。

 * F：逐位确定dp，多重背包。

 * G：从后往前确定，可以证明当前位置如果变成恰好比他大的不行，再变大一些也不行，还可以证明，当前位置的下个位置如果能填出位置，那么后面都行，不然不行，从后往前枚举直到找到可以变大的位置，剩下的数字在往下走的时候取最小值，在往上走的时候如果是最后一个数字就取最小值，否则取次小值，注意特判更改头的时候，注意特判前两个数字。

 * H：先取所有人，每次把非法的删掉。

 * I：一个节点的sg值是所有儿子的sg值的异或和+1，所有独立子树的每一个子树都是一个游戏，根据anti-nim的结论：如果属于异或和为0，所有数字都小于等于1(其实本题没有等于0的情况)，显然做不到异或和依旧为0的情况下出现一个大于1的数字，所以考虑依旧保持所有数字<=1，但是让异或和不为0，对每个游戏递归寻找是否存在这样的边；如果是异或和不为0，有数字大于1，一种方法是如果存在唯一的大于1的数字，令它小于等于1，并且依旧保持异或和不为0，或者找到一个游戏，使得异或和为0，同时满足这个游戏变成一个大于1的数，或者原来大于1的数不为1，或者这个数不是原来大于1的那个数。

 * J：最小割，注意到从左下往右上dp即可。

 * K：排序，对应相减取绝对值输出。

 * L：枚举8个方向写计算。

Western Subregional 2013

流水账

出门顺利地A1y14，K1y17，H1y53，E1y66，D1y67，J1y73，之后卡了一下sub上机F2y118，cjb搞了个错误题意I wa了，之后fix了之后感觉很稳，sub给出构造，B1y140，sub上机L1y161。之后yzc上机搞I，wa了之后终于发现结论错了，之后cjb和sub写G没写出来，一直wa就没了。

chenjb

今天被anti-nim搞了之后就失去战意了，甚至都没有和yzc讲G，不然这个G理应过的，三个人感觉比较疲惫了。

oipotato

subconscious

题解

  • A：树状数组维护bitset。
  • B：每次折半然后连满边，继续分治直到只剩1个点。
  • C：分段，每段内考虑每个人的答案，是一个多项式除上每个人自己的那份贡献，这个可以用分治在O(n2logn)解决，总复杂度是O(n3logn)，注意要改成全正数的加法，这样才能保证精度。
  • D：读入第一个点输出。
  • E：暴力枚举即可。
  • F：逐位确定dp，多重背包。
  • G：从后往前确定，可以证明当前位置如果变成恰好比他大的不行，再变大一些也不行，还可以证明，当前位置的下个位置如果能填出位置，那么后面都行，不然不行，从后往前枚举直到找到可以变大的位置，剩下的数字在往下走的时候取最小值，在往上走的时候如果是最后一个数字就取最小值，否则取次小值，注意特判更改头的时候，注意特判前两个数字。
  • H：先取所有人，每次把非法的删掉。
  • I：一个节点的sg值是所有儿子的sg值的异或和+1，所有独立子树的每一个子树都是一个游戏，根据anti-nim的结论：如果属于异或和为0，所有数字都小于等于1(其实本题没有等于0的情况)，显然做不到异或和依旧为0的情况下出现一个大于1的数字，所以考虑依旧保持所有数字<=1，但是让异或和不为0，对每个游戏递归寻找是否存在这样的边；如果是异或和不为0，有数字大于1，一种方法是如果存在唯一的大于1的数字，令它小于等于1，并且依旧保持异或和不为0，或者找到一个游戏，使得异或和为0，同时满足这个游戏变成一个大于1的数，或者原来大于1的数不为1，或者这个数不是原来大于1的那个数。
  • J：最小割，注意到从左下往右上dp即可。
  • K：排序，对应相减取绝对值输出。
  • L：枚举8个方向写计算。
附加文件