专栏文章

Solution-CF2109C3

CCaiZi
CF2109C3题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip6ajsd
此快照首次捕获于
2025/12/03 06:51
3 个月前
此快照最后确认于
2025/12/03 06:51
3 个月前
查看原文
有大神拿这题做儿童节游园会小游戏，所以写篇题解。
C2 题解。
既然 C2 要求是 44 次，那么我们可以先尝试 33 次操作，再尝试 22 次操作（11 次操作显然不可行）。
考虑 C2 有哪次操作可以不用，显然最后 11 次操作优化不掉，那就只能优化前 33 次操作，我们希望第 11 次操作乘上某个数后，只用 11 次 digit 就可以得到一个确定的数。
我们乘法最大可以乘 10910^9，不妨尝试一下 99 的倍数，发现没有结论。然后尝试一下 99 个 99 组成的数，即 109−110^9-1。可以发现： (109−1)x=109x−x=109(x−1)+109−x=[109(x−1)]+[(109−1)−(x−1)]\begin{aligned}(10^9-1)x&=10^9x-x\\&=10^9(x-1)+10^9-x\\&=[10^9(x-1)]+[(10^9-1)-(x-1)]\end{aligned} 令 x−1=a1⋯a9‾x-1=\overline{a_1\cdots a_9}，那么 (109−1)x=a1⋯a9(9−a1)⋯(9−a9)‾(10^9-1)x=\overline{a_1\cdots a_9(9-a_1)\cdots(9-a_9)}。
于是 S((109−1)x)=a1+(9−a1)+⋯+a9+(9−a9)=9×9=81S((10^9-1)x)=a_1+(9-a_1)+\cdots+a_9+(9-a_9)=9\times9=81。
于是现在我们找到了 33 次操作的做法。对于 n=81n=81 可以略去最后 11 次操作，只需要 22 次操作。那么有没有什么其他的 nn 是只需要 22 次操作就可以得到的呢？
假设存在 a≠109−1a\ne10^9-1 使得 S(ax)=n0S(ax)=n_0，取 x=109−1x=10^9-1，由上面的结论可以知道 S(ax)=81S(ax)=81。而我们再取 x=1x=1，S(ax)=S(a)S(ax)=S(a)，只有取 a=109−1a=10^9-1 才能使 S(a)=81S(a)=81。于是我们证明了只有 n=81n=81 是只需要 22 次操作就可以得到的。
最终答案：
CPP
if(n==81){
	cout<<"mul 999999999\n";
	cout<<"digit\n";
}
else{
	cout<<"mul 999999999\n";
	cout<<"digit\n";
	cout<<"add"<<n-81<<"\n";
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...