Codeforces Round 913 (Div. 3)E 不进位各数位和与打表

发布时间:2024年01月14日

Problem - E - Codeforces

digsum(a)+digsum(b)+digsum(c)=digsum(n)

要点一:

当左边和发生进位,比如5+6 == 11,那么数位和会变小。其实下一位就是相加后对9取余,各数位和必定变小的。

要点二:

然后就是组合情况了:

我们输入的是n,也就是说我们需要把n拆成a,b,c

每个数位单独看,最后所有数位乘起来就可以(比如第一位的排列数乘以第二位的排列数)。

每一位有三个数相加,每个数可以是0~9

那么我们可以遍历所有情况,即打表:

int harr[10];
for (int i = 0; i <= 9; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int k = 0; k <= 9; k++)
			{
				if(i+j+k<10)
					harr[i + j + k]++;
			}
		}
	}

这里i j k分别代表a b c 某数位的数字,i+j+k就是该位的n啦

大于10即进位的情况就不要了。

这里遍历所有情况了,比如 1,2,0 ;2,1,0 ;0,2,1都是可以遍历到的。

打表结果(有人手搓):

一开始自己手搓了,没想到这种办法。。(搓完都忘记自己要干什么了)

//0   0 0 0
//    100 3种 ;110 3种 ,120 6种 ;111 1种 ,112 3种 ,123 6种
//    aaa组合 1 ;abb组合 3 ;abc组合 6 ;
//1   1 0 0
//2   2 0 0 , 1 1 0
//3   3 0 0 , 2 1 0 , 1 1 1
//4   4 0 0 , 3 1 0 , 2 2 0 , 2 1 1 
//5   5 0 0 , 4 1 0 , 3 2 0 , 3 1 1 , 2 2 1
//6   6 0 0 , 5 1 0 , 4 2 0 , 3 3 0 , 4 1 1 , 3 2 1 , 2 2 2
//7   7 0 0 , 6 1 0 , 5 2 0 , 4 3 0 , 5 1 1 , 4 2 1 , 3 3 1 , 3 2 2
//8   8 0 0 , 7 1 0 , 6 2 0 ,5 3 0 ,4 4 0 ,6 1 1 ,5 2 1 ,4 3 1 ,4 2 2 ,3 3 2
//9   9 0 0 ,8 1 0 ,7 2 0 ,6 3 0 ,5 4 0 ,7 1 1 ,6 2 1 ,5 3 1 ,4 4 1 ,5 2 2 ,
//    4 3 2 ,3 3 3
//0: 1
//1: 3
//2: 6
//3: 3 6 1 = 10  
//4: 3 6 3 3 = 15
//5: 3 6 6 3 3 = 21	//对应了前几个样例
//6: 3 6 6 3 3 6 1 = 28
//7: 3 6 6 6 3 6 3 3 = 36
//8: 3 6 6 6 3 3 6 6 3 3 = 45
//9: 3 6 6 6 6 3 6 6 3 3 6 1 = 55

文章来源:https://blog.csdn.net/JK01WYX/article/details/135586905
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。