2017-Sp301-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
G非常经典吧？但是还是要记住这种经典结论(k数码问题的可行性和逆序对以及空白格子移动时的影响有关系)，不然可能会爆炸。这套题有点神秘，大力链剖分块可还行。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：每个数找到最小的和自己and为0的数，没有就和1连。

 * B：用dsu on tree得到一开始的答案，然后把修改转换成几个从根上出发的链的+1和-1，链剖后变成序列上区间加减，分块即可。

 * C：无解显然，n/k为偶数的时候头尾匹配即可，奇数时可以先取前3k配成相等，然后再把头尾并起来，注意特判n=1

 * D：

 * E：

 * F：吃树和不吃树的变化和哪些位置选择休息无关，因此不考虑吃树，只考虑休息，斜率优化dp，然后再贪心吃树即可。

 * G：考虑打扁成序列后的逆序对奇偶性，空格左右移动不改变，上下移动与边长奇偶有关，因为是4所以改变，因此判定逆序对和空格坐标y的奇偶性即可。

 * H：二分+主席树

 * I：

 * J：枚举n的1/5次方内的所有质数拿走，随后大力分类讨论，注意到可以判定出贡献为432的情况，其他贡献一定是1，开平方根和开三次根即可。

流水账

chenjb

G非常经典吧？但是还是要记住这种经典结论(k数码问题的可行性和逆序对以及空白格子移动时的影响有关系)，不然可能会爆炸。这套题有点神秘，大力链剖分块可还行。

oipotato

subconscious

题解

• A：每个数找到最小的和自己and为0的数，没有就和1连。
• B：用dsu on tree得到一开始的答案，然后把修改转换成几个从根上出发的链的+1和-1，链剖后变成序列上区间加减，分块即可。
• C：无解显然，n/k为偶数的时候头尾匹配即可，奇数时可以先取前3k配成相等，然后再把头尾并起来，注意特判n=1
• D：
• E：
• F：吃树和不吃树的变化和哪些位置选择休息无关，因此不考虑吃树，只考虑休息，斜率优化dp，然后再贪心吃树即可。
• G：考虑打扁成序列后的逆序对奇偶性，空格左右移动不改变，上下移动与边长奇偶有关，因为是4所以改变，因此判定逆序对和空格坐标y的奇偶性即可。
• H：二分+主席树
• I：
• J：枚举n的1/5次方内的所有质数拿走，随后大力分类讨论，注意到可以判定出贡献为432的情况，其他贡献一定是1，开平方根和开三次根即可。