魏培原
0%

Zuma 解题报告

发表于 分类于

这是DSA 2023 Spring LAB 1 Zuma的解题报告，简单指出了每一段代码的错误情况和测例构造思路，请在独立完成本LAB后再浏览本文。

代码01

最严重错误类型

Runtime Error

错误原因

经过逐行检查，发现一处代码会超下界访问数组。

1
2
3
4
if (size >= 3) {
    a.erase(left, size);
    play(left - 1);//left=0时，这里可能超下界
}

测例构造思路

使上段代码中的 left=0，也就是使某次消除之后，被消除的序号最小元素的序号为0。

代码02

最严重错误类型

Runtime Error

错误原因

经过逐行检查，发现一处代码会超下界访问数组。

1
char color = a.at(rank);//数组为空时，这里会超下界

测例构造思路

使某次消除之后，序列为空即可。

代码03

最严重错误类型

Time Limit Exceeded

错误原因

经过逐行检查，未发现代码存在逻辑或者语法错误。考虑到这个算法未采取分块策略，用时较高，因此在数据量较大时会超时。

测例构造思路

尽力使得输入序列和插入操作次数最大，于是按如下规则构造测例：

1、初始序列长度为规定的最大值500000，确保初始序列最大。前250000位由不断重复的ABCD构成，后250000位由不断重复的DCBA构成。

2、随后进行500000次操作，确保操作次数最多。这些操作分成两个部分：前250000次操作为向序列中间位置按DCBA顺序循环插入字符，使得每次插入都能完成一次消除，直到序列为空。后250000次操作为不断向序列最前端插入同一个字符A，确保尽可能多地进行消除操作。

3、按这个思路构造的测例，实现了以下三点目标：初始序列最长、操作次数最多、消除操作最多。

代码04

最严重错误类型

Wrong Answer

错误原因

经过检查，发现以下代码存在问题：

1
while (left > 0 && a.at(left) == color) --left;

这段代码负责的功能是：向左寻找最左端的可以消除的元素。可以发现，当最左端的可以消除的元素序号为1时，left 取得的实际值却为0，这将导致序号为0的元素被错误地删去。

测例构造思路

测例需要满足如下条件：

1、序号为1的元素应当被消去

2、序号为0的元素不应当被消去

可见，初始序列为ABBAA，之后向中间加一个B使B消去，即可使该程序输出错误结果。

代码05

最严重错误类型

Wrong Answer

错误原因

经过与其他整体相同思路的程序进行比较，发现该程序使用了 cin 进行初始序列输入，这将导致它无法处理空输入。

测例构造思路

初始序列为空即可。

代码06

最严重错误类型

Wrong Answer

错误原因

经过与其他整体思路相近的程序比较，发现该程序没有在一个块的元素数量超过每一块的最大长度时对块进行重新划分，这将导致它在这一情况下把当前块的数据覆盖到其他块的存储空间中，进而导致错误。

测例构造思路

1、构造一个长度足够长（长于每个块的目标长度，即2048）的初始序列，使该程序在初始分块时至少有两个块。

2、不断地向第一个块的某个位置插入字符，确保插入的字符和原序列的字符不会发生任何消除。这样的插入，至少进行超过2048次，确保第一个块的数据量超过其最大长度，将第二个块中的数据覆盖。

3、这样，原本应该输出的结果中所应该包含的第二个块的内容会因被覆盖而被省略。

代码07

最严重错误类型

Wrong Answer

错误原因

经过与其他整体思路相近的程序比较，发现该程序因为在执行消除操作的部分，没考虑l.first!=r.first的情况，所以没法一次性跨越多块消除。

注：因为存在左侧块内元素可能在之前的消除中被消除或者跨块连消等情况，所以必须实现跨越多块消除。

测例构造思路

不难发现，只要出现跨块消除的情况，就会让程序出现错误。在之前我为03设计的测例中，一定会出现跨块消除的情况，因为插入的位置不可能始终处于某个块的中心。所以，可以重复使用03的测例。

