Lab1 Report

发布于 2023-01-26

本Lab要求针对一道PA题给出的十份错误代码，分析出错原因以及可能发生的最严重错误，并给出一个能够造成最严重错误的测例。

code 1¶

最严重错误类型：Runtime Error
产生错误原因：在play()函数中，由于游戏可能消除到rank=0的位置，此时会递归调用play(-1)，从而出现越界访问a(-1)的情况，造成Runtime Error。
测例构造：构造一个会向前消除到rank=0位置的测例即可触发此错误。测例如下：
```
AAB
1
0 A
```
code 2¶
最严重错误类型：Runtime Error
产生错误原因：在play()函数中，若游戏消除到rank=0位置，则会递归调用play(0)，但若此时字符串被消除至空串，则会出现越界访问a(0)的情况，造成Runtime Error。
测例构造：构造一个会消除至空串的测例即可触发此错误。测例如下：
```
AA
1
0 A
```

code 3¶

最严重错误类型：Time Limit Exceeded
产生错误原因：在插入字符的时候，没有采用memmove()函数移动字符串元素，而是采用了效率较低的insert()方法，当测例字符串长度很长、操作数量很多时，程序会运行超时。
测例构造：构造长度接近数据范围上界的初始字符串，例如可以将字符串"ABCDE"重复十万次，随后构造五十万次插入操作，可以简单地从开头依次插入'A','B','C','D','E'，重复十万次。测例如下：
```
ABCDEABCDE...ABCDE //长度为500000
499999
0 A
1 B
2 C
3 D
4 E
5 A
6 B
7 C
8 D
9 E
...
499990 A
499991 B
499992 C
499993 D
499994 E
499995 A
499996 B
499997 C
499998 D
```

code 4¶

最严重错误类型：Wrong Answer
产生错误原因：在play()函数中，left的起始位置为rank，判断能否消除是根据right - left >= 3来判断，则应在while (left > 0 && a.at(left) == color) --left;语句后增加一句left += 1;来确保检查完毕后left在正确的可消除区域的左端点，而本程序中没有这一句，则会导致错误的区域消除，从而造成Wrong Answer。
测例构造：构造测例使得插入的字符恰好与该位置右侧的字符相同，则会导致错误的消除。测例如下：
```
ABC
1
1 B
```

code 5¶

最严重错误类型：Wrong Answer
产生错误原因：初始字符串可能是空字符串，但是本程序中采用cin来读取字符串，无法读取空串，从而造成后续操作全部错误，从而造成Wrong Answer。
测例构造：输入的初始字符串为空字符串即可。例如：
```
1
0 A
```

code 6¶

最严重错误类型：Wrong Answer
产生错误原因：本程序中用二维数组的形式对出事的字符串进行分块存储，但是没有考虑到后续操作过程中，某一块长度过长，超出设定的最大长度的情况，此时这一块字符串会往后溢出，覆盖后面分块中的内容，从而导致字符串操作不正常，最终造成Wrong Answer。

测例构造：构造一个测例，在初始字符串中同一位置（例如0号位置）不断插入字符至超出每一块的长度限制，随后向得到的字符串中随机位置进行多次操作，就会造成Wrong Answer。测例如下：

ABCDEFGABCDEFG...ABCDEFG
30000
0 A
0 B
0 C
0 D
0 E
0 F
0 G
0 H
...
0 A
0 B
0 C
0 D
0 E
0 F
0 G
0 H //此处为两万次操作
//以下均为随机位置，随机插入字符，共一万次
629 A
777 F
903 B
503 F
759 D
699 F
987 B
...
877 A
449 D
955 A
651 D
950 C

code 7¶

最严重错误类型：Wrong Answer
产生错误原因：在消除的时候可能会出现中间某一块长度为0的情况，设这一块为第\(i\)块，此时若第\(i-1\)块的末尾与第\(i+1\)块的开头可以进行消除，但执行消除过程的时候左端点一次只能移动一块，这会导致l.second < 0，从而导致无法执行这样的消除操作。

测例构造：构造测例使得中间某块可以被消除至长度为0，且前后可以形成可消除块即可。测例如下：

ABCDEFGHABCDEFGH...ABCDEFGABBCC...BBCCAZ
//上述字符串长度为4098，第2048个字符为A，从第2049个字符开始，重复输入BBCC，第4097个字符为A，第4098个字符为任意，此处为Z
1025
2048 B
2048 C
2048 B
2048 C
...
2048 B
2048 C
2048 B
2048 C//此处为1024次操作
2048 A

code 8¶

最严重错误类型：Wrong Answer
产生错误原因：本程序中，在计算需要消除的区域时，缺少了while(1)的控制，只会进行一次计算，无法做到连续消除。
测例构造：构造可以连续消除的测例即可。测例如下：
```
AABBA
1
1 B
```

code 9¶

最严重错误类型：Runtime Error
产生错误原因：没有考虑到在同一块字符内出现消除的情况，此时会导致len < 0，而数组plen中存储的数据类型为unsigned long long，此时会导致某一块长度超过最大长度，从而导致溢出，造成Runtime Error。
测例构造：构造在某一块内产生消除的情况即可，例如在第一块消除，测例如下：
```
ABBC
1
1 B
```

code 10¶

最严重错误类型：Wrong Answer
产生错误原因：在for (int i = l.first; i < r.first; i++)这一行中，会导致消除后left标志所在的块的长度也被修改为0，导致之后的修改操作无法正确执行，从而导致Wrong Answer。

测例构造：构造一个测例，第\(i\)块全部消除至长度为0，第\(i-1\)块发生消除但不会消除至长度为0，第\(i-1\)块的末尾和第\(i+1\)块的开头可以组成另一次消除。这样的测例会造成Wrong Answer。测例如下：

HGFEDCBAHGFEDCBA...HGFEDCBABBCC...BBCCAZ
//上述字符串长度为4098，从第2049个字符开始，重复输入BBCC，第4097个字符为A，第4098个字符为Z
1027
1 G
1 G
2048 B
2048 C
2048 B
2048 C
...
2048 B
2048 C//此处为第1026次操作
2048 A