Zuma

CST LAB1

Zuma

代码 1

• 错误类型: Runtime Error

• 错误原因

void play(int rank) {
    int left = rank;
    int right = rank;
    char color = a.at(rank);

    while (left >= 0 && a.at(left) == color) --left;
    left += 1;
    while (right < a.size() && a.at(right) == color) ++right;

    int size = right - left;
    if (size >= 3) {
        a.erase(left, size);
        play(left - 1);
    }
}

由于 play 函数并未显式调用 return, 在这里 left 的范围为 [0, rank].

因此, 若 left 在函数体内变为 0, 那么在尾部调用 play(left - 1) 时便会访问到越界的内存 a.at(-1), 产生 Runtime Error.

• 测例构造思路

串 AAB 经第一次消除后变为 B, 因为消除发生在串的最前部, 此时 play 函数内 left = 0, 接下来调用 play(left - 1) 时便会访问到越界的内存 a.at(-1), 产生 Runtime Error.

• 构造测例

AAB
1
1 A

代码 2

• 错误类型: Runtime Error

• 错误原因

void play(int rank) {
    ...
    if (size >= 3) {
        a.erase(left, size);

        int next = left;
        if (left - 1 >= 0) next = left - 1;

        play(next);
    }
}

此处 play 函数处理了 left = 0 的情况. 但如果经过消除, 在函数尾部串 a 为空, 此时 left = 0, 发生调用 play(0) 便会越界访问了空串 a 的元素 a.at(0), 产生 Runtime Error.

• 测例构造思路

串 AA 经第一次消除后变为空串, 因为消除发生在串的最前部, 此时 play 函数内 next = left = 0, 接下来调用 play(next) 时便会访问到越界的内存 a.at(0), 产生 Runtime Error.

• 构造测例

AA
1
1 A

代码 3

• 错误类型: Time Limit Exceeded

• 错误原因

void play(int rank) {
    ...
    if (size >= 3) {
        a.erase(left, size);

        if (left < a.size()) {
            play(left);
        }
    }
}

这份代码在逻辑上是正确的, 但是由于采用数组实现, 时间复杂度正比于输入数据的规模. 因为数组的插入与删除操作复杂度为 $O(n)$, 那么当输入规模过大时, 会导致 Time Limit Exceeded.

• 测例构造思路

构造长度为 500000 的串 a, 并在串 a 的头部进行 500000 次插入操作, 导致超时.

代码 4

• 错误类型: Wrong Answer

• 错误原因

void play(int rank) {
    ...
    while (left > 0 && a.at(left) == color) --left;
    while (right < a.size() && a.at(right) == color) ++right;

    int size = right - left;
    if (size >= 3) {
        a.erase(left, size);

        if (left >= 0 && left < a.size()) {
            play(left);
        }
    }
}

play 函数的实现事实上并未能访问 a.at(0) 的具体元素, 注意到 left 可被赋值为 0, 此时在 erase 操作中会删去 a.at(0) 位置的元素, 如果在此时进行了消除则会导致 Wrong Answer.

• 测例构造思路

串 BAC 经第一次插入 A 后 left = 0, right = 3, 错误地在串头部发生消除, 串 a 变为 C, 产生 Wrong Answer.

• 构造测例

BAC
1
1 A

代码 5

• 错误类型: Wrong Answer

• 错误原因

int main(){
    cin >> a;
    int m = 0;
    cin >> m;
    ...
}

主函数在读取字符串 a 时使用了 cin, 因为 cin 并不能读取空串, 因此这种方式不具有鲁棒性. 这种情况下, 程序会将本属于 m 的值读入 a, 进而导致错误.

• 测例构造思路

int main() {
    ...
    for(int i = 0; i < m; ++i) {
        cin >> rank >> color;
        a.insert(a.cbegin() + rank, color);
        play(rank);
    }

    cout << a << endl;

    return 0;
}

将输入串 a 置空, 程序会将本属于 m 的值 2 读入 a, 将值 0 读入 m, 此时循环会因 m = 0 被直接跳过执行 cout << a << endl, 产生 Wrong Answer.

• 构造测例

 
2
0 A
0 B

代码 6

• 错误类型: Wrong Answer

• 错误原因

void play(int rank, char ch) {
    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);
    }
    *cur = ch;
    alen++;
    plen[pos.first]++;
    ...
}

play 函数在插入字符的时候并未考虑是否会超出数组大小, 直接执行 memmove 操作. 由于字符串采用二维数组 p[1 << 12][plen_bound] 形式存储, 占用了一块连续的内存. 若一直进行插入操作而不发生消除, 那么在单个数组到达最大容量后便会覆盖下个数组的内容, 进而导致输出串 a 时产生 Wrong Answer.

• 测例构造思路

只需向字符串头部不停执行插入操作而不产生消除即可, 在单个数组到达最大容量后便会覆盖下个数组的内容, 进而导致输出串 a 时产生 Wrong Answer.

代码 7