代码08

最严重错误类型

Wrong Answer

错误原因

经过与其他整体思路相近的程序比较，发现该程序在确认消除范围时出现了代码缺失。该程序这一部分的代码为：

1
2
3
4
5
if (dis > 3) {
    eliminated += dis - 1;
    lbound = l;
    rbound = r;
}

06、07、09、10程序这一部分在循环内，且代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
if (dis > 3) {
    eliminated += dis - 1;
    lbound = l;
    rbound = r;
    if (l.first >= 0) {
        ch = get(l);
        dis = 1;
    } else {
      break;
    }
} else {
    break;
}

不难发现，该程序在找到当前消除的最左端后，没有继续执行寻找下一个元素的消除的程序，因此没法实现连续消除的功能。

测例构造思路

仿照题目中的测例设计一个连消的情况即可。

代码09

最严重错误类型

Runtime Error

错误原因

经过与其他整体思路相近的程序比较，发现该程序执行消除操作的部分没有考虑l和r在同一个块的情况。这一部分的代码为：

1
2
3
4
5
6
7
8
9
10
11
if (l.first >= 0) {
    plen[l.first] = l.second + 1;//在这里，该段长度被修正为左侧被消除元素所在位置
if (r.first < pn) {
    int len = plen[r.first] - r.second;//该段长度又被减去右端长度，已经小于0了
    if (len > 0) {
        memmove(&p[r.first][0], &p[r.first][r.second], len);
    }
    plen[r.first] = len;cout<<len<<endl;
}
for (int i = l.first + 1; i < r.first; i++)
    plen[i] = 0;

不难发现，该段代码对plen的维护是错误的，肯定会导致对数组的非法访问。

测例构造思路

既然程序对块内消除的操作一定会导致后续对数组的访问越界，只要构造一个在正常块内消除操作后继续访问的情形即可。

代码10

最严重错误类型

Wrong Answer

错误原因

这段代码是思路整体相同的各段代码中写得最全面的，因此必须逐行检查是否存在问题。检查后，一共发现了两处可能出现问题的地方：

1、执行对珠子的插入操作时可能导致越界访问。这段代码为：

1
2
3
4
5
6
Rank pos = find(rank);
char *cur = &get(pos);
int succ_len = plen[pos.first] - pos.second;
if (succ_len > 0) {
    memmove(cur + 1, cur, succ_len);
}

不难发现，这段代码在使用 memmove 之前没有判断当前数组是否仍有剩余空间。如果当前数组已经达到每个数组的最大长度（即4096），则此处 memmove 会出现问题。

2、执行l和r不同块的消除操作时，对于 plen 的维护存在漏洞。这段代码为：

1
2
3
4
5
6
7
8
9
10
11
12
if (l.first >= 0) {
    plen[l.first] = l.second + 1;//第一次赋值
}
if (r.first < pn) {
    int len = plen[r.first] - r.second;
    if (len > 0) {
        memmove(&p[r.first][0], &p[r.first][r.second], len);
    }
    plen[r.first] = len;
}
for (int i = l.first; i < r.first; i++)
    plen[i] = 0;//第二次赋值

不难发现，这段代码对于 plen[l.first] 进行了两次赋值，最终结果一定为0.但事实上，显然消除序列左端所在的块可能有元素剩余，这就会导致维护失效。

测例构造思路

在以上两个问题中，我选择对第二个问题构造测例，因为这个问题的一部分（跨块消除）我已经分析过。具体分析如下：

既然消除序列左端所在的块有元素剩余的跨块消除操作会导致维护失效，那么就应该构造这种操作。不难发现，之前对03构造的测例就符合这一条件，因为：

1、这个测例被消除的部分始终位于序列的中间，而不会始终位于某个块的中间，因此会有跨块操作。

2、这个测例的前250000次操作每次只消除1组，因此被消除部分的左端所在的块一定会有元素剩余，导致该块 plen 与事实不符。

因此，可以再次复用03测例。