dango

POJ2750 Potted Flower(线段树区间更新)

传送门： http://poj.org/problem?id=2750

题目大意：
一堆花围成一圈，每一盆都有自己的attractive value。要你来选一串花，使得总attractive value最大。（题目中有一个非常重要的条件：不可以选所有的花，这个一不注意就功亏一篑了）
每次，有一只坏猫会来把第A盆花的attractive value换成B。坏猫每捣蛋一次，你就要求一个新的总attractive value最大的连续序列。

解题思路：
数据那么大，暴力搞肯定超时了，这种区间最大最小值的问题首先还是应该要想到线段树的。

1 struct tnode 
2 {
3     int sum,mins,maxs;      //当前区间的和、最小子序列和、最大子序列和 
4     int lmin,lmax;          // 当前区间从left出发所能形成的 最小子序列和、最大子序列和 
5     int rmin,rmax;          // 当前区间以right结尾所能形成的 最小子序列和、最大子序列和
6     //int minn;           //当前区间最大最小值 
7 }t[maxn*4];

线段树的节点定下来以后写法差不多也就定了。
每次需要根据孩子的情况来更新父节点的各种值。判断的时候一定要把“转移”（这个挺像动态规划的状态转移的其实……）情况都想齐全，再下手写，写的时候比较容易晕，一定要仔细，避免查错的时候头昏脑胀。
WA了一次，有一个地方没写好。题中说不可以选取所有的花，所以若得到的总attractive value最大的连续序列是整圈的花，就要剪掉整圈花总attractive value最小的连续序列的attractive value和，WA的时候之剪了最小attractive value的一盆花。

代码：（注释掉的一些地方是第一次错的地方，引以为戒~）

POJ2750
 1 #include <cstdio>
 2 #include <cstdlib>
 3 #define maxn 100010
 4 
 5 struct tnode 
 6 {
 7     int sum,mins,maxs;      //当前区间的和、最小子序列和、最大子序列和 
 8     int lmin,lmax;          // 当前区间从left出发所能形成的 最小子序列和、最大子序列和 
 9     int rmin,rmax;          // 当前区间以right结尾所能形成的 最小子序列和、最大子序列和
10     //int minn;           //当前区间最大最小值 
11 }t[maxn*4];
12 
13 int data[maxn];// 存放输入数据 
14 int n,m;// 点数、修改次数 
15 
16 int min(int a, int b, int c, int d, int e){
17     int ret=(a<b)?a:b;
18     ret=(ret<c)?ret:c;
19     ret=(ret<d)?ret:d;
20     ret=(ret<e)?ret:e;
21     return ret;
22 }
23 int max(int a, int b, int c, int d, int e){
24     int ret=(a>b)?a:b;
25     ret=(ret>c)?ret:c;
26     ret=(ret>d)?ret:d;
27     ret=(ret>e)?ret:e;
28     return ret;
29 }
30 int min2(int a, int b){
31     if (a<b) return a; else return b;
32 }
33 int max2(int a, int b){
34     if (a>b) return a; else return b;
35 }
36 
37 void update(int k){
38     int lson=k<<1, rson=(k<<1)+1;
39     t[k].sum = t[lson].sum+t[rson].sum;
40     t[k].lmax = max2(t[lson].sum+t[rson].lmax, t[lson].lmax);
41     t[k].lmin = min2(t[lson].sum+t[rson].lmin, t[lson].lmin);
42     t[k].rmax = max2(t[rson].sum+t[lson].rmax, t[rson].rmax);
43     t[k].rmin = min2(t[rson].sum+t[lson].rmin, t[rson].rmin);
44     t[k].mins=min(t[lson].mins, t[rson].mins,
45                   t[lson].rmin+t[rson].lmin, t[k].rmin, t[k].lmin);
46     t[k].maxs=max(t[lson].maxs, t[rson].maxs, 
47                   t[lson].rmax+t[rson].lmax, t[k].rmax, t[k].lmax);
48     //t[k].minn= min2(t[lson].minn, t[rson].minn);
49 }
50 
51 void buildtree(int k, int l, int r){
52     if (l==r){
53         t[k].sum=t[k].mins=t[k].maxs=data[l];
54         t[k].lmin=t[k].rmin=t[k].lmax=t[k].rmax=data[l];
55         //t[k].minn=data[l];
56     }
57     else{
58         int mid=(l+r)>>1;
59         buildtree(k<<1, l, mid);
60         buildtree((k<<1)+1, mid+1, r);
61         update(k);
62     }
63 }
64 
65 void modify(int k, int l, int r, int a, int b){
66     if (l==r){
67         t[k].sum=t[k].mins=t[k].maxs=b;
68         t[k].lmin=t[k].rmin=t[k].lmax=t[k].rmax=b;
69         //t[k].minn=b;
70     }
71     else{
72         int mid=(l+r)>>1;
73         if (a<=mid)
74             modify(k<<1, l, mid, a, b);
75         else
76             modify((k<<1)+1, mid+1, r, a, b);
77         update(k);
78     }
79 }
80 
81 int main(){
82     int ans, a, b;
83     scanf("%d", &n);
84     for (int i=1; i<=n; i++) scanf("%d", &data[i]);
85     buildtree(1, 1, n);
86     scanf("%d", &m);
87     while (m--){
88         scanf("%d%d", &a, &b);
89         modify(1, 1, n, a, b);
90         if (t[1].maxs==t[1].sum)
91             ans=t[1].sum-t[1].mins; //not -t[1].minnumber
92         else
93             ans=max2(t[1].maxs, t[1].sum-t[1].mins); //not -t[1].minnumber
94         printf("%d\n", ans);
95     }
96     system("pause");
97     return 0;
98 }
99 

     摘要: 写了题还是应该来总结一下，否则除了个别刻骨铭心的题以外，都忘掉了。 POJ2155题目大意：给一个N*N的矩阵，每次给一个命令取反一个子矩阵，或者查询其中某一点的01状态。（注意每两组output中间要空行，PE了一次） 解题方法；二维线段树。 解题小结：原先好像写过二维的线段树，不过都忘得差不多了，这一次算是重新捡起来吧。这一道题可以用a[rootx][rooty]来记录rootx段到ro...  阅读全文

     摘要: 准备ACM，看了一下STL库。http://www.docin.com/p-46121844.html豆丁这个PDF不错，福州大学的，感觉简明扼要刚好够ACM用。很水，所以做水题。每一道题都能多发现几个有用的函数。map很多时候都不是最好的办法，自己写hash估计其实会更快的，不过既然是熟悉map，就全部用map了。相关的POJ题目, 搜索"poj map"然后找出来的可以用map解决的题目。PO...  阅读全文

     摘要: [hdu3236] Gift Hunting （转自自己的CSDN博客） 一、题目描述 原题地址: http://acm.hdu.edu.cn/showproblem.php?pid=3236 GG有两张奖券，面额分别为V1、V2，准备给MM买礼物。当天是MM生日，所以MM还可以免费得到一份礼物。 礼物有价格和幸福值两个参数，并且礼物分为特殊礼物和普通礼物，特殊礼物是一定要全部到手的。 ...  阅读全文

     摘要: [hdu3234] Exclusive-OR （从自己的CSDN博客转来的） 一、题目描述 http://acm.hdu.edu.cn/showproblem.php?pid=3234 存在n个正数。题目逐渐给出信息或询问。 如果中途出现冲突，输出有冲突，其余语句全部忽略。 详见原题。 二、准备知识 对于a,b,c有：a xor b == c 和 a xor c == b 和 b ...  阅读全文

