2017-Sp324-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

=== subconscious  ===

== 题解 == 

 * A：计算每个叉积的贡献，组合数，long double存得下。

 * B：显然完全一样可以；在不满足这个条件的前提下，如果a全是x，显然不可以，接下来观察终止状态，显然某行被敲过，还能做到两个x，所以对于终止态，任意一对同行或同列的x，都必须不能被敲，然后把它们锁定，对于那些只有行或者列其中之一被锁定的格子，如果是x的话，在未被锁定的格子中，有O的前提下，是能被变成O的，剩下的问题就是一个矩阵每行每列最多只有一个X，然后由于之前判断的限制，它不会是一个纯X的矩阵，所以一定有个O，我们砸一下这个位置，就可以接着把同行同列都砸一下，然后全局只剩一个X，显然可以把它移动到终止态最左边第一个X，终止态剩下的X直接敲出来即可。

 * C：

 * D：类欧几里得。

 * E：mask枚举行，预处理列之间单调关系，2^r^*rc dp统计即可。

 * F：

 * G：扫描线求出横线和纵线的交点数量，和4*n比较。

 * H：

 * I：考虑当前最大字母的联通块数量，如果能用当前操作数量解决，就贪心拿掉，递归到下一层；否则考虑只取k个块，维护k-max的和，同时剩下部分是两个后缀比较，sa或者hash都可以。注意考虑递归中k=0的情况，以及当开头是一段最大字母的时候，要合理地白嫖。

 * J：暴力。

 * K：

 * L：答案是n-1-最大匹配，第二行输出最大匹配非必需点，从不在匹配上的点走交错点就能把同侧的判掉，两边各做一次。

 * M：对于一个序列，如果左边一半和右边一半完全相同，答案是左边答案*2，如果左右两边完全没有交集，答案是两边相乘，否则是0。

流水账

chenjb

oipotato

subconscious

题解

• A：计算每个叉积的贡献，组合数，long double存得下。
• B：显然完全一样可以；在不满足这个条件的前提下，如果a全是x，显然不可以，接下来观察终止状态，显然某行被敲过，还能做到两个x，所以对于终止态，任意一对同行或同列的x，都必须不能被敲，然后把它们锁定，对于那些只有行或者列其中之一被锁定的格子，如果是x的话，在未被锁定的格子中，有O的前提下，是能被变成O的，剩下的问题就是一个矩阵每行每列最多只有一个X，然后由于之前判断的限制，它不会是一个纯X的矩阵，所以一定有个O，我们砸一下这个位置，就可以接着把同行同列都砸一下，然后全局只剩一个X，显然可以把它移动到终止态最左边第一个X，终止态剩下的X直接敲出来即可。
• C：
• D：类欧几里得。
• E：mask枚举行，预处理列之间单调关系，2^r*rc dp统计即可。
• F：
• G：扫描线求出横线和纵线的交点数量，和4*n比较。
• H：
• I：考虑当前最大字母的联通块数量，如果能用当前操作数量解决，就贪心拿掉，递归到下一层；否则考虑只取k个块，维护k-max的和，同时剩下部分是两个后缀比较，sa或者hash都可以。注意考虑递归中k=0的情况，以及当开头是一段最大字母的时候，要合理地白嫖。
• J：暴力。
• K：
• L：答案是n-1-最大匹配，第二行输出最大匹配非必需点，从不在匹配上的点走交错点就能把同侧的判掉，两边各做一次。
• M：对于一个序列，如果左边一半和右边一半完全相同，答案是左边答案*2，如果左右两边完全没有交集，答案是两边相乘，否则是0。