http://www.ifrog.cc/acm/problem/1083
题意：比较好懂。注意答案的x不包含ax本身，所以才输出-1。
思路：离线处理。根据x排序，然后每次更新Hash[]数组就好了。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <string> 7 #include <iostream> 8 #include <stack> 9 #include <map> 10 #include <queue> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 #define N 100010 15 #define INF 0x3f3f3f3f 16 struct P { 17 int x, id; 18 } ask[N]; 19 int Hash[N], p[N], ans[N]; 20 21 bool cmpx(const P &a, const P &b) { if(a.x == b.x) return a.id < b.id; return a.x < b.x; } 22 23 int get(int num) { 24 int ans = 0; 25 while(num) { 26 ans += num % 10; 27 num /= 10; 28 } 29 return ans; 30 } 31 32 int main() 33 { 34 int t, cas = 1; 35 scanf("%d", &t); 36 while(t--) { 37 int n, q; 38 scanf("%d%d", &n, &q); 39 for(int i = 1; i <= n; i++) 40 scanf("%d", &p[i]); 41 for(int i = 1; i <= q; i++) { 42 scanf("%d", &ask[i].x); 43 ask[i].id = i; 44 } 45 sort(ask + 1, ask + q + 1, cmpx); 46 printf("Case #%d:\n", cas++); 47 memset(Hash, -1, sizeof(Hash)); 48 int j = 1, now; 49 for(int i = 1; i <= q; i++) { 50 while(ask[i].x > j && j <= n) { 51 now = get(p[j]); 52 Hash[now] = max(Hash[now], p[j]); 53 j++; 54 } 55 now = get(p[ask[i].x]); 56 if(Hash[now] == -1) ans[ask[i].id] = -1; 57 else ans[ask[i].id] = Hash[now]; 58 } 59 for(int i = 1; i <= q; i++) printf("%d\n", ans[i]); 60 } 61 return 0; 62 }