• 错误类型: Wrong Answer

• 错误原因

void play(int rank, char ch) {
    // 计算需要消除的开区间 (l, r)
    ...
    while (1) {
        while (l.first >= 0 && get(l) == ch) {
            l.second--;
            dis++;
            if (l.second < 0 && l.first >= 0) {
                l.first--;
                if (l.first >= 0)
                    l.second += plen[l.first];
            }
        }
        ...
    }
}

play 函数中处理左右两侧 Rank 时, 会对左右侧 Rank 进行移动. 当需要消除的字符不全处于同一数组中时, 会进行判断并将 Rank 移动指向不同的数组.

但是在移动左侧 Rank l 时使用 if 进行判断, 每移动一个字符的位置, l 最多改变一个数组的指向. 因此若存在类似 CBA| |ABC 的情况 (使用 “|” 分隔不同的数组), 向第三组头部插入字符 A, 经过一个 if 循环后, l 仅能移动到第二组而非第一组.

此时 l.first = 2, l.second = -1, 由于存储字符串使用二维数组的结构, 操作 get(l) 会访问到 p[1][plen_bound - 1] = p[1][4095], 而非预期中的 p[1][plen[1] - 1] = p[1][2], 进而导致错误地认为不能消除, 产生 Wrong Answer.

• 测例构造思路

输入 4099 位的字符串 a 使得 a 能被存储入三个数组 p[0]、p[1]、p[2], 然后通过一系列插入消除使得 p[1] 为空, 此时 p[0] 的末字符与 p[2] 的首字符均为 B. 最后向 p[2] 首部插入字符 B, 但是程序错误地认为不能消除, 产生 Wrong Answer.

代码 8

• 错误类型: Wrong Answer

• 错误原因

void play(int rank, char ch) {
    ...
    while (l.first >= 0 && get(l) == ch) {
        l.second--;
        dis++;
        while (l.second < 0 && l.first >= 0) {
            l.first--;
            if (l.first >= 0)
                l.second += plen[l.first];
        }
    }
    while (r.first < pn && get(r) == ch) {
        r.second++;
        dis++;
        while (r.second >= plen[r.first] && r.first < pn) {
            r.second -= plen[r.first];
            r.first++;
        }
    }
    if (dis > 3) {
        eliminated += dis - 1;
        lbound = l;
        rbound = r;
    }
    ...
}

play 函数在寻找相同字符这一部分缺失了其他代码所有的 while(1) 循环, 这导致在进行一次消除后无法进行同组内的连续消除, 进而产生 Wrong Answer.

• 测例构造思路

串 a 为 AABBA, 向其中插入 B 后会先发生 BBB 的消除, 但无法进行 AAA 的连续消除, 输出 AAA, 产生Wrong Answer.

• 构造测例

AABBA
1
2 B

代码 9

• 错误类型: Runtime Error

• 错误原因

void play(int rank) {
    ...
    if (eliminated > 0) {
        alen -= eliminated;
        l = lbound;
        r = rbound;
        
        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 + 1; i < r.first; i++)
            plen[i] = 0;
    }
}

play 函数在执行消除过程中并未考虑特殊处理 l.first = r.first 的情形. 那么 plen[l.first] 被赋值为 l.second + 1, 接下来 len = plen[r.first] - r.second = plen[l.first] - r.second 为负值. 而 plen[r.first] 为 size_t 类型, 即 unsigned long long 类型, 从而在赋值 plen[r.first] = len 时会因下溢出而被赋为很大的正数.

void p2a() {
    int copied = 0;
    for (int i = 0; i < pn; i++) {
        memcpy(&a[copied], p[i], plen[i]);
        copied += plen[i];
    }
}

此时对 a[copied] 进行 memcpy 时则会因为 plen[i] 过大而导致越界访问到 p[i] 长度之外的内存, 产生 Runtime Error.

• 测例构造思路

只需构造一个在同一数组内发生一次消除, 产生 l.first = r.first 的情形. 此时会因为在 memcpy(&a[copied], p[0], plen[0]) 部分出现越界访问, 产生 Runtime Error.

• 构造测例

ABBC
1
2 B

代码 10

• 错误类型: Wrong Answer

• 错误原因

void play(int rank) {
    ...
    if (eliminated > 0) {
        ...
        for (int i = l.first; i < r.first; i++)
            plen[i] = 0;
        ...
    }
}

play 函数中消除结束后, 如果消除发生在不同的块中, 那么会将 l.first 所在块的长度错误地记为 0, 如果在后续操作中插入珠子的位置在此之后, 那么 find() 函数查找到的位置就会出错, 产生 Wrong Answer.

• 测例构造思路

输入充分长的串 a 使得 a 被存储在两个数组 p[0], p[1] 中, 随后输出字符使得在 p[0]、p[1] 连接处产生消除, 程序将 p[0] 的长度错误地记为 0, 进而之后的插入会插入错误地位置, 直接关联到之后 p2a() 的过程, 产生 Wrong Answer.