题目链接：http://www.ifrog.cc/acm/problem/1083?contest=1010&no=4
题目大意：T组 给定n个数和q个询问， 问从a1 到 a（x - 1）是否有位数和与ax相同的， 如果有 输出最大的那个数
数据范围： T≤5 (1≤n≤100000) and q(1≤q≤100000) (1≤ai≤109)
解题思路： 看数据范围就知道不能On^2的扫， 肯定T ， 就想到了用数组存 开一个二维数组pos[x][y] 表示第ax之前位数和为y的数的最大值位置， 因为n< 1e9 所以y开100就够， 刚开始开了200结果 内存超了。。。
第i个的所有pos 就有i - 1的pos 更新过来， 再看i - 1 的位数和是否需要更新， 最后就可以O（1）输出了
总结： 数组开到刚刚好就好， 不要没事开那么大 第一次因为开大了WA了一发， 比赛的时候如果错了，， 代码也找不出问题 多读几遍题， 可能是哪个条件漏了。。 今天就因为没看到最大值 直接更新 一直错，， 最后半个小时重新读了一遍题 就知道错哪了 判断一下再更新
最后附上代码
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdlib> 5 #include<cmath> 6 using namespace std; 7 const int MaxN = 1e5; 8 int n, q, T; 9 int num[MaxN + 5]; 10 int sum[MaxN + 5]; 11 int pos[MaxN + 5][105]; 12 int main() 13 { 14 scanf("%d", &T); 15 int t = T; 16 while(T--) 17 { 18 memset(num, 0, sizeof(num)); 19 memset(sum, 0, sizeof(sum)); 20 memset(pos, 0, sizeof(pos)); 21 scanf("%d %d", &n, &q); 22 for(int i = 1; i <= n; i++) 23 scanf("%d", &num[i]); 24 for(int i = 1; i <= n; i++){ 25 int temp = num[i]; 26 while(temp != 0) 27 { 28 int ans = temp % 10; 29 sum[i] += ans; 30 temp /= 10; 31 } 32 } 33 for(int i = 2; i <= n; i++){ 34 for(int j = 1; j <= 100; j++) 35 pos[i][j] = pos[i - 1][j]; 36 if(num[i - 1] > num[pos[i][sum[i - 1]]]) 37 pos[i][sum[i - 1]] = i - 1; 38 } 39 printf("Case #%d: ", t - T); 40 for(int i = 1; i <= q; i++){ 41 int a; 42 scanf("%d", &a); 43 if(pos[a][sum[a]]) 44 printf("%d ",num[pos[a][sum[a]]]); 45 else printf("-1 "); 46 } 47 } 48 return 0; 49 }