线段树，虽然没接触过也不太懂，但实用价值好像还蛮大的。
View Code
/* 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 4 Hint For 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 hdu 4351 Digital root http://acm.hdu.edu.cn/showproblem.php?pid=4351 线段树 每个节点保存前缀 后缀 和 剩余情况 中（k）(0<=k<=9) 是否出现 除了叶子节点外 其它节点要用左右孩子 来维护 求答案时类似 维护的过程中有重复的计算 需要用打表和位运算来优化 否则超时 注意0的情况 代码及其注释： */ ///求各位上的和为多少就是除以9取余 #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<stack> #include<cmath> #define LL long long using namespace std; const int N=100005; struct node { int l,r,root;//root 为这一段总起来的 结果 int lt,rt,mt;//前缀 后缀 和其它情况 中k（0--9）是否出现 用二进制表示 } mem[N*4]; struct tt//同上 { int lt,rt,mt,root; } ans[N*4]; int mul[1024][1024];//将 i 和 j 两种情况合并 int a[N]; inline int Froot(int x)//只能处理小于等于18的情况 { if(x>9) return x-9; return x; } void begin()//打表 来优化时间 否则超时 { for(int x=1; x<1024; ++x) for(int y=1; y<1024; ++y) { mul[x][y]=0; for(int i=0; i<=9; ++i) { if(x&(1<<i)) for(int j=0; j<=9; ++j) if(y&(1<<j)) mul[x][y]=(mul[x][y]|(1<<Froot(i+j))); } } } void updatemem(int x)//维护x 的前缀 后缀 等信息 { mem[x].root=mul[ mem[ x<<1 ].root ][ mem[ x<<1|1 ].root ];//root 是左右子树 root 的 更新 mem[x].rt=(mem[ x<<1|1 ].rt | (mul[ mem[ x<<1 ].rt ][ mem[ x<<1|1 ].root]));//后缀由 右子树后缀 左子树后缀+右子树全部来更新 mem[x].lt=(mem[ x<<1 ].lt | (mul[ mem[ x<<1|1 ].lt ][ mem[ x<<1 ].root ]));//前缀由 左子树前缀 右子树前缀+左子树全部来更新 mem[x].mt=(mem[ x<<1 ].mt | mem[ x<<1|1 ].mt | (mul[ mem[ x<<1 ].rt ][ mem[ x<<1|1 ].lt ]));//其它 由 左子树其它 右子树其它 左子树后缀+右子树前缀更新 } void updateans(int x)//同上 { ans[x].root=mul[ ans[ x<<1 ].root ][ ans[ x<<1|1 ].root ]; ans[x].rt=(ans[ x<<1|1 ].rt | (mul[ ans[ x<<1 ].rt ][ ans[ x<<1|1 ].root])); ans[x].lt=(ans[ x<<1 ].lt | (mul[ ans[ x<<1|1 ].lt ][ ans[ x<<1 ].root ])); ans[x].mt=(ans[ x<<1 ].mt | ans[ x<<1|1 ].mt | (mul[ ans[ x<<1 ].rt ][ ans[ x<<1|1 ].lt ])); } void build(int x,int l,int r)//建树 { mem[x].l=l; mem[x].r=r; if(l==r) { mem[x].lt=1<<a[l];//初始化 mem[x].rt=1<<a[l]; mem[x].mt=1<<a[l]; mem[x].root=1<<a[l]; // cout<<">>>build:"<<mem[x].root<<" "<<mem[x].rt<<" "<<mem[x].lt<<" "<<mem[x].mt<<endl; return ; } int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); updatemem(x);//更新 } void Fans(int x,int l,int r) { if(mem[x].l==l&&mem[x].r==r) { ans[x].lt=mem[x].lt;//答案搜索边界 ans[x].rt=mem[x].rt; ans[x].mt=mem[x].mt; ans[x].root=mem[x].root; return ; } int mid=(mem[x].l+mem[x].r)>>1; if(mid<l) { Fans(x<<1|1,l,r);//只在右子树 传结果上来 ans[x].lt=ans[x<<1|1].lt; ans[x].rt=ans[x<<1|1].rt; ans[x].mt=ans[x<<1|1].mt; ans[x].root=ans[x<<1|1].root; } else if(mid>=r) { Fans(x<<1,l,r); ans[x].lt=ans[x<<1].lt; ans[x].rt=ans[x<<1].rt; ans[x].mt=ans[x<<1].mt; ans[x].root=ans[x<<1].root; } else { Fans(x<<1,l,mid); Fans(x<<1|1,mid+1,r); updateans(x);//左右都有 更新 } } int main() { //freopen("data.txt","r",stdin); begin(); int T; scanf("%d",&T); for(int c=1; c<=T; ++c) { int n; scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d",&a[i]); if(a[i]<=18) a[i]=Froot(a[i]); else//注意很大的情况 { a[i]=a[i]%9; if(a[i]==0) a[i]=9; } } build(1,1,n); int q; scanf("%d",&q); printf("Case #%d:\n",c); while(q--) { int l,r; scanf("%d %d",&l,&r); Fans(1,l,r); int a=(ans[1].lt|ans[1].rt|ans[1].mt); int k=0; for(int i=9; k<5&&i>=0; --i) { if(a&(1<<i)) { printf("%d",i); ++k; if(k<5) printf(" "); } } while(k<5) { printf("-1"); ++k; if(k<5) printf(" "); } printf("\n"); } if(c<T) printf("\n"); } return 0; }
无意中看到网上有人这题用技巧过了，数字1~9不大。
View Code
/* hdu 4351 Digital root http://acm.hdu.edu.cn/showproblem.php?pid=4351 变换过程: 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<string.h> #include<queue> #include<iostream> 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; #ifndef ONLINE_JUDGE cout<<"sum["<<i<<"]:"<<sum[i]<<endl; #endif } 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;//规律 #ifndef ONLINE_JUDGE cout<<num<<endl; #endif 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; }
题意看着不难的，一般方法肯定超时。
Digital root
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)
Total Submission(s): 1287 Accepted Submission(s): 421
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.
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).
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.
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 4
Hint
For 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