2017-Sp330-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

=== subconscious  ===

== 题解 == 

 * A：构造1个3位0,1,2映射到2个2位10,01,00，FWT后统计即可。注意内存。普通分治可能也可以？

 * B：

 * C：

 * D：矩乘得到每个b对应初始向量，高斯消元即可。

 * E：显然平分，除二上取整。

 * F：对于一条非树边，如果边权大于他覆盖这部分的最小值，设这条边两端为x，y，所有点到x，y至多一个点不经过最小值那条边，于是满足到其中一个点不经过最小值的就可以删掉。将两种边分别排序，启发式合并，维护树边联通块的合法点。在适当的时候由非树边将不合法点删掉。

 * G：

 * H：md=sigma1_m{|i-d|}，二分答案解方程。

 * I：

 * J：对于一个确定的棋盘，转化为每一列前m-1个字符对应点向后m-1个字符对应点连边，流量平衡，答案是入度阶乘乘积，哈希维护。由于每行只有一个问号，枚举第一行的问号填什么，就能推断出每行的问号，同时维护出每列的两个哈希值。

 * K：第一个值减第二个值。注意取模。

流水账

chenjb

oipotato

subconscious

题解

• A：构造1个3位0,1,2映射到2个2位10,01,00，FWT后统计即可。注意内存。普通分治可能也可以？
• B：
• C：
• D：矩乘得到每个b对应初始向量，高斯消元即可。
• E：显然平分，除二上取整。
• F：对于一条非树边，如果边权大于他覆盖这部分的最小值，设这条边两端为x，y，所有点到x，y至多一个点不经过最小值那条边，于是满足到其中一个点不经过最小值的就可以删掉。将两种边分别排序，启发式合并，维护树边联通块的合法点。在适当的时候由非树边将不合法点删掉。
• G：
• H：md=sigma1_m{|i-d|}，二分答案解方程。
• I：
• J：对于一个确定的棋盘，转化为每一列前m-1个字符对应点向后m-1个字符对应点连边，流量平衡，答案是入度阶乘乘积，哈希维护。由于每行只有一个问号，枚举第一行的问号填什么，就能推断出每行的问号，同时维护出每列的两个哈希值。
• K：第一个值减第二个值。注意取模。