解题报告

总结

连通性判断

分析

题目很长，但是意思很简单。首先要做 data consistancy 的检查。

1. 如果 a 在 b 前面，但是 b 不在 a 后面，那么就是有问题的数据
2. 如果不连通，数据也是有问题的

数据没有问题之后，一次 DFS 就可以找到各个方向上的最长长度，比如设起始点的坐标为 (0,0,0,0)。

总结

从最后一位开始判断

分析

1. 如果$n$是偶数，那么最后一位一定是0。
2. 如果是奇数，那么最后一位一定是1。如果对应的比特位为正，那么$n \leftarrow (n-1) / 2$，否则 $n \leftarrow (n +1) / 2$。

总结

就是连通性和图的同构判断。

分析

找出属于同一组的点很简单，DFS就可以搞定。图的同构可以用图的Hash来判断。这个不是我想出来的，是网上看来的：
$\sum\nolimits_{i,]} distance(p_i, p_j)$
即同一组中所有点的距离加起来，这个数值做为这个图的哈希值。我不知道如何去证明，但是目前我没找到反例。至少这个题可以用。如果有同学可以帮证明可以或是不可以，那就多谢了。

总结

搜索问题。

分析

设：

1. $c_i$ 表示第$i$行最后一个被添的列，即第$i$行第$c_{i+1}$列以后是空的，以前都已经被添满
2. $p_i$ 表示边长为$i$的蛋糕的数量

基本想法如下：每次搜索都找到最短的那一行，然后试着添上蛋糕，如果不能添了就返回false。如果可以，那么就更新$c_i$和$p_i$继续搜索。 有人说直接暴搜也可以过。

总结

简单但是有点绕。

分析

根据题意，基本的想法就是找到$S_k$，然后在$S_k$中找相应的数字。很多算法和实现都会有溢出的问题。

陷阱

如果一直WA，可能是溢出问题。将int换成long long试试。