此文主要为了方便【想要参加南京大学软件学院】的同学熟悉机试题目类型。不知是否由于今年特殊原因，今年南软的机试类型和以往（一道算法题，一道面向对象编程题）不同。
注：南软通知入营后，会加入一个群聊，群文件中有《南京大学软院夏令营机试练习指南》，里面有介绍机试的慕测平台，以及如何注册账 、练习、参加考试等等
1，字符串的修改
1）题目
题目描述
依旧是字符串处理，设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。 对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
输入描述
输出描述
测试样例
输入
输出
2）解题思路
从字符串A”daaqerdwq”（横轴）到字符串B”afwdreqew”（纵轴），需经过最少的变换次数为8（棕色方框展示）
状态转移方程如下：
- 由于从 字符串变为空 / 空变为字符串 只有单纯的 删除 / 添加 操作，所以dp[x][0]和dp[0][x]对应的最少操作次数，都是相应字符串位数；
- 由于字符串编 从0开始，而dp数组中对于字符串的处理从1开始（第0行，第0列有其他用途），所以A[j-1]对应的是A中第j个字符，B[i-1]同理；
- 计算dp[i][j]需要考虑三个位置的值，并选择最小值：
- dp[i-1][j]+1（字符串A[0,j-1]已经转换为字符串B[0,i-2]，还需添加一个字符B[i-1]。比如daaqerdwq=》afwdreqew，再添加w即可）、
- dp[i][j-1]+1（字符串A[0,j-2]已经转换为字符串B[0,i-1]，还需删去一个字符A[j-1]。比如daaqerdwq=》afwdreqew，再删除q即可）、
- dp[i-1][j-1]+(1/0)（当A[j-1]==B[i-1]时，可直接把A[j-2]转换为B[i-2]的操作次数dp[i-1][j-1]，看作A[j-1]转换为B[i-1]的操作次数dp[i][j]，否则只需将A[j-1]修改为B[i-1]即可。比如当A[j-1]不等于B[i-1]时，即daaqerdwq=》afwdreqew，q转换为w即可,dp[i][j] == dp[i-1][j-1]+1；当A[j-1]等于B[i-1]时，即daaqerdww=》afwdreqew，dp[i][j] == dp[i-1][j-1]）。
3）AC代码（C++）
2，字符串正反连接
1）题目
题目描述
输入描述
输出描述
测试样例
输入
输出
2）解题思路
getline(cin, String)读取数据（不能直接用cin，因为字符串中间可能含有空格）
然后字符串遍历拼接（String类型操作还是很方便的）
3）AC代码（C++）
3，字符串的展开
1）题目描述
题目描述
如果在输入的字符串中，含有 类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减 ，即，将上面两个子串分别输出为 “defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：
(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减 “-”，减 两侧同为小写字母或同为数字，且按照ASCII码的顺序，减 右边的字符严格大于左边的字符。
(2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星 “*”来填充。
(3) 参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减 两边的字符不变。
(4) 参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减 两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。
(5) 如果减 右边的字符恰好是左边字符的后继，只删除中间的减 ，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减 右边的字符按照 ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减 ，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。
数据规模和约定
100%的数据满足：1
输入描述
输出描述
测试样例
输入
输出
2）解题思路
类似于这种条件非常复杂的情况，我比较喜欢的做法是自顶向下，从主函数入手，看需要辅助函数得到什么样的结果，先把函数接口和输出接口定义好，便假定这个函数已经得到了我想要的东西，于是接着往下写。在构造辅助函数时，原理同上。
比如：
- 主函数：针对小的题目，由于不需要考虑参数在整个工程中的复杂关系，这里为了使函数参数列表看起来不那么臃肿，将输入字符串以及参数p1, p2, p3当作全局变量。而且我希望通过unford()函数得到完全处理后的字符串，于是就有了ans = unford();
- string unford()：我要得到完全处理后的字符串，那么需要判断当前字符是否需要扩展needUnford，以及得到扩展后的字符串unfordString；
- bool needUnford(int i)：希望通过此函数判断是否需要扩展；
- string unfordString(char a, char b)：希望通过此函数获得扩展部分的字符串，根据参数处理字符串即可；
3）AC代码（C++）
- //#include
- #include
- #include
- #include
-
using namespace std;
-
-
int p1, p2, p3;
- string input;
-
-
bool needUnford(int i){ //判断当前位置是否能够展开
- if(input[i] == '-'){
- if(i - 1 >= 0 && i + 1 length()){ //判断边界
- if((input[i-1] >= '0' && input[i+1] '9' && input[i-1] 1]) ||
- (input[i-1] >= 'a' && input[i+1] 'z' && input[i-1] 1])){
- return true;
- }else return false;
- }else return false;
- }else return false;
- }
-
string unfordString(char a, char b){ //构造展开后的字符串
- string ans;
- for(char c = a + 1; c
- for(int i = 0; i
- ans += c;
- }
- }
-
- if(p3 == 2){
- reverse(ans.begin(), ans.end()); //无返回值
- }
-
- if(p1 == 2){
- transform(ans.begin(), ans.end(), ans.begin(), ::toupper);
- }else if(p1 == 3){
-
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！