首页 > 代码库 > hdoj 4901 The Romantic Hero DP hdoj 4902 Nice boat 线段树
hdoj 4901 The Romantic Hero DP hdoj 4902 Nice boat 线段树
惨遭丽洁乱虐。。这一场也是比得乱七八糟的，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同一个数两次相当于xor028 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。