曾彪彪的个人博客 -- # P1098 [NOIP 2007 提高组] 字符串的展开 (测试用例设计方法总结)

# P1098 [NOIP 2007 提高组] 字符串的展开

## 题目描述

在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于 `d-h` 或者 `4-8` 的字串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为 `defgh` 和 `45678`。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：

(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号 `-` ，减号两侧同为小写字母或同为数字，且按照 `ASCII` 码的顺序，减号右边的字符严格大于左边的字符。

(2) 参数 $p_1$：展开方式。$p_1=1$ 时，对于字母子串，填充小写字母；$p_1=2$ 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。$p_1=3$ 时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号 `*` 来填充。

(3) 参数 $p_2$：填充字符的重复个数。$p_2=k$ 表示同一个字符要连续填充 $k$ 个。例如，当 $p_2=3$ 时，子串`d-h` 应扩展为 `deeefffgggh`。减号两边的字符不变。

(4) 参数 $p_3$：是否改为逆序：$p_3=1$ 表示维持原来顺序，$p_3=2$ 表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当 $p_1=1$、$p_2=2$、$p_3=2$ 时，子串 `d-h` 应扩展为 `dggffeeh`。

(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：`d-e` 应输出为 `de`，`3-4` 应输出为 `34`。如果减号右边的字符按照 `ASCII` 码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：`d-d` 应输出为 `d-d`，`3-1` 应输出为 `3-1`。

## 输入格式

共两行。

第 $1$ 行为用空格隔开的 $3$ 个正整数，依次表示参数 $p_1,p_2,p_3$。

第 $2$ 行为一行字符串，仅由数字、小写字母和减号 `-` 组成。行首和行末均无空格。

## 输出格式

共一行，为展开后的字符串。

## 输入输出样例 #1

### 输入 #1

```
1 2 1
abcs-w1234-9s-4zz
```

### 输出 #1

```
abcsttuuvvw1234556677889s-4zz
```

## 输入输出样例 #2

### 输入 #2

```
2 3 2
a-d-d
```

### 输出 #2

```
aCCCBBBd-d
```

## 说明/提示

$40\%$ 的数据满足：字符串长度不超过 $5$。

$100\%$ 的数据满足：$1  \le  p_1  \le  3,1  \le  p_2  \le  8,1  \le  p_3  \le  2$。字符串长度不超过 $100$。

NOIP 2007 提高第二题

这是一道模拟题，第一次提交只得了60分，查看失败原因，发现自己漏了一些测试用例，造成部分测试无法通过。
这是第一次提交的代码：
```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
- define function getOutputString(vector<char> sign) to get output string, receive parameter "a-b", return output string.
- loop the input string, if s[i]=='-', then call getOutputString to get output string, and replace "-" with the output string.
- for the getOutputString, according to the description to implement the logic.
-
test case:
-
1 2 1
abcs-w1234-9s-4zz
-
2 3 2
a-d-d
-
3 2 1
abcs-w1234-9s-4zz
-
1 2 1
abcs-w1234-9s-4zz-c
-
1 2 1
abcs-w1234-9s-4zz-z
-
1 2 1
abcs-w1234-9s-4z4-2ff4-4ff4-s
-
1 2 1
-abcs-w1234-9s-4zz-
-
1 2 1
-abcs-w1234-9s-4za-D-D-E
-
2 3 2
a-d-d-e
first submit score: 60
cause:
test case doesn't cover below case:
1 5 1
-254-243-52-345-243-5234-52-345-234-52-345-234-52345-4325-2345-2345-2345

**/

#include <bits/stdc++.h>
using namespace std;

int p1, p2, p3;

string getOutputString(char start, char end)
{
    string result = "";
    char l = start + 1, r = end - 1;
    if (l == r)  //这里错误，如果a-c这种场景，会返回空，实际应该包含字母b的输出
    {
        return result;
    }
    if (p1 == 3)
    {
        int len = (r - l) + 1;
        return string(len * p2, '*');
    }
    if (p1 == 2)
    {
        l -= 32;
        r -= 32;
    }
    for (int i = l; i <= r; i++)
    {
        string t(p2, i);
        result.append(t);
    }
    if (p3 == 2)
    {
        reverse(result.begin(), result.end());
    }

return result;
}

bool needTransfer(char a, char b)
{
    if (a >= '0' && a <= '9' && b >= '0' && b <= '9' && a < b)
    {
        return true;
    }
    if (a >= 'a' && a <= 'z' && b >= 'a' && b <= 'z' && a < b)
    {
        return true;
    }
    return false;
}

int main()
{

// freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    cin >> p1 >> p2 >> p3;
    string input;
    cin >> input;
    input = "-" + input + "-";
    string ans = "";
    for (int i = 1; i < input.size() - 1; i++)
    {
        if (input[i] != '-')
        {
            ans.push_back(input[i]);
            continue;
        }
        if (needTransfer(input[i - 1], input[i + 1]))
        {
            ans.append(getOutputString(input[i - 1], input[i + 1]));
        }
        else
        {
            ans.push_back(input[i]);
        }
    }
    cout << ans;
    return 0;
}

```
测试用例是非常重要的，不经过全面的测试，即使这题思路正确，也只能拿60分。正好这道题需要分情况讨论的场景比较多，我们就来设计一下测试用例。
之前设计的测试用例不全，是因为设计测试用例的思路不对。原来的设计思路是：

p1=1
    p2=1
        p3=1
            数字字符
            char字符
        p3=2
            数字字符
            char字符    
    p2=8
p1=2
p1=3

然后设计字符顺序测试用例

a-b 相差1
a-c 相差2  (这个测试用例被忽略了)
a-f 相差>2
b-a

1-2
1-3
1-9
3-1

最后设计非常规用例
-1-2-4--- 
1-a
A-B
a-B

上面测试用例设计思路有点混乱。在设计第一组测试用例是，使用了深度优先的方式，这个其实挺复杂的，场景特别多，有3*2*2*2=24种场景。(p1有三个值，p2两个值，p3有两个值需要测试，再加上数字和字符两种场景)
而在顺序和异常场景测试用例设计时，有采用了广度优先的方式。
所以最终还是使用广度优先的方式来设计测试用例，如下：

首先设计一个字符串，包含字符串相关的所有测试用例，如：

p1
    p1=1
        数字字符(covered)
        char字符(c)
    p1=2
        数字字符
        char字符
    p1=3
        数字字符
        char字符
p2
    p2=1
        char字符
    p2=3
        数字字符
    p2=8
        char字符
p3
    p3=1
        数字字符
        char字符
    p3=2
        char字符
        char字符

然后加上字符顺序测试用例和非常规测试用例，最后的测试用例和代码如下：
```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
- define function getOutputString(vector<char> sign) to get output string, receive parameter "a-b", return output string.
- loop the input string, if s[i]=='-', then call getOutputString to get output string, and replace "-" with the output string.
- for the getOutputString, according to the description to implement the logic.
-
test case:
-
1 2 1
abcs-w1234-9s-4zz
-
2 3 2
a-d-d
-
1 2 1
a-d-1-5
-
2 2 1
a-d-1-5
-
3 2 1
a-d-1-5
-
1 8 1
a-d-1-5
-
1 1 1
a-d-1-5
-
1 2 1
a-d-1-5
-
1 2 2
a-d-1-5
-
1 2 1
a-b
-
1 2 1
a-c
-
1 2 1
a-f
-
1 2 1
b-a
-
1 2 1
1-2
-
1 2 1
1-3
-
1 2 1
1-8
-
1 2 1
9-1
-
1 2 1
--1-3--
-
1 2 1
--a-d--
-
1 2 1
1-a
-
1 2 1
A-B
-
1 2 1
a-B
first submit score: 60
cause:
test case doesn't cover below case:
1 5 1
-254-243-52-345-243-5234-52-345-234-52-345-234-52345-4325-2345-2345-2345

**/

#include <bits/stdc++.h>
using namespace std;

int p1, p2, p3;

string getOutputString(char start, char end)
{
    string result = "";
    char l = start + 1, r = end - 1;
    if (p1 == 3)
    {
        int len = (r - l) + 1;
        return string(len * p2, '*');
    }
    if (p1 == 2 && l >= 'a' && l <= 'z')
    {
        l -= 32;
        r -= 32;
    }
    for (int i = l; i <= r; i++)
    {
        string t(p2, i);
        result.append(t);
    }
    if (p3 == 2)
    {
        reverse(result.begin(), result.end());
    }

return result;
}

int main()
{

```

切记，不要合并测试用例，一个测试用例要足够简单，很容易就能看出结果，多执行几次测试用例，不会花太多时间。
合并测试用例的坏处：
- 容易遗漏
- 容易失误

经过上面测试用例测试后，一次提交AC

# P1098 [NOIP 2007 提高组] 字符串的展开 (测试用例设计方法总结)

评论(0)