C++ 实现 luogu 公司面试审核系统 - 500ms 内高效完成 - 常规

C++ 实现 luogu 公司面试审核系统 - 500ms 内高效完成

题目背景

luogu 站长 kkksc03 新开了一家公司，这个公司的招募方式非常奇怪：每当有一个人来面试，必然严查祖上三代（不包括自己）有没有禁过言的或进过陶片的，就像'政审'一样。因为面试的人太多了，kkksc03 实在算不过来，他找到了你，请你编写一个程序帮助他进行审核。

题目描述

现在有 t 个人要前来面试，每个人的简历里面有一段家谱供 kkksc03 审核，这个家谱是一段长度为 n 的字符串，从左到右每一位辈分递减，表示祖先到儿孙的违规情况，如果这个人犯过事情，那么这个人对应的那一位将会标记为 1 ，否则为 0 ，这个人自己在家谱中表示为 A.

思路：

遍历每个人的家谱字符串，从左到右逐位判断是否有违规情况。
如果当前位是'1'，则表示这个人犯过事情，直接输出'NO'，并终止当前人的面试。
如果当前位是'A'，则表示这个人自己，判断其前三代是否有违规情况。
如果前三代中有违规情况，则输出'NO'，并终止当前人的面试。
如果前三代都没有违规情况，则输出'YES'，并继续下一个人的面试。

代码如下：

#include <iostream>
#include <string>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string genealogy;
        cin >> genealogy;
        bool isViolated = false;
        for (int i = 0; i < genealogy.length(); i++) {
            if (genealogy[i] == '1') {
                isViolated = true;
                break;
            } else if (genealogy[i] == 'A') {
                if (i >= 3 && genealogy[i-1] == '1' && genealogy[i-2] == '1' && genealogy[i-3] == '1') {
                    isViolated = true;
                    break;
                }
            }
        }
        if (isViolated) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
    return 0;
}

时间复杂度分析：

每个人的家谱字符串长度为n，遍历每个人的家谱字符串需要O(n)的时间，总共有t个人，所以总时间复杂度为O(t*n)。由于题目给出t和n的范围不超过1000，所以算法在500ms内可以完成。