Hdu 3265 Posters

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3265

    很多很多海报，每张海报又被挖掉了一个长方形。求这些海报的覆盖面积。

题目分析：

    一张海报可以拆成四个矩形处理。线段树。

小结：

Long long 还是不要用printf输出，用cout吧……

Hdu 3231 Box Relations

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3231

    给定一些正方体的关系，要求一组符合这些关系的正方体坐标，如果不存在符合条件的正方体坐标，IMPOSSIBLE。(Special Judge)

 

题目分析：

    首先把正方体这个立体问题拆分成X，Y，Z三个维度上的的平面问题。三个维度上的平面问题处理完了，正方体问题也就处理完了。

    首先想到了差分约束系统，但是我的SPFA呃，TLE了……（求一个不TLE的差分约束系统标程……）

    上网搜索了一个大牛的文，说只需要拓补排序就可以了，完全不需要差分约束。

    再想一想，此题如果用差分约束系统来做，所有边权都是-1。其实不如更直观地进行构图，例如a<b，那么就构图map[a][b] = 1，也就是不妨看做a到b的边权为1。其实进行一下拓补排序，根据点的拓补排序的结果就可以直接作为答案输出，如果拓补排序失败也就是IMPOSSIBLE。

 

代码：

Hdu 3237 Help Bubu

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3237

    题目可以抽象成这样，有0~7这样8个数字组成的数字串，可以抽出k个数字再插回到任意位置，问最后不同的数字段（相同的数字组成一段，例如00077112有4段，000为一段，77为一段……）

 

题目分析：

    这个题乍一看很像动态规划，但是真的是动态规划，不过我还是第一次做这样的动态规划。

    参考了一位大牛的报告，地址如下：

F[i][j][k][s]，表示前i本书，拿走j本，留下的书最后一本高k（呃我觉得这个很巧妙），留下的书的组合为s（例如1010000表示高度为0的，高度为2的书有留下的）

    状态转移部分伪代码（当处理到f[i][j][k][s]时）

(1)  考虑第i本书不抽走，在f[i-1][j][k][s]存在的前提下（也就是处理到i-1本书的时候，这个状态下，留下的最后一本书高度为k）：

若这本书的高度也是k，那么这本书的加入不会造成混乱度的提升，则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s])

若这本书的高度不是k，那么这本书的加入会造成混乱度增加1，则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s] + 1)

（2）考虑抽走第i本书，f[now][j+1][k][s] = min( f[pre][j][k][s], f[now][j+1][k][s])

最后处理答案的时候要考虑一下那些被抽走的书还是要插回去的。如果有一本高度为h的书被抽走，剩下的书里头都没有高度为h的，那么混乱度需要增加。

 

代码：

     摘要: Hdu3229 Jinyuetuan Puzzle 题目大意：     原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=3229     劲乐团游戏，得分种类： 1、  single note，按一下键得一个cool 2、  strip note，开始时按一下键得...  阅读全文

     摘要: Hdu3225 Flowers Placement 题目大意：     原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=3225     给定每个位置上不可以出现的数字，求N满足以上要求的第K(1<=K<=80)大的N（1<=N<=200）的全排列。 题目分析：...  阅读全文