2017-Sp337-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：那个数字一定是所有数字积的根号，记得特判0。

 * B：设撞击时间t，可得方向固定且加速度可解，接下来算出t的取值范围求导，讨论可得，注意特判直接停下来。

 * C：只有10000张不同的图，大力统计每个点是雷的情况，每次选可能性最小的去问，然后通过得到的结果把不合法的图踢掉。

 * D：把n放在k,i,j的位置各relax n^2^次，然后大力做3次就过了。

 * E：枚举谁在第一个独立集，他相邻的所有人只能放在他或者他下一个独立集，显然放在下一个更优，每个联通块找到能扩展次数最多的加起来即可，用bitset优化。

 * F：考虑4种边：empty[i]到empty[j]；empty[i]到empty[j](在i加油)；full[i]到full[j](在j加油)；full[i]到empty[j]，通过中间点k加油。floyd即可。

 * G：相当于求抠掉武器的点是否有主角和怪物连通，由于每个点只有4条边，转化为删边、加边、维护两点连通性，离线线段树，把每一组删边加边看成一个时刻的操作，就可以使线段树规模降到3T，可能需要手写链表卡空间。

 * H：

 * I：

 * J：空串是奇数，加一个字母之后变偶数，直到下一次再遇到这个字母之前都不会变，下次遇到之后变成空串。对每个串，枚举每一种状态经过这个串后变为哪个状态，f[mask][i]表示mask这些点已经考虑进来，现在状态是i的方案数，由于空串是奇数，所以最后将不为空串的那些f值加起来就是答案。

 * K：往左走的按需求放左边，往右走的按需求放右边。

 * L：

流水账

chenjb

oipotato

subconscious

题解

A：那个数字一定是所有数字积的根号，记得特判0。
B：设撞击时间t，可得方向固定且加速度可解，接下来算出t的取值范围求导，讨论可得，注意特判直接停下来。
C：只有10000张不同的图，大力统计每个点是雷的情况，每次选可能性最小的去问，然后通过得到的结果把不合法的图踢掉。
D：把n放在k,i,j的位置各relax n²次，然后大力做3次就过了。
E：枚举谁在第一个独立集，他相邻的所有人只能放在他或者他下一个独立集，显然放在下一个更优，每个联通块找到能扩展次数最多的加起来即可，用bitset优化。
F：考虑4种边：empty[i]到empty[j]；empty[i]到empty[j](在i加油)；full[i]到full[j](在j加油)；full[i]到empty[j]，通过中间点k加油。floyd即可。
G：相当于求抠掉武器的点是否有主角和怪物连通，由于每个点只有4条边，转化为删边、加边、维护两点连通性，离线线段树，把每一组删边加边看成一个时刻的操作，就可以使线段树规模降到3T，可能需要手写链表卡空间。
H：
I：
J：空串是奇数，加一个字母之后变偶数，直到下一次再遇到这个字母之前都不会变，下次遇到之后变成空串。对每个串，枚举每一种状态经过这个串后变为哪个状态，f[mask][i]表示mask这些点已经考虑进来，现在状态是i的方案数，由于空串是奇数，所以最后将不为空串的那些f值加起来就是答案。
K：往左走的按需求放左边，往右走的按需求放右边。
L：