曾彪彪的个人网站
首页
文章列表
>>
文章详情
# P1098 [NOIP 2007 提高组] 字符串的展开 (测试用例设计方法总结)
作者:
曾彪彪
日期:
2025-07-03 03:50:50
阅读(49)
分类:
问题记录
Algorithm
# 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; } 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; } ``` 切记,不要合并测试用例,一个测试用例要足够简单,很容易就能看出结果,多执行几次测试用例,不会花太多时间。 合并测试用例的坏处: - 容易遗漏 - 容易失误 经过上面测试用例测试后,一次提交AC
评论(0)
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)
提交
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)