惨遭丽洁乱虐。。这一场也是比得乱七八糟的，4902本是丽洁定义比较难的题，结果数据随机的，被许多暴力水过了。。4905考察的是四边形不等式优化，但是这道题的dp方程实际上不满足该优化的条件。。朴素的o(n^3)会超时，所以这题目前是没有正解了。。我还写了个这题的贪心，强度挺高，可以对大概一半数据，错的误差也只有个位数，还揪出官方第五个数据。。朴素dp和贪心跑这个数据都比官方数据多了1，也就证明这题不满足四边形不等式优化的条件。。
http://acm.hdu.edu.cn/showproblem.php?pid=4901
看到每个数在0到1023，启发了dp思路。我们记录前i个数用xor组成0-1023的方案数，对应地乘上第i个数以后用and组成0-1023的方案数，累加即是答案。这样会有重复的问题，所以需要多开一个数组辅助。
f[i][j]是前i个数xor组成j的方案数，而且是必须取第i个数，这样保证S的子集不会重复计算，g[i][j]是前i个数xor组成j的方案数，h[i][j]是第i个数及以后and组成j的方案数。ans=ΣΣf[i][j]*h[i+1][j]即是答案。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const long long mo = (long long)1e9 + 7; 7 int n, T; 8 int a[1100]; 9 long long f[1100][1100], g[1100][1100], h[1100][1100]; 10 int main() 11 { 12 scanf("%d", &T); 13 while(T--) 14 { 15 scanf("%d", &n); 16 for (int i = 0; i < n; i++) scanf("%d", a+i); 17 memset(f, 0, sizeof(f)); 18 memset(g, 0, sizeof(g)); 19 memset(h, 0, sizeof(h)); 20 for (int i = 0; i < n-1; i++){ 21 f[i][a[i]] ++; 22 if (i == 0){ 23 g[i][a[i]] ++; 24 continue; 25 } 26 for (int j = 0; j < 1024; j++) 27 f[i][j] = (f[i][j] + g[i-1][j^a[i]]) % mo; //xor同一个数两次相当于xor0 28 for (int j = 0; j < 1024; j++) 29 g[i][j] = (g[i-1][j] + f[i][j]) % mo; 30 } 31 for (int i = n-1; i > 0; i--){ 32 h[i][a[i]] ++; 33 if (i == n-1) continue; 34 for (int j = 0; j < 1024; j++) 35 h[i][j&a[i]] = (h[i][j&a[i]] + h[i+1][j]) % mo; //但是and不行。。和上面xor一样地写导致wa了几次。。 36 for (int j = 0; j < 1024; j++) 37 h[i][j] = (h[i][j] + h[i+1][j]) % mo; 38 } 39 long long ans = 0; 40 for (int i = 0; i < n-1; i++) 41 for (int j = 0; j < 1024; j++) 42 if (f[i][j] > 0) 43 ans = (ans + f[i][j] * h[i+1][j]) % mo; 44 printf("%lld\n", ans); 45 } 46 return 0; 47 }
http://acm.hdu.edu.cn/showproblem.php?pid=4902
一只线段树，因为第一种操作是区间修改所有数为同一个数，打个标签，对于有标签的区间，第二种操作就只需要对一个数进行处理了。数据比较水，然后就水过了，丽洁的题解和标程我也看不太懂。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 struct tree{ 7 int maxn; 8 bool flag; 9 }t[101000 << 2]; 10 int T, n, q; 11 int a[101000]; 12 void pushup(int x) 13 { 14 t[x].maxn = max(t[x<<1].maxn, t[x<<1|1].maxn); 15 } 16 void pushdown(int x) 17 { 18 if (t[x].flag){ 19 t[x].flag = false; 20 t[x<<1].maxn = t[x<<1|1].maxn = t[x].maxn; 21 t[x<<1].flag = t[x<<1|1].flag = true; 22 } 23 } 24 void build(int x, int l, int r) 25 { 26 t[x].flag = false; 27 if (l == r){ 28 t[x].flag = true; 29 t[x].maxn = a[l]; 30 return; 31 } 32 int mid = l + r >> 1; 33 build(x<<1, l, mid); 34 build(x<<1|1, mid+1, r); 35 pushup(x); 36 } 37 void update(int x, int l, int r, int s, int e, int v) 38 { 39 if (s <= l && r <= e){ 40 t[x].flag = true; 41 t[x].maxn = v; 42 return; 43 } 44 pushdown(x); 45 int mid = l + r >> 1; 46 if (s <= mid) 47 update(x<<1, l, mid, s, e, v); 48 if (e > mid) 49 update(x<<1|1, mid+1, r, s, e, v); 50 pushup(x); 51 } 52 void trans(int x, int l, int r, int s, int e, int v) 53 { 54 if (t[x].maxn <= v) return; 55 if (s <= l && r <= e && t[x].flag){ 56 t[x].maxn = __gcd(t[x].maxn, v); 57 return; 58 } 59 if (l == r){ 60 t[x].maxn = __gcd(t[x].maxn, v); 61 return; 62 } 63 pushdown(x); 64 int mid = l + r >> 1; 65 if (s <= mid) 66 trans(x<<1, l, mid, s, e, v); 67 if (e > mid) 68 trans(x<<1|1, mid+1, r, s, e, v); 69 pushup(x); 70 } 71 int query(int x, int l, int r, int p) 72 { 73 if (t[x].flag) return t[x].maxn; 74 int mid = l + r >> 1; 75 if (p <= mid) return query(x<<1, l, mid, p); 76 else return query(x<<1|1, mid+1, r, p); 77 } 78 int main() 79 { 80 scanf("%d", &T); 81 while(T--) 82 { 83 scanf("%d", &n); 84 for (int i = 1; i <= n; i++) 85 scanf("%d", a+i); 86 build(1, 1, n); 87 scanf("%d", &q); 88 int type, l, r, x; 89 for (int i = 0; i < q; i++){ 90 scanf("%d %d %d %d", &type, &l, &r, &x); 91 if (type == 1) 92 update(1, 1, n, l, r, x); 93 else 94 trans(1, 1, n, l, r, x); 95 } 96 for (int i = 1; i <= n; i++) 97 printf("%d ", query(1, 1, n, i)); 98 puts(""); 99 } 100 return 0; 101 }
顺便把4905贪心贴出来吧，虽然过不了题= = 策略是优先合并相同的数（且不为0，比如0 0 5），然后合并gcd最大的数。说不定优化优化有朝一日会变成正解？= =。。
啊妈蛋刚才发现这道题都被下架了。。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 8 long long ans; 9 int T, n; 10 int a[3010]; 11 int gcd(int a, int b) 12 { 13 if (b == 0) return a; 14 return gcd(b, a % b); 15 } 16 int main() 17 { 18 scanf("%d", &T); 19 while(T--) 20 { 21 ans = 0; 22 scanf("%d", &n); 23 for (int i = 1; i <= n; i++){ 24 scanf("%d", a+i); 25 ans = ans + a[i]; 26 } 27 int tot = n; 28 for (int i = 1; i <= n-1; i++){ 29 int j, pos, tmp, tmp1; 30 for (j = 1; j <= tot-1; j++) 31 if (a[j] == a[j+1] && a[j] != 0) break; 32 if (j == tot){ 33 tmp = 0; 34 for (j = 1; j <= tot-1; j++){ 35 tmp1 = gcd(a[j], a[j+1]); 36 if (tmp1 > tmp){ 37 tmp = tmp1; 38 pos = j; 39 } 40 } 41 j = pos; 42 } 43 else tmp = a[j]; 44 ans = ans + tmp; 45 a[j] = tmp; 46 for (int k = j+1; k < tot; k++) 47 a[k] = a[k+1]; 48 tot --; 49 } 50 printf("%lld\n", ans); 51 } 52 return 0; 53 }
hdoj 4901 The Romantic Hero DP hdoj 4902 Nice boat 线段树,布布扣,bubuko.com
hdoj 4901 The Romantic Hero DP hdoj 4902 Nice boat 线段树
原文：http://www.cnblogs.com/james47/p/3884305.html