P A T 甲级：分类题型｜字符串处理｜1152、1150、1005、1001题解及延伸

系列目录

前言

⚠️建议按照题型分类，题号从大到小的顺序刷题～
⚠️会单独写篇BLog分享具体的题型分类、合适的刷题顺序

1152 Google Recruitment

🌟字符串

原题链接

C++
若未特殊标明，以下题解均写用C++

#include <iostream>

using namespace std;

bool isPrime(int num)
{
    if (num == 1 || num == 0) return false;
    // 用 i * i <= num 优化 原因见注解
    for (int i = 2; i * i <= num; i ++)
        if (num % i == 0) 
            return false;

    return true;
}

int main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    // i 一旦大于 n - k ，取出的string长度就不足k
    
    for (int i = 0; i <= n - k; i ++) {
        // 第一个参数 起始位置pos 
        // 第二个参数 长度len
        // 作用对象s——s.substr()
        string s1 = s.substr(i, k);
        // string to int
        int num = stoi(s1);
        if (isPrime(num)) {
            cout << s1;
            
            // return 0的作用相当于 while 里的 break
            return 0;
        }
    }

    // 循环结束也没有找到满足长度为k的 consecutive prime
    // 这里记得要加 双引号""
    cout << "404\n";

    return 0;
}

注解：

数学证明

$\\ 那么它必然还有一个小于或等于其平方根的因子 b，使得 a * b = num$

$是num的因子\ 且\ a > \sqrt{num}\\ \Rightarrow \frac{1}{a} < \frac{1}{\sqrt{num}} \\ 由因数的定义，必然存在另一个因数b \\使得\ a * b = num \\ b = \frac{num}{a} < \sqrt{num} \\ 故得证$

因此我们可以使用 i * i <= num进行优化

substr()

substr 是 std::string 类的一个成员函数，用于从字符串中提取子串这个函数接受两个参数(有时也可以接受三个参数，但在这里我们只讨论两个参数的情况)：

起始位置(pos)：子串开始的位置(基于0的索引)
长度(len)：要提取的子串的长度

例如：

string t = s.substr(i, k);

这里 s 是一个 std::string 对象，i 是起始位置，k 是要提取的子串的长度

因此，t 将包含从 s的第 i 个字符开始，长度为 k 的子串

stoi()

stoi 是一个标准库函数，用于将字符串转换为 int 类型的整数这个函数接受一个字符串参数，并尝试将其解析为一个整数如果字符串包含非数字字符(除了可能的空白字符和符号字符，如 + 或 -)，则 stoi 会抛出一个 std::invalid_argument 异常如果转换结果超出了 int 类型能够表示的范围，则会抛出一个 std::out_of_range 异常

示例：

try {  
    int num = std::stoi(t);  
    // 处理 num  
} catch (const std::invalid_argument& e) {  
    // 处理无效的输入  
} catch (const std::out_of_range& e) {  
    // 处理范围错误  
}

1150 Travelling Salesman Problem

🌟无序图+集合+二维数组

原题链接

C++
若未特殊标明，以下题解均写用C++

#include <iostream>
#include <vector>
#include <set>
#include <climits>

using namespace std;

int e[210][210], ans = INT_MAX, ansid;
// n表示顶点个数 m表示边的条数
int n, m;
vector<int> v;

void check(int index) {
    // cnt 表示 该路径的顶点数
    int sum = 0, cnt, flag = 1;
    cin >> cnt;

    // 注意 集合的定义
    set<int> s;
    vector<int> v(cnt);
    for (int i = 0; i < cnt; i ++) {
        cin >> v[i];
        // 别忘了插入集合，确保每个顶点只出现一次——便于检查比较
        s.insert(v[i]);
    }

    // 要用到 i + 1
    for (int i = 0; i < cnt - 1; i ++) {
        if(e[v[i]][v[i + 1]] == 0)
            flag = 0;
        
        // 记录权值之和
        sum += e[v[i]][v[i + 1]];
    }
    
    // 缺边
    if (flag == 0)
        printf("Path %d: NA (Not a TS cycle)\n", index);

    // 首尾顶点不是同一个顶点 或 有重复顶点
    else if (v[0] != v[cnt - 1] || s.size() != n)
        printf("Path %d: %d (Not a TS cycle)\n", index, sum);

    // 缺顶点 未被遍历
    else if (cnt != n + 1) {
        printf("Path %d: %d (TS cycle)\n", index, sum);

        if (sum < ans) {
            ans = sum;
            ansid = index;
        }
    }

    else {
        printf("Path %d: %d (TS simple cycle)\n", index, sum);

        if (sum < ans) {
            ans = sum;
            ansid = index;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++) {
        // t1-city1 t2-city2 t- destination
        int t1, t2, t;
        cin >> t1 >> t2 >> t;
        // 别忘了存储边的权值
        e[t1][t2] = e[t2][t1] = t;
    }

    // k表示要检查的路径数
    int k;
    cin >> k;
    for (int i = 1; i <= k; i ++)
        check(i);

    printf("Shortest Dist(%d) = %d\n", ansid, ans);

    return 0;
}

注解：

为什么flag == 1 只能保证所有的边存在，而不能保证所有的顶点都“存在”

实际上的图，边和顶点是分不开的，一条边的存在必然确定两个顶点
但图的某些部分没有被正确连接到遍历的起始点
说人话就是——遍历的时候只遍历到了所有的边，但并不一定遍历了所有顶点
如果为了判断某条边是否存在的同时遍历这条边的起始顶点和结束顶点，会累积大量不必要的重复

1005 Spell It Right

🌟字符串

原题链接

C++
若未特殊标明，以下题解均写用C++

// 字符串处理
#include <iostream>
#include <cstring>

using namespace std;

int main ()
{
	// 10^100 超过long long int 的范围
	// 选择使用字符串进行处理
	string a;
	cin >> a;

	int sum = 0;
	// 先求和，将 字符转换成数字
	for (int i = 0; i < a.length() - 1; i ++)
		sum += a[i] - '0';

	// 将刚才的 整数结果转化为字符串
	string s = to_string(sum);
	// 数组array 中的元素可以为任意数据类型
	// 注意 字符串是 双引号" "
	string arr[10] = {"zero", "one", "two", "three", 
	"four", "five", "six", "seven", "eight", "nine"};
	// 将所得的和转换为 consecutive words
	// 第一个字母前没有空格 我们需要单独处理
	cout << arr[s[0] - '0'];
    
	for (int i = 1; i < s.size() - 1; i ++)
		// 注意处理中间的空格；空格要用双引号括起来
		cout << " " << arr[s[i] - '0'];

	return 0;
}

1001 A+B Format

🌟字符串

原题链接

C++
若未特殊标明，以下题解均写用C++

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    string sum = to_string(a + b);
    int len = sum.size();
    for (int i = 0; i < len; i ++) {
        cout << sum[i];
        if (sum[i] == '-') continue;

        if ((i + 1) % 3 == len % 3 && i != len - 1)
            cout << ',';
    }

    return 0;
}