题目描述
一个数字的数字根定义为:这个数字每一位的数字加起来求和,反复这个过程直到和小于10。例如,64357的数字跟为7,因为6+4+3+5+7=25,2+5=7个区间的数字根定义为这个区间所有数字和的数字根。
给定一个序列A1,A2,A3,…,An,你需要回答一些询问。每一个询问给定个区间[L,R],求出这个区间所有连续子区间里最大的前5个不同的数字根，不够5个的用-1补全
输入输出格式
输入格式：
第一行一个整数N,表示序列的长度。第二行是N个整数Ai(0≤Ai<10^9)。第三行是一个整数Q表示询问次数。接下来Q行,每一行两个正整数1,r,表示询问区间。(1≤l≤r≤N)
输出格式：
Q行,表示每一个查询区间所有连续子区间里最大的前5个不同的数字根,按降序输出,输出用空格隔开。
输入输出样例
输入样例#1：
5
101 240 331 4 52 3 1 3 4 5 1 5
输出样例#1：
8 7 6 4 2 7 4 2 -1 -1 9 8 7 6 4
说明
样例解释
第一个查询区间[1,3],它的连续子区间有[1,1],[2,2],[3,3],[1,2],[2,3],[1,3].可对应的数字根分别为2,6,7,8,4,6。所以最大的5个是8,7,6,4,2。
数据范围
30%的数据，N ≤ 1000; Q ≤ 1000
100%的数据，N ≤ 100000; Q ≤ 100000
解法
感觉懂了数字根是什么就会做这个题了。（我去征求VANE的意见时，发现他也不懂数字根，他和我说要记忆化搜索……）
（虽然我也不懂，问了百度。）
结论就是 数字根=各位加在一起%9 (如果是0就=9)
现在有了思路，以后有了证明再补吧。
于是就预处理前缀和，暴力枚举[L,R]内的子区间，因为答案只有0~9，而且只要求你输出前5个，当你已经找到5，6，7，8，9时就可以退出了，
所以这么暴力的做法是超不了时的
#include<bits/stdc++.h> #define MAXN 100005 using namespace std; int read(){ int x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){x+=c-'0';c=getchar();} return x; } int N,Q,l,r,a[MAXN],s[MAXN]; bool b[10]; void query(){ memset(b,0,sizeof b); int k=5; l=read(),r=read(); for(int i=l;i<=r;i++) for(int j=i;j<=r;j++){ int tmp=(s[j]-s[i-1])%9; tmp?b[tmp]=1:b[9]=1; if(b[9]&&b[8]&&b[7]&&b[6]&&b[5]){ printf("9 8 7 6 5 "); return ; } } for(int i=9;i>=1;i--) if(k&&b[i])printf("%d ",i),k--; for(int i=1;i<=k;i++)printf("-1 "); printf(" "); } int main() { N=read(); for(int i=1;i<=N;i++) a[i]=read(),s[i]=s[i-1]+a[i]; Q=read(); while(Q--)query(); return 0; }