)
题目描述
- 牛客小白月赛152E题 9运算
- 题解来自大神Kendieer
- 大神的牛客小白月赛125讲解
思路分析
C++代码展示
#include<bits/stdc++.h>#defineint__int128#definell__int128usingnamespacestd;inta1[100],a9[100];inlinellread(){ll x=0,f=0;charch=0;while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}returnf?(-x):x;}inlinevoidwrite(ll x){charnum[65];ll cnt=0;if(!x){putchar('0');return;}if(x<0){putchar('-');x=(-x);}while(x>0){num[cnt++]=x%10+'0';x/=10;}while(cnt>0){putchar(num[--cnt]);}}voidinit(){for(inti=1;i<=32;i++)a1[i]=a1[i-1]*10+1;for(inti=1;i<=32;i++)a9[i]=a1[i-1]*9;}voidsolve(){intans=1e35;intx=read();if(x%9==0){for(inti=1;i<=32;i++){if(a9[i]>=x){ans=min(ans,(a9[i]-x)/9);break;}}}for(inti=1;i<=32;i++){if(a9[i]-9*x>=0){intmiu=(a9[i]-9*x)/81;intlemuda=(a9[i]-81*miu-9*x)/9;inttemp=miu+lemuda+1;ans=min(ans,temp);}}write(ans);putchar('\n');}signedmain(){intT=read();init();while(T--)solve();return0;}AI代码注释
#include<bits/stdc++.h>#defineint__int128// 重定义int为__int128，处理超大数避免溢出#definell__int128// 别名，简化__int128的书写usingnamespacestd;// 全局数组：a1[i]存储i个1组成的数(如a1[3]=111)；a9[i]存储i个9组成的"好数字"(如a9[3]=999)inta1[100],a9[100];// 内联函数：读取__int128类型数字（cin/cout不支持__int128，手动实现）inlinellread(){ll x=0,f=0;// x存储数值，f标记是否为负数（本题x为正，f实际无作用）charch=0;// 跳过非数字字符while(!isdigit(ch)){f|=(ch=='-');// 若有负号，标记f=1ch=getchar();}// 逐位读取数字，计算数值（位运算优化：x*10 = x<<3 + x<<1）while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);// ch^48等价于ch-'0'，转字符为数字ch=getchar();}returnf?(-x):x;// 负数返回-x，正数返回x}// 内联函数：输出__int128类型数字（cin/cout不支持__int128，手动实现）inlinevoidwrite(ll x){charnum[65];// 存储数字的每一位字符（逆序）ll cnt=0;if(!x){// 特殊处理x=0的情况putchar('0');return;}if(x<0){// 处理负数（本题x为正，此分支无实际作用）putchar('-');x=(-x);}// 逐位拆分数字，存入num数组（逆序存储）while(x>0){num[cnt++]=x%10+'0';// x%10取最后一位，+ '0'转为字符x/=10;}// 逆序输出，恢复数字的正确顺序while(cnt>0){putchar(num[--cnt]);}}// 初始化函数：预处理生成a1和a9数组（32位以内的1序列和9序列）voidinit(){// 递推生成i个1组成的数：a1[1]=1, a1[2]=11, a1[3]=111...for(inti=1;i<=32;i++)a1[i]=a1[i-1]*10+1;// 递推生成i个9组成的"好数字"：a9[1]=9, a9[2]=99, a9[3]=999...for(inti=1;i<=32;i++)a9[i]=a1[i-1]*9;}// 核心解题函数：计算将x转为"好数字"的最少步数voidsolve(){intans=1e35;// 初始化最小步数为极大值（1e35远大于可能的最大步数）intx=read();// 读取当前测试用例的初始数字x// 场景1：不使用乘9操作，仅通过加9变为好数字if(x%9==0){// 前提：x必须是9的倍数（好数字都是9的倍数）// 枚举所有位数的好数字，找到第一个比x大的for(inti=1;i<=32;i++){if(a9[i]>x){// 计算加9步数：(好数字 - x)/9，更新最小步数ans=min(ans,(a9[i]-x)/9);break;// 第一个更大的好数字步数最少，无需继续枚举}}}// 场景2：使用1次乘9操作，再通过加9变为好数字for(inti=1;i<=32;i++){// 好数字需≥9*x（乘9后的数字），否则无法通过加9得到if(a9[i]-9*x>=0){// 拆分加9操作：miu是加81(9*9)的次数，lemuda是剩余加9的次数intmiu=(a9[i]-9*x)/81;intlemuda=(a9[i]-81*miu-9*x)/9;inttemp=miu+lemuda+1;// 总步数=加81次数+加9次数+1次乘9ans=min(ans,temp);// 更新最小步数}}write(ans);// 输出最小步数putchar('\n');// 换行分隔测试用例}// 主函数：处理多组测试用例signedmain(){intT=read();// 读取测试数据组数Tinit();// 预处理生成1序列和9序列数组while(T--)solve();// 逐组处理测试用例return0;}
