小R排数字【牛客tracker 每日一题】

小R排数字时间限制1秒 空间限制512M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小 R 是一只小猫。有一天她得到了一个正整数n nn且n nn在十进制表示下没有0 00不考虑前导零。小R RR太顽皮了以至于她将这个正整数n nn的数位重新排列为一个数也可以不做排列这样这个数依旧是n nn。现在小R RR的主人T TT想问问你小R RR重组的数字是否有可能是4 44的倍数。本题有多组询问你需要对每个询问都求出相应的结果。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 4 ) T(1≤T≤10^4)T(1≤T≤104)代表数据组数每组测试数据描述如下在一行上输入一个正整数n ( 1 ≤ n ≤ 10 9 ) n(1≤n≤10^9)n(1≤n≤109)代表初始数字。保证n nn十进制下没有0 00数位。输出描述对于每一组测试数据如果小R RR重组的数字有可能是4 44的倍数在单独的一行上输出Y E S YESYES否则直接输出N O NONO都是大写字母。示例1输入3 32123432 1354 552122输出YES NO YES说明对于第一组测试数据32 123 432 32 123 43232 123 432本身就是4 44的倍数。对于第二组测试数据我们可以证明1 354 1 3541 354无法通过重排数位变成4 44的倍数。对于第三组测试数据552 122 552 122552 122可以重排成122 552 122 552122 552它是4 44的倍数。解题思路本题是数论整除特性 枚举验证的基础应用题核心利用4的倍数的数位判定规律将重排问题简化为两位数的可行性校验。1. 核心数论依据一个整数能被4整除当且仅当它的最后两位组成的两位数能被4整除。原理任意整数均可拆分为100 × 高位部分 末两位而100是4的倍数高位部分对4取模恒为0因此整个数的整除性完全由末两位决定。2. 问题等价转化数位重排后能否得到4的倍数等价于能否从原数的数位中选出两个数位数字相同时需至少出现2次组成一个能被4整除的两位数。只要存在这样的两位数剩余数位可任意排列在高位整个数必然是4的倍数。3. 算法执行步骤数位计数逐位提取输入数字统计1~9每个数字出现的次数。枚举校验遍历所有两位的4的倍数从12到96步长为4对每个两位数若十位与个位数字不同检查两个数字的出现次数均≥1。若十位与个位数字相同检查该数字的出现次数≥2。只要存在一个满足条件的两位数即可判定答案为YES。边界处理若输入为一位数无法组成两位数直接判断其本身是否能被4整除。无符合条件所有两位数均无法用现有数位组成时输出NO。算法总时间复杂度为O ( T ) O(T)O(T)每组测试仅需常数次枚举校验可轻松处理1万组数据规模。总结核心逻辑利用4的倍数仅由末两位决定的特性将全排列问题降维为两位数可行性校验通过数位计数快速验证。关键操作末两位整除规律、数位频次统计、枚举两位4的倍数、计数合法性校验。效率保障单组测试为常数级运算万级数据量下运行开销极低。代码简要说明solve单组处理函数若输入数字≤10一位数直接对4取模判断输出对应YES/NO。通过循环取模逐位提取数字统计每个数位的出现次数存入cnt数组。从12开始步长4遍历所有两位4的倍数对每个候选数临时扣减十位和个位的计数若扣减后均非负则说明数位充足立即输出YES并返回否则回溯计数继续校验。遍历完所有候选仍无合法解输出NO。主函数逻辑读取测试组数T循环调用solve处理每组用例。输入优化关闭流同步并解绑tie大幅提升多组数据的读取速度。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n;cinn;if(n10){if(n%4)coutNO\n;elsecoutYES\n;return;}vectorllcnt(10,0);for(ll in;i;i/10)cnt[i%10];vectorllf;for(ll i12;i100;i4)f.emplace_back(i);for(ll i0;i(ll)f.size();i){ll tf[i];cnt[t/10]--;cnt[t%10]--;if(cnt[t/10]0cnt[t%10]0){coutYES\n;return;}cnt[t/10];cnt[t%10];}coutNO\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;cinT;while(T--)solve();return0;}