PAT甲级之字符串处理(一)

1001 A+B Format (20 分)

Calculate a+b and output the sum in standard format — that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input Specification:

Each input file contains one test case. Each case contains a pair of integers a and b where −106≤a,b≤106. The numbers are separated by a space.

Output Specification:

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

Sample Input:

1 2	-1000000 9 !!结尾无空行

Sample Output:

1 2	-999,991 !!结尾无空行

AC:

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    
    string sum;
    sum = to_string(a + b); // 转成字符串好按位处理
    
    string res;
    for (int i = sum.size() - 1, j = 0; i >= 0; i--) // 倒叙输出
    {
        res = sum[i] + res; // 每次拼接在原来的前面
        ++j; // 位数计数器
        if (j % 3 == 0 && i && sum[i - 1] != '-') // 计数为3的倍数且不为首位且第二位的前一位不是符号
        {
            res = ',' + res; // 添加逗号
        }
    }
    
    cout << res;
    
    return  0;
}

1005 Spell It Right (20 分)

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

Input Specification:

Each input file contains one test case. Each case occupies one line which contains an N (≤10100).

Output Specification:

For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

Sample Input:

1 2	12345 !!结尾无空行

Sample Output:

1 2	one five !!结尾无空行

AC:

#include <iostream>

using namespace std;

int main()
{
    string str;
    cin >> str; // 读入数字
    
    // 利用ASCII码差值计算每一位的和
    int sum;
    for (auto c : str) 
    {
        sum += c - '0';
    }
    
    // 转成字符串
    string s = to_string(sum);
    // 枚举英文单词
    string num[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    
    cout << num[s[0] - '0']; // 先输出首位，为满足输出格式
    for (int i = 1; i < s.size(); i++) // 遍历输出
    {
        cout << ' ' << num[s[i] - '0'];
    }
    
    return 0;
}

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

1	ID_number Sign_in_time Sign_out_time

where times are given in the format HH:MM:SS, and ID_number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.

Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40
!!结尾无空行

Sample Output:

1 2	SC3021234 CS301133 !!结尾无空行

AC:

#include <iostream>

using namespace std;

int main()
{
    string open_id, open_time; // 开门人id，开门时间
    string close_id, close_time; // 关门人id，关门时间
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        string id, in_time, out_time; // 三要素
        cin >> id >> in_time >> out_time;
        
        if (!i || in_time < out_time && in_time < open_time) // 保证签到时间比签退早且如果签到时间早于开门时间
        {
            // 更新数据
            open_id = id;	
            open_time = in_time;
        }
        if (!i || out_time > in_time && out_time > close_time) 保证签退时间比签到时间晚且如果签退时间晚于关门时间
        {
            // 更细数据
            close_id = id;
            close_time = out_time;
        }
    }
    
    cout << open_id << ' ' << close_id;
    
    return 0;
}

1035 Password (20 分)

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N (≤1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.

Output Specification:

For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line There are N accounts and no account is modified where N is the total number of accounts. However, if N is one, you must print There is 1 account and no account is modified instead.

Sample Input 1:

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa
!!结尾无空行

Sample Output 1:

2
Team000002 RLsp%dfa
Team000001 R@spodfa
!!结尾无空行

Sample Input 2:

1
2
3

1
team110 abcdefg332
!!结尾无空行

Sample Output 2:

1 2	There is 1 account and no account is modified !!结尾无空行

Sample Input 3:

2
team110 abcdefg222
team220 abcdefg333
!!结尾无空行

Sample Output 3:

1 2	There are 2 accounts and no account is modified !!结尾无空行

AC:

#include <iostream>

using namespace std;

const int N = 1000;

string userId[N], password[N]; // 存放最后输出的用户名和密码

// 密码变换
string Change(string pwd)
{
    string res;
    
    // 遍历原字符串，更改对应的字符并拼接
    for (auto c : pwd)
    {
        if (c == '1')
        {
            res += '@';
        }
        else if (c == '0')
        {
            res += '%';
        }
        else if (c == 'l')
        {
            res += 'L';
        }
        else if (c == 'O')
        {
            res += 'o';
        }
        else
        {
            res += c;
        }
    }
    
    return res;
}

int main()
{
    int n;
    cin >> n;
    
    int cnt = 0; // 更改的密码个数
    for (int i = 0; i < n; i++) 
    {
        string user, pwd;
        cin >> user >> pwd;
        
        string changed_pwd = Change(pwd); // 改变后的密码
        if (pwd != changed_pwd) // 若改变密码后不同
        {
            userId[cnt] = user; // 存入对应用户名
            password[cnt] = changed_pwd; // 存入新的密码
            ++cnt; // 计数器+1
        }
    }
    
    if (!cnt) // 如果个数为0，即没有密码改变
    {
        if (n == 1)
        {
            puts("There is 1 account and no account is modified");
        }
        else
        {
            printf("There are %d accounts and no account is modified", n);
        }
    }
    else // 有密码改变
    {
        cout << cnt << endl;
        for (int i = 0; i < cnt; i++)
        {
            cout << userId[i] << ' ' << password[i] << endl;
        }
    }
    
    return 0;
}

1036 Boys vs Girls (25 分)

This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N lines of student information. Each line contains a student’s name, gender, ID and grade, separated by a space, where name and ID are strings of no more than 10 characters with no space, gender is either F (female) or M (male), and grade is an integer between 0 and 100. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case, output in 3 lines. The first line gives the name and ID of the female student with the highest grade, and the second line gives that of the male student with the lowest grade. The third line gives the difference grade**F−grade**M. If one such kind of student is missing, output Absent in the corresponding line, and output NA in the third line instead.

Sample Input 1:

3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95
!!结尾无空行

Sample Output 1:

Mary EE990830
Joe Math990112
6
!!结尾无空行

Sample Input 2:

1
2
3

1
Jean M AA980920 60
!!结尾无空行

Sample Output 2:

Absent
Jean AA980920
NA
!!结尾无空行

AC:

#include <iostream>

using namespace std;

int main()
{
    string boy_name, boy_id;
    int boy_score;
    string girl_name, girl_id;
    int girl_score;
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        string name, sex, id;
        int score;
        cin >> name >> sex >> id >> score;
        
        // 女生
        if (sex == "F")
        {
            if (girl_name.empty() || girl_score < score) 
            {
                girl_name = name;
                girl_id = id;
                girl_score = score;
            }
        }
        // 男生
        else
        {
            if (boy_name.empty() || boy_score > score)
            {
                boy_name = name;
                boy_id = id;
                boy_score = score;
            }
        }
    }
    
    if (girl_name.empty())
    {
        puts("Absent");
    }
    else
    {
        cout << girl_name << ' ' << girl_id << endl;
    }
    
    if (boy_name.empty())
    {
        puts("Absent");
    }
    else
    {
        cout << boy_name << ' ' << boy_id << endl;
    }
    
    if (girl_name.size() && boy_name.size()) // 存在相关的女生和男生
    {
        cout << girl_score - boy_score << endl;
    }
    else
    {
        puts("NA");
    }
    
    return 0;
}

