PA2 完全指南

2020-01-05 更新:本文已弃坑

这个 PA2 啊,真就是没一道省心的题了?

防剧透分割线

你还有时间撤离!

本文中出现的所有「代码」均没有 Honor Code 问题(因为都是伪代码),请放心食用。

2-1 Build

LCT 天下无敌!

注意 cost 的定义与每个结点的顺序有关,因此可以使用左儿子右兄弟表示法存储树:

1
2
3
4
5
struct tree {
// ... data
tree *left_child;
tree *right_sibling;
};

子树规模 (size) 等于所有子树的 size 之和再 +1,可以在 DFS 回溯时(或从树的某结点向上移动时)统计。

高度(深度,height)比较麻烦。我们在 tree 中增加一条记录,suffix_maximal_height,即后缀最大高度。这里的「后缀」指当前子树及所有「右边」(可以通过 right_sibling 链式访问)的兄弟子树。

为适应输入数据的含义,移动操作时,先将所操作的子树从原位置分离 (detach),然后再挂 (attach) 到目标位置。分离或挂上子树时,从子树根开始,向左(一直到头)、再向上(一层)、再向左(到头)、再向上(一层)、……一直到根,更新所有结点的 suffix_maximal_heightheight

为此需要在 tree 中额外引入一些数据成员。链式结构比较容易写错,需要特别注意,可以使用小黄鸭调试法 :-)。

2-2 Circuit

对于每个点的查询,将其前、后各 (k+1) 个 01 串插入一个 Trie 树中。然后以当前要查询的 01 串,从 Trie 的根节点开始,每次试图走与查询串对应位置数字不同的分支(如果该分支不存在,或没有任何终止结点,才走数字相同的分支)。

注意不要每次都初始化 Trie 树并插入 01 串。前一次查询结束后把最前面的 01 串去掉、再加入后一个 01 串即可。

处理重复。可以在 Trie 的叶子结点上维护一个编号列表,每次取最小值或次小值(若最小值对应了当前编号)。

其实这道题难度还可以更高一些:将 01 串全部以十进制整数的形式输入。这样,没有经验的同学可能就看不出来需要用 Trie 树解决问题了(大雾

内 存 危 机

这道题的难点根本不在于如何维护 Trie 树的结构,最麻烦的是只有 256M 内存!

计算一下 Trie 树结点规模:完全二叉树情形的结点数最多,共有 $1+2+4+\cdots+2^{18}+500000\times 46=23524187$ 个结点。这样平摊到每个结点上的内存不能超过 11 字节

考虑一下必须存储在 Trie 树结点中的数据:左右子树、及子树中终止结点的数量(删除操作不会删除已经不再对应输入字串的死路,必须使用 size 参数记录其中包含多少个终止结点)。这些加起来已经需要 $3\times 4=12$ 个字节了。真的没有办法么?

  • 方法 1:想办法把 size 参数去掉;
  • 方法 2:压缩这三个参数所用的内存空间;
  • 方法 3:减少结点数量。

方法 2 可以通过手动实现 bitset 实现(注意,没有 STL,bitset 需要自己写)。这里介绍一种更简单的写法——bitfield(位域):

1
2
3
4
5
6
struct my_struct {
int a:4;
int b:6;
int c:8;
int d:10;
};

上面定义的结构 my_struct 包含 4 个数据成员,分别占据 4、6、8、10 的空间。由于位域成员可能不会占用完整的字节,因此不可取地址

但是,默认情况下,编译器会自动对这些数据成员进行内存对齐,于是结构体的大小可能不会像预期一样小。需要在代码中手动关闭内存对齐,gcc/g++ 编译器可以这样写:

1
2
3
struct __attribute__((packed)) my_struct {
// 各数据成员
};

Warning:使用上述写法可能导致白盒分数损失。取消内存对齐虽然能节省内存使用量,但同时也会降低程序性能。当心 TLE。

方法 3 可以通过压缩 Trie 树中的长单链解决,可以期望至少能减少一半以上的结点(仅为估计,没有严格证明)。由于 (zuo) 比 (wei) 较 (xiao) 麻 (zhu) 烦 (jiao) 懒得写了。

至于使用指针动态开结点的想法,只能说……64 位环境下每个指针占用 8 字节内存,祝好运。

另外,叶子节点中实际没有必要保存编号列表(那么,如何处理呢?)。这样可以进一步压缩内存用量。

2-3 Graph

(占坑)

2-4-2 Kidd

(占坑)

2-5 Temperature

(占坑)

2-6 ChromPoly

经过多方查询资料(Wikipedia、论文等),基本可以确认这道题没有多项式时间复杂度算法,只能爆搜。

当然,直接爆搜会超时(前 10 个点只能过 4 个),需要剪枝优化。

注意到,如果我们用 k 种颜色给图染色,那么:

  • 「叶子」结点(度为 1 的结点。加了引号是因为图不一定是树)的染色方法一定有 (k-1) 种;
  • $K_r$ 完全子图中如果包含一个度恰为 (r-1) 的结点,那么这个结点的染色方法一定是 (k-r+1) 种。

其中第一条是第二条的特殊情况(想一想,为什么)。可以尝试在图中连上一些边来凑出 $K_r$ 完全子图,这样就可以缩点。但是为了避免 TLE,不要试图凑太大的完全子图,r=6 或 7 就足够了。

伪代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
chrompoly(G) {
u = 度数最小结点编号
if (degree(u)) < r) { // r 是预定的常数
if (在与 u 相邻的结点中找到了两个还没有相连的) {
H, I = 连边、缩点后的图;
return chrompoly(H) + chrompoly(I);
} else {
// 没法连边,说明结点 u 周围存在 K_{degree(u)+1} 完全子图
H = 从图中删去结点 u;
return chrompoly(H) * polynomial(x - degree(u));
}
} else {
return 在 G 中找一条边,删去、缩点、递归、套公式;
}
}

这样写出来的代码可以跑得非常快,什么 7s 时限 1G 内存根本就是吓人的: