小红的密码修改【牛客tracker 每日一题】

小红的密码修改

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

已知合法的密码有以下要求：

1. 长度在8 88到16 1616之间。
2. 必须包含大写字母、小写字母、数字、特殊符号这四种字符。其中特殊符号只能是英文逗号、英文句号、英文问号和英文感叹号这四种。

小红准备修改她目前的密码，但她最多只会修改一个字符，因为修改多了小红就容易忘记她的密码。修改后需要满足是合法的密码。

小红想知道，她一共有多少种修改的方式？共有t tt次询问。

输入描述：

第一行输入一个正整数t tt，代表询问的次数。

接下来的t tt行，每行输入一个字符串。保证输入的字符串是一个合法的密码。

1 ≤ t ≤ 1 0 5 1≤t≤10^51≤t≤105

输出描述：

输出t tt行，每行输出一个整数，代表修改的方案数。

示例1

输入：

1 12345aB.

输出：

378

解题思路

输入的字符串为合法密码（长度8 − 16 8-168−16，包含大写字母、小写字母、数字、指定四种特殊符号各至少一个），首先统计这四类字符的数量；定义数组p = 25 , 25 , 9 , 3 p={25,25,9,3}p=25,25,9,3，分别对应每类字符仅存1 11个时，替换该类字符为同类型其他字符的可选数（避免替换后该类字符消失，导致密码不合法）；对于每类字符，若数量为1 11则累加p [ i ] p[i]p[i]到答案，否则累加该类字符数量乘以65 6565（所有合法字符的总数，此时替换任意合法字符都不会造成类别缺失）；最终累加的总和即为最多修改一个字符的合法方案数，该方法单次处理字符串的时间复杂度为O ( l e n ( s ) ) O(len(s))O(len(s))，适配t tt达1 e 5 1e51e5的规模，高效计算出结果。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;voidsolve(){string s;cin>>s;vector<ll>c(4,0),p={25,25,9,3};for(auto&ch:s){if(isupper(ch))c[0]++;// 当是大写字母时为真elseif(islower(ch))c[1]++;// 当是小写字母时为真elseif(isdigit(ch))c[2]++;// 当是数字是为真elsec[3]++;}ll ans=0;for(ll i=0;i<4;i++){if(c[i]==1)ans+=p[i];elseans+=c[i]*65;}cout<<ans<<endl;}intmain(){ll t;cin>>t;while(t--)solve();return0;}