hdu 4351 Digital root

http://acm.hdu.edu.cn/showproblem.php?pid=4351

　　这题是一道稍微复杂的区间合并线段树，因为没有query，可以写成RMQ来降低query的复杂度。

　　题意不难理解，先解释一下所谓的数字的根是指一个数的各位数字和的各位数字和的各位数字和的各位数字和。。。。直到数只剩一位。数字根有一个性质，就是它如果是非0，最后必然是非0的数；如果这个数模9余d，d!=0，d就是数字根，d==0，数字根就是9。知道性质以后，题目给出一列数，要求求出给定的一个区间里所有子序列的和的数字根中最大的5个数字根，不包括重复的。这个题意可以直接由下面的hint看出。

　　解决这个问题需要对一个区间的子序列分类，让其可以进行区间合并的操作。例如，我在这题里面，将子序列分为不连接到左右两个端点的、连接到左（右）端点的，以及同时连接到两个端点（也就是整段区间）。这样，分别对它们操作，很容易就可以想到如何对任意给定区间进行合并，只是合并的操作相对繁琐罢了。如果像我这样做，区间中还得判断是否有0，以及是否全是0，这两种特殊情况。

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define lson l, m, rt << 1
  9 #define rson m + 1, r, rt << 1 | 1
 10 
 11 const int maxn = 1E5 + 5;
 12 struct Seg {
 13     bool left[9], right[9], mid[9];
 14     bool onlyZero, zero;
 15     int whole;
 16 } seg[maxn << 2];
 17 
 18 Seg up(Seg left, Seg right) {
 19     Seg ret;
 20 
 21     ret.zero = left.zero | right.zero;
 22     ret.onlyZero = left.onlyZero & right.onlyZero;
 23     ret.whole = (left.whole + right.whole) % 9;
 24     for (int i = 0; i < 9; i++) {
 25         ret.left[i] = left.left[i];
 26         ret.right[i] = right.right[i];
 27         ret.mid[i] = left.mid[i] | right.mid[i] | left.right[i] | right.left[i];
 28     }
 29     if (!left.onlyZero) ret.left[left.whole] = true;
 30     if (!right.onlyZero) ret.right[right.whole] = true;
 31     for (int i = 0; i < 9; i++) {
 32         int l = (left.whole + i) % 9, r = (right.whole + i) % 9;
 33 
 34         if (!left.onlyZero) ret.left[l] |= right.left[i];
 35         if (!right.onlyZero) ret.right[r] |= left.right[i];
 36         for (int j = 0; j < 9; j++) {
 37             ret.mid[(i + j) % 9] |= (right.left[i] & left.right[j]);
 38         }
 39     }
 40 
 41     return ret;
 42 }
 43 
 44 void build(int l, int r, int rt) {
 45     if (l == r) {
 46         memset(&seg[rt], 0, sizeof(Seg));
 47         scanf("%d", &seg[rt].whole);
 48         seg[rt].zero = seg[rt].onlyZero = !seg[rt].whole;
 49         seg[rt].whole %= 9;
 50         return ;
 51     }
 52     int m = (l + r) >> 1;
 53 
 54     build(lson);
 55     build(rson);
 56     seg[rt] = up(seg[rt << 1], seg[rt << 1 | 1]);
 57 }
 58 
 59 Seg query(int L, int R, int l, int r, int rt) {
 60     Seg ret;
 61 
 62     if (L <= l && r <= R) {
 63         return seg[rt];
 64     }
 65     int m = (l + r) >> 1;
 66 
 67     if (L <= m) {
 68         ret = query(L, R, lson);
 69         if (m < R) {
 70             ret = up(ret, query(L, R, rson));
 71         }
 72         return ret;
 73     }
 74     if (m < R) {
 75         return query(L, R, rson);
 76     }
 77 
 78     return ret;
 79 }
 80 
 81 int main() {
 82     freopen("in", "r", stdin);
 83     int T, n;
 84 
 85     scanf("%d", &T);
 86     for (int i = 1; i <= T; i++) {
 87         if (i != 1) puts("");
 88         scanf("%d", &n);
 89         build(1, n, 1);
 90 //        for (int j = 1; j < n << 2; j++) {
 91 //            printf("%d : %d\n", j, seg[j].whole);
 92 //            for (int k = 0; k < 9; k++) {
 93 //                printf("rest %d : %d %d %d\n", k, seg[j].left[k], seg[j].mid[k], seg[j].right[k]);
 94 //            }
 95 //            puts("~~");
 96 //        }
 97 //        puts("~~~~~~");
 98         printf("Case #%d:\n", i);
 99 
100         int m;
101 
102         scanf("%d", &m);
103         while (m--) {
104             int l, r;
105 
106             scanf("%d%d", &l, &r);
107 
108             Seg ans = query(l, r, 1, n, 1);
109             int cnt = 5;
110             bool pr = false;
111 
112             for (int t = 9; t >= 1; t--) {
113                 int ii = t % 9;
114 
115                 if (ans.left[ii] || ans.right[ii] || ans.mid[ii] || (ans.whole == ii && !ans.onlyZero)) {
116                     if (pr) {
117                         putchar(' ');
118                     }
119                     pr = true;
120                     printf("%d", t);
121                     cnt--;
122                 }
123                 if (cnt == 0) break;
124             }
125             if (cnt && ans.zero) {
126                     if (pr) {
127                         putchar(' ');
128                     }
129                     pr = true;
130                     putchar('0');
131                     cnt--;
132             }
133             while (cnt--) {
134                 if (pr) putchar(' ');
135                 pr = true;
136                 printf("-1");
137             }
138             puts("");
139         }
140     }
141 
142     return 0;
143 }

——written by Lyon