BSG白山极客挑战赛 A-数数字 (模拟)

来源:互联网 发布:怎么用vs2013写c语言 编辑:IT博客网 时间:2019/12/06 11:46

数数字
System Message (命题人)
yule_z (测试)
基准时间限制:1 秒 空间限制:262144 KB 分值: 20

统计一下 aaa  aaana × b 的结果里面有多少个数字d,a,b,d均为一位数。

样例解释:

3333333333*3=9999999999,里面有10个9。


Input
多组测试数据。第一行有一个整数T,表示测试数据的数目。(1≤T≤5000)接下来有T行,每一行表示一组测试数据,有4个整数a,b,d,n。 (1≤a,b≤9,0≤d≤9,1≤n≤10^9)
Output
对于每一组数据,输出一个整数占一行,表示答案。
Input示例
23 3 9 103 3 0 10
Output示例
100
分析:
刚开始就根据题目要求用数组去模拟计算,说知道样例过了,一组测试数据都过不了,后来好不容易找到了一点规律,也就过了三组测试数据,所以没办法,继续找规律,最后发现可以分为三种:
1、n=1,最多会出现两位数字,处理即可;
2、n!=1,但a*b<10,也不需要进位处理,而且所有位上的数字都一样;
3、排除了所有的特殊数据,就要老老实实进位运算了,但是随着位数增多,其中一定会有相同的数字,无需循环,就可得出,如果数据本身不会重复,我们也要计算到重复才跳出,我们可以把多乘的减去;

#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <map>#include <stack>#include <vector>#include <list>#include <iostream>#include <algorithm>using namespace std;long long num[10], sum[100];int main(){    int t, a, b, d, n;    scanf("%d", &t);    while (t--)    {        memset(num, 0, sizeof(num));        memset(sum, 0, sizeof(sum));        scanf("%d%d%d%d", &a, &b, &d, &n);        if (n == 1)        {            a *= b;            while (a)//循环得到它的每一位的数量            {                sum[a % 10]++;                a /= 10;            }            printf("%lld\n", sum[d]);        }        else if ( a * b < 10)//如果相乘后无需进位,那么只有一种数字        {            sum[a * b] = n;            printf("%lld\n", sum[d]);        }        else        {            int jin = 0;//进位初始化为0            num[0] = -1;//不能初始化为0,因为还可能统计0的个数            for (int i = 1; ; i++)            {                num[i] = a * b + jin;//进位处理                jin = num[i] / 10;                num[i] %= 10;                sum[num[i]]++;                if (num[i] == num[i - 1])//统计中间相同数字的数量                {                    sum[num[i]] += n - i;//如果乘的过多,也可再减回去                    break;//不再循环判断,循环可能会超时                }            }            sum[jin]++;//第一位的数字次数加1            printf("%lld\n", sum[d]);        }    }    return 0;}



0 0