1050 String Subtraction (20 分)

Given two strings S1 and S2, S=S1−S2 is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate S1−S2 for any given strings. However, it might not be that simple to do it fast.

Input Specification:

Each input file contains one test case. Each case consists of two lines which gives S1 and S2, respectively. The string lengths of both strings are no more than 104. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

Output Specification:

For each test case, print S1−S2 in one line.

Sample Input:

1
2
3

They are students.
aeiou
!!结尾无空行

Sample Output:

1 2	Thy r stdnts. !!结尾无空行

AC:

#include <iostream>
#include <unordered_set> // 哈希表头文件

using namespace std;

string s1, s2;

int main()
{
    // 因为需读入两行，用getline
    getline(cin, s1); 
    getline(cin, s2);
    
    unordered_set<char> hash; // 创建一个哈希表
    // 将s2中字符存入
    for (auto c : s2)
    {
        hash.insert(c);
    }
    
    string res;
    for (auto c : s1) // 遍历s1
    {
        if (!hash.count(c)) // 判断hash中是否存在
        {
            res += c;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

1071 Speech Patterns (25 分)

People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.

Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?

Input Specification:

Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return \n. The input contains at least one alphanumerical character, i.e., one character from the set [0-9 A-Z a-z].

Output Specification:

For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

Note that words are case insensitive.

Sample Input:

1 2	Can1: "Can a can can a can? It can!" !!结尾无空行

Sample Output:

1 2	can 5 !!结尾无空行

AC:

#include <iostream>
#include <unordered_map>

using namespace std;

bool check(char c) // 根据题目条件判断是否合法
{
    if (c >= 'A' && c <= 'Z') {
        return true;
    }
    else if (c >= 'a' && c <= 'z') {
        return true;
    }
    else if (c >= '0' && c <= '9') {
        return true;
    }
    else {
        return false;
    }
}

int main()
{
    string str;
    getline(cin, str);
    
    unordered_map<string, int> hash; // 用来存储常用词和对应出现的次数
    for (int i = 0; i < str.size(); i++) // 遍历，采用双指针算法
    {
        if (check(str[i])) // 判断是否合法
        {
            int j = i; // 从此时的下标向后遍历
            string word; // 常用词
            while (j < str.size() && check(str[j])) // 直到句子结束且字符合法
            {
                word += tolower(str[j++]); // 存储常用词
            }
            
            hash[word]++; // 存入常用词及其出现次数
            i = j; // 接着遍历
        }
    }
    
    string res; // 存放答案
    int cnt = - 1; // 计数器
    
    for (auto item : hash) // 遍历
    {
        // 出现次数大于此时计数或者常用词出现次数一样且长度小于另一个，利用字典序大小
        if (item.second > cnt || (item.second == cnt && item.first < res)) 
        {
            res = item.first;
            cnt = item.second;
        }
    }
    
    cout << res << ' ' << cnt << endl;
    
    return 0;
}

1001 A+B Format (20 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

AC:

1005 Spell It Right (20 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

AC:

1006 Sign In and Sign Out (25 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

AC:

1035 Password (20 分)

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

Sample Input 3:

Sample Output 3:

AC:

1036 Boys vs Girls (25 分)

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

AC:

1050 String Subtraction (20 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

AC:

1071 Speech Patterns (25 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

AC: