用C++解决以下问题在500ms内完成：题目背景luogu站长 kkksc03 新开了一家公司这个公司的招募方式非常奇怪：每当有一个人来面试必然严查祖上三代不包括自己有没有禁过言的或进过陶片的就像政审一样。因为面试的人太多了kkksc03 实在算不过来他找到了你请你编写一个程序帮助他进行审核。题目描述现在有 t 个人要前来面试每个人的简历里面有一段家谱供 kkksc03 审核这个家谱是一段长度为

思路：

1. 遍历每个人的家谱字符串，从左到右逐位判断是否有违规情况。
2. 如果当前位是'1'，则表示这个人犯过事情，直接输出"NO"，并终止当前人的面试。
3. 如果当前位是'A'，则表示这个人自己，判断其前三代是否有违规情况。
4. 如果前三代中有违规情况，则输出"NO"，并终止当前人的面试。
5. 如果前三代都没有违规情况，则输出"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内可以完成