密码

GitHub跳转原题关系图Canvas 关系图返回列表

一次扫描统计密码是否含字母、数字、特殊字符及同字符频次，据此按高、中、低三级规则分类。

OJ: shumeng

题目 ID: CSP202409A

难度:入门

标签:模拟字符串计数

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 一次扫描统计
    2. 按等级判断
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 nn 个密码串（由大小写字母、数字、*、# 组成），按规则输出每个密码的安全等级：

  • 高安全度（输出 2）：同时含字母、数字、特殊字符，且每个字符出现次数不超过 22；
  • 中安全度（输出 1）：同时含三类字符，但存在某字符出现次数超过 22；
  • 低安全度（输出 0）：未同时含三类字符。

思路

只需要对每个密码维护四个信息：是否出现字母、是否出现数字、是否出现特殊字符，以及每个字符的出现次数。

一次扫描统计

扫描字符串的每个字符：按字符范围判断它属于哪一类并置对应布尔标记，同时把该字符的计数加一。由于密码只由字母、数字、*、# 构成，非字母非数字的字符就是特殊字符。

按等级判断

统计完成后按从高到低的包含关系判断：

  1. 三类字符齐全且所有字符频次都不超过 22 → 2；
  2. 三类字符齐全但存在频次超过 22 → 1；
  3. 否则 → 0。

用长度为 128128 的数组记录 ASCII 字符频次即可，无需映射结构。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

// 判断单个字符属于哪类：字母 / 数字 / 特殊字符
void classify(char ch, bool &has_letter, bool &has_digit, bool &has_special) {
    if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z')) {
        has_letter = true;
    } else if ('0' <= ch && ch <= '9') {
        has_digit = true;
    } else {
        has_special = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    while (n--) {
        string password;
        cin >> password;

        // 统计三类字符是否出现，以及每个字符的出现次数
        bool has_letter = false;
        bool has_digit = false;
        bool has_special = false;
        int count[128] = {};
        for (int i = 0; i < (int)password.size(); i++) {
            unsigned char ch = password[i];
            count[ch]++;
            classify((char)ch, has_letter, has_digit, has_special);
        }

        // 是否存在出现次数超过 2 的字符
        bool has_three_same = false;
        for (int i = 0; i < 128; i++) {
            if (count[i] > 2) {
                has_three_same = true;
                break;
            }
        }

        // 高安全度：三类字符齐全且每个字符至多出现 2 次
        if (has_letter && has_digit && has_special && !has_three_same) {
            cout << 2 << '\n';
        } else if (has_letter && has_digit && has_special) {
            cout << 1 << '\n';
        } else {
            cout << 0 << '\n';
        }
    }

    return 0;
}

复杂度

设单个密码长度为 LL。

  • 时间：每个字符只扫描一次，O(L+128)=O(L)O(L + 128) = O(L)；总复杂度为全部密码字符数之和。
  • 空间：常数额外空间，O(1)O(1)。

总结

把文字规则拆成独立的布尔条件（三类字符是否齐全）和频次条件（是否出现超过两次），先完整统计再按高、中、低的包含关系逐级判断，就能避免漏判或重复判断。