Digital root
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)
Total Submission(s): 575 Accepted Submission(s): 164
Problem Description
The digital root (also repeated digital sum) of a number is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process
continues until a single-digit number is reached.
For example, the digital root of 65536 is 7, because 6+5+5+3+6=25 and 2+5=7.
The digital root of an interval is digital root of the sum of all numbers in that interval.
continues until a single-digit number is reached.
For example, the digital root of 65536 is 7, because 6+5+5+3+6=25 and 2+5=7.
The digital root of an interval is digital root of the sum of all numbers in that interval.
Consider a sequence A1,A2,A3……An, your task is to answer some queries[l,r]. For each query, tell the biggest five different digital roots among all continuous subintervals of interval[l,r]
Input
In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 10) Then T cases follows. For each test case, the first line is an integer n indicating the length of sequence(1<=n<=100000); following
one line containing n integer Ai(0<=Ai<=1000000000); the third line is an integer Q indicating the number of queries(1<=Q<=100000); following Q lines, each line indicating one query [l,r],(1<=l<=r<=n).
one line containing n integer Ai(0<=Ai<=1000000000); the third line is an integer Q indicating the number of queries(1<=Q<=100000); following Q lines, each line indicating one query [l,r],(1<=l<=r<=n).
Output
For each test case, first you should print "Case #x:" in a line, where x stands for the case number started with 1. Then for each query output a line contains five integer indicating the answers(if the kind of digital root is smaller
than five, output -1 to complete). Leave an empty line between test cases.
than five, output -1 to complete). Leave an empty line between test cases.
Sample Input
1 5 101 240 331 4 52 3 1 3 4 5 1 5
Sample Output
Case #1: 8 7 6 4 2 7 4 2 -1 -1 9 8 7 6 4HintFor the first query, [1,3] has six subintervals: [1,1],[2,2],[3,3],[1,2],[2,3],[1,3]. Interval sums are 101,240,331,341,571,672, correspondence digital roots are 2,6,7 ,8,4,6,the most biggest five are 8,7,6,4,2
题意：
一个数 假如 ４６７ 那么变换为一位数的过程为本4+6+7=17 1+7=8
输入一堆数 对于每一个query 输入left right 求left 到right 的区间的各个子串的和 这些和 对应变换成一位数
输出其中最大的５个 如果不够５个 就用-1填充
/*
变换过程:
num= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ......... 100 101 102 103 ....
root=0 1 2 3 4 5 6 7 8 9 1 2 3 4 .......1 2 3 4....
可以归纳出规律
root=(num-1)%9+1
之后暴力出区间内的连续字串相加的和sum 求出只有一位的数
另外在暴力过程中 如果找到了 9 8 7 6 5 这5个后就没有必要循环了 直接退出循环即可
防止超时
*/
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;
int n,a,used[10];
__int64 sum[100000+100];
int main()
{
int i,j,cas,opr,left,right,cnt,cnt1,t,count=0,flag;
__int64 num;
scanf("%d",&cas);
for(t=1;t<=cas;t++)
{
printf("Case #%d:\n",t);
scanf("%d",&n);
sum[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a);
sum[i]=sum[i-1]+a;
}
scanf("%d",&opr);
while(opr--)
{
cnt=0;count=0;flag=0;
memset(used,0,sizeof(used));
scanf("%d %d",&left,&right);
for(i=left-1;i<right;i++)
{
for(j=1;j<=right-left+1;j++)
{
if(i+j<=right)
{
if(used[9]&&used[8]&&used[7]&&used[6]&&used[5]) flag=1;//防止超时
if(flag==1) break;
num=sum[i+j]-sum[i];
num=(num-1)%9+1;//规律
if(!used[num])
{
used[num]=1;
cnt++;
}
}
}
if(flag)
break;
}
if(flag)
{
printf("9 8 7 6 ");
printf("5\n");
continue;
}
cnt1=0;
if(cnt<5)
{
for(i=9;i>=0;i--)
if(used[i]) printf("%d ",i);
for(i=cnt;i<4;i++)
printf("-1 ");
printf("-1\n");
}
else
{
for(i=9;i>=0&&cnt1<4;i--)
if(used[i])
{
printf("%d ",i);
cnt1++;
}
for(i;i>=0;i--)
if(used[i])
{
printf("%d\n",i);
break;
}
}
}
if(t!=cas) printf("\n");
}
return 0;
}