小红的密码修改【牛客tracker 每日一题】
小红的密码修改
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
已知合法的密码有以下要求：
- 长度在8 88到16 1616之间。
- 必须包含大写字母、小写字母、数字、特殊符号这四种字符。其中特殊符号只能是英文逗号、英文句号、英文问号和英文感叹号这四种。
小红准备修改她目前的密码，但她最多只会修改一个字符，因为修改多了小红就容易忘记她的密码。修改后需要满足是合法的密码。
小红想知道，她一共有多少种修改的方式？共有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;}