[数据结构与算法]信息学奥赛第一节——字符串1

字符串string类

string是C++中STL标准模板库提供的字符串类，用来处理字符串相关的问题

字符串与字符数组的区别

• 其实，字符串的本质依然是字符数组。只不过string是长度不固定的，或者说是长度不限的字符数组。在使用string类的时候，不要先定义长度，如char c[100]
• 先定义一个字符数组c

char c[100];//c[0] == *c

• 字符数组相关的函数比较少，string集成了很多的函数
• 字符数组的本质是数组，故其不能直接进行比较或者拼接运算。string可以直接进行比较或拼接运算
• 对于没有学习过字符数组的学生，也是可以直接学习string

通过下述代码，可以实现字符串的“加法操作”

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    
    //加法操作
    s += "hello";
    s += ' ';
    s += "world!";
    
    cout << s << endl;//hello world!
    return 0;
}

字符串的读取

string s;//首先定义字符串

可以考虑两种读取方式：

• 直接cin >> s；
• 使用函数getline(cin,s);

以上两种读取方式的区别是，前者不可以读入空格。而后者是读入一行字符换，字符串中可以有空格，遇到换行符时才结束

字符串的相关函数

• s.size() —— 字符串的长度
• s[下标] —— 访问字符串某个位置的元素

根据以上知识点，请完成下题
Acwing 760 字符串长度
AC代码：

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    getline(cin,s);//读入一行字符串
    
    cout << s.size() << endl;//输出字符串的长度
    return 0;
}

练习1

原题链接

题目描述

看到两个标准格式的时间，有小时，有分钟，有秒，格式如：h : m : s，即 时:分:秒 你想知道，这两个时间之间相差多少吗？

输入

输入包括两行，两行均为一个“时:分:秒”格式的时间。且本题保证第一个时间一定大于第二个时间！

输出

输出就是输入的两个时间之间的秒数差。

样例输入

01:10:10
00:30:30

样例输出

2380

解题思路：先读入两个字符串，使用s[下标]的方法将其元素取出，然后将字符转换为数字，再进行运算即可。字符转化为数字的方法：s[x] - '0'
AC代码：

#include <iostream>
#include <string>

using namespace std;

//用来计算传入的字符串s可以转化为多少秒
int cal_second(string s)
{
    int h,m,second;//分别代表对应的小时、分钟、秒数
    h = (s[0] - '0') * 10 + s[1];
    m = (s[3] - '0') * 10 + s[4];
    second = (s[6] - '0') * 10 + s[7];
    
    int res = h * 3600 + m * 60 + second;
    return res;
}

int main()
{
    string s1;
    string s2;
    
    getline(cin,s1);
    getline(cin,s2);
    
    cout << cal_second(s1) - cal_second(s2) << endl;
    return 0;
}

练习2

原题链接

题目描述

输入一个很大的数，求各位上的数字和。

输入

一个很大的整数（不超过200位）

输出

一个整数

样例输入

123

样例输出

6

解题思路：本题的解题思路和上题类似，直接遍历字符串中各个位置上的元素，先将各个字符转化为数字，再进行求和即可。
AC代码：

#include <iostream>
#include <string>

using namespace std;

//用来计算传入的字符串s各个位置上的数字之和
int cal_sum(string s)
{
    int res = 0;//res用来存储数字之和
    int len = s.size();
    for (int i = 0;i < len;i++) res += (s[i] - '0');
    return res;
}

int main()
{
    string s1; getline(cin,s1);
    
    cout << cal_sum(s1) << endl;
    
    return 0;
}

在此简单介绍一下如何构造一些特殊的、方便自己计算的数据来进行代码的测试：

• 输入20个1，答案输出的应该是20
• 输入20个0，答案输出的应该是0
• 对样例进行测试，应该输出6
• 不要输入123456789101112131415，这样不方便自己对代码进行测试

练习3

原题链接

题目描述

Julius Caesar曾经使用过一种很简单的密码。对于明文中的每个字符，将它用它字母表中后5位对应的字符来代替，这样就得到了密文。比如字符A用F来代替。如下是密文和明文中字符的对应关系。
密文：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
明文：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
你的任务是对给定的密文进行解密得到明文。
你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。

输入

一行，给出密文，密文不为空，而且其中的字符数不超过200。

输出

输出一行，即密文对应的明文

样例输入

NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX

样例输出

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES

解题思路：通过题意可以得到，将明文向后移动五个位置得到密文，那么将密文向前移动五个位置就可以得到明文。但是在将密文转化为明文(向前移动)的过程中，需要考虑到英文字母表的前五个字符会超出界限，故'A'、'B'、'C'、'D'、'E'需要单独处理才可以得到其对应的明文，且通过观察，我们不难发现以下规律：

A + V - A = V
B + V - A = W
C + V - A = X
D + V - A = Y
E + V - A = Z

AC代码：

#include <iostream>
#include <string>

using namespace std;

//用来将传入的字符串s各个位置上的字符向前移动五个位置
string mi_to_ming(string s)
{
    int len = s.size();//计算字符串的长度
    for (int i = 0;i < len;i++)
    {
        if (s[i] >= 'A' && s[i] <= 'Z')//是大写字母才对其进行解密
        {
            if (s[i] >= 'F' && s[i] <= 'Z') s[i] = s[i] - 5;//是大写字母且不超过界限
            else s[i] = s[i] + 'V' - 'A';//移动过程中超过界限的字符需要单独处理
        }
    }
    return s;
}

int main()
{
    string s1; getline(cin,s1);
    
    cout << mi_to_ming(s1) << endl;
    
    return 0;
}