PAT - [1152] Google Recruitment (20分)

本题使用暴力解的方法成功AC，本来担心会不会超时，但是并没有。只是实现的思路略复杂，也导致了在判断的时候遗漏了部分关键信息。

Vocabulary

1. prime number 素数
2. consequence 连续的
3. transcendental number 超越数
4. in bold 黑体的，加粗的

个人解题思路

本题使用暴力解的方法成功AC，本来担心会不会超时，但是并没有。只是实现的思路略复杂，也导致了在判断的时候遗漏了部分关键信息。

自己的复杂思路：采用枚举法，从左至右一依次寻找k位数，为了缩短时间，首先判断最后一位是否是偶数。在这里隐含了两种情况。第一种情况是是偶数，但这个数为2，2为素数；第二种情况是是除2以外的偶数，可以直接判断为非素数进入下一次的循环。
如果最后一位为奇数，且9位以下的数在int范围内，则将其该k位数转为int型，通过isPrime函数进行判断是否为素数，如果是素数则按位输出，谨防丢掉前面的几位0。
最后如果没有找到则输出404。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

bool isPrime(int q){
    bool flag = true;
    if(q==1||q==2){
        return flag;
    }else{
        for(int i=2;i<=sqrt(q);++i){
            if(q%i==0){
                flag = false;
                break;
            }
        }
        return flag;
    }
}

int main() {
    int l,k;
    scanf("%d%d",&l,&k);
    char s[l];
    scanf("%s",s);
    bool f = false;
    for(int i=0;i+k-1<l;++i){
        //此种情况表示这个k位数为偶数，偶数不是素数，除2外
        if((s[i+k-1]-'0')%2==0){
            bool flag = true;
            //如果不是00002，那么一定是偶数
            if((s[i+k-1]-'0')!=2){
                flag = false;
            }else{
                //如果flag为false，表示不是素数，为true表示是素数
                for(int j = i;j<i+k-1;++j){
                    if(s[j]!='0'){
                        flag = false;
                        break;
                    }
                }
            }
            if(flag){
                f = true;
                for(int j = i;j<i+k;++j){
                    cout<<s[j];
                }
                break;
            }else{
                continue;//向后寻找素数
            }
        }else{//非偶数的情况
            int iP = 0;
            int su = 1;
            int t = i+k-1;
            while(t>=i){
                iP += (s[t]-'0')*su;
                --t;
                su*=10;
            }
            if(isPrime(iP)){
                f =true;
                for(int j = i;j<i+k;++j){
                    cout<<s[j];
                }
                break;
            }
        }
    }
    if(!f){
        cout<<"404";
    }
    return 0;
}

代码优化

//代码链接 https://www.liuchuo.net/archives/category/code/page/5
#include <iostream>
#include <string>
using namespace std;
bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
int main() {
    int l, k;
    string s;
    cin >> l >> k >> s;
    for (int i = 0; i <= l - k; i++) {
        string t = s.substr(i, k);
        int num = stoi(t);
        if (isPrime(num)) {
            cout << t;
            return 0;
        }
    }
    cout << "404\n";
    return 0;
}

学习心得：
该题考虑了多种情况提高代码速度反而带来了更多的漏洞，可以先直接尝试暴力解是否得解，超时的话再考虑代码优化问题。

C++ stoi函数使用：

引入头文件

#include <string>

作用：将n进制的字符串转为十进制

用法

//stoi（字符串，起始位置，n进制），将 n 进制的字符串转化为十进制

stoi(str, 0, 2); //将字符串 str 从 0 位置开始到末尾的 2 进制转换为十进制

C++ substr函数使用

引入头文件

#include <string>

作用：返回一个从指定位置开始的指定长度的子字符串

用法

//只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789"
string sub1 = s.substr(5);

//从下标为5开始截取长度为3位：sub2 = "567"
string sub2 = s.substr(5, 3);