鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

LA-3938-"Ray, Pass me the dishes!" 解题报告 -

来源:互联网 作者:佚名 时间:2015-08-09 07:33
多么经典的线段树题。题意:给你n个数,m个查询,(n和m都小于500000,每个数的绝对都不大于10亿)每个查询给你一个区间[a,b],请你求出这个区间的最大连续和的左端点和右端点并输出,如果有多组解,输出左端点最小的那组解,如果还有多解,输出右端点最小的

       多么经典的线段树题。题意:给你n个数,m个查询,(n和m都小于500000,每个数的绝对值都不大于10亿)每个查询给你一个区间[a,b],请你求出这个区间的最大连续和的左端点和右端点并输出,如果有多组解,输出左端点最小的那组解,如果还有多解,输出右端点最小的那组解。


       我的解题思路:《算法竞赛入门经典--训练指南》中有对这道题目的分析。我求区间最大连续和,在构造线段树时维护了这么几个节点:区间和sum,最大连续和max_sub,最大前缀和max_pre,最大后缀和max_suf以及前缀和右端点prer,后缀和左端点sufl和连续和左右端点subl与subr。假设要查询区间[a,c]且b在ac之间(不一定要是ac的中点),那么求这些和有这样的递推式(区间和sum不用说了):

max_pre[a,c] = max( max_pre[a,b],  sum[a,b] + max_pre[b,c] )

max_suf[a,c] = max( max_suf[b,c],  sum[b,c] + max_suf[a,b] )

max_sub[a,c] = max( max_sub[a,b],  max_sub[b,c],  max_pre[a,b] + max_suf[b,c] )

可以仔细想想为什么递推式是这样,通过这样的递推式也可以确定端点的位置。另外,由于有多组答案时要输出左端点尽量小的,还有多组答案时输出右端点尽量少的,所以在递推式里面某些式子相等的情况下,因为它们的左右端点不一样,所以优先级不同,要注意输出题目要求的答案。


       我的解题代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>

using namespace std;

#define N 500000

typedef long long INT;

struct tree
{
    int left, right, mid;
    INT max_pre;    //最大前缀和
    INT max_sub;    //最大连续和
    INT max_suf;    //最大后缀和
    INT sum;        //区间和
    int subl, subr, prer, sufl;     //分别是连续和左右端点,前缀和右端点,后缀和左端点
};

tree node[N<<2];
int n, m;

#define LL(x) x << 1
#define RR(x) x << 1 | 1

void BuildTree(int left, int right, int x);     //建立线段树

tree Query(int left, int right, int x);         //查询区间节点

int main()
{
    int tn = 1, a, b;
    while (~scanf("%d %d", &n, &m))
    {
        BuildTree(1, n, 1);
        printf("Case %d:\n", tn++);
        while (m--)
        {
            scanf("%d %d", &a, &b);
            tree ans = Query(a, b, 1);
            printf("%d %d\n", ans.subl, ans.subr);
        }
    }
    return 0;
}

void BuildTree(int left, int right, int x)
{
    node[x].left = left;
    node[x].right = right;
    node[x].mid = (left + right) >> 1;
    if (left == right)
    {
        scanf("%lld", &node[x].max_sub);
        node[x].sum = node[x].max_suf = node[x].max_pre = node[x].max_sub;
        node[x].subl = node[x].subr = node[x].prer = node[x].sufl = left;
        return;
    }
    int lx = LL(x);
    int rx = RR(x);
    BuildTree(left, node[x].mid, lx);
    BuildTree(node[x].mid + 1, right, rx);
    node[x].sum = node[lx].sum + node[rx].sum;
    //求前缀和信息
    if (node[lx].max_pre >= node[lx].sum + node[rx].max_pre)
    {
        node[x].max_pre = node[lx].max_pre;
        node[x].prer = node[lx].prer;
    }
    else
    {
        node[x].max_pre = node[lx].sum + node[rx].max_pre;
        node[x].prer = node[rx].prer;
    }
    //求后缀和信息
    if (node[rx].max_suf > node[rx].sum + node[lx].max_suf)
    {
        node[x].max_suf = node[rx].max_suf;
        node[x].sufl = node[rx].sufl;
    }
    else
    {
        node[x].max_suf = node[rx].sum + node[lx].max_suf;
        node[x].sufl = node[lx].sufl;
    }
    //求连续和信息
    if (node[lx].max_sub >= max(node[rx].max_sub, node[lx].max_suf + node[rx].max_pre))
    {
        node[x].max_sub = node[lx].max_sub;
        node[x].subl = node[lx].subl;
        node[x].subr = node[lx].subr;
    }
    else if (node[lx].max_suf + node[rx].max_pre >= node[rx].max_sub)
    {
        node[x].max_sub = node[lx].max_suf + node[rx].max_pre;
        node[x].subl = node[lx].sufl;
        node[x].subr = node[rx].prer;
    }
    else
    {
        node[x].max_sub = node[rx].max_sub;
        node[x].subl = node[rx].subl;
        node[x].subr = node[rx].subr;
    }
    return;
}

tree Query(int left, int right, int x)
{
    if (node[x].left == left && right == node[x].right) return node[x];
    int lx = LL(x);
    int rx = RR(x);
    if (right <= node[x].mid)
    {
        return Query(left, right, lx);
    }
    if (left > node[x].mid)
    {
        return Query(left, right, rx);
    }
    tree ans;
    tree a1 = Query(left, node[x].mid, lx);
    tree a2 = Query(node[x].mid + 1, right, rx);
    ans.sum = a1.sum + a2.sum;
    //计算前缀和信息
    if (a1.max_pre >= a1.sum + a2.max_pre)
    {
        ans.max_pre = a1.max_pre;
        ans.prer = a1.prer;
    }
    else 
    {
        ans.max_pre = a1.sum + a2.max_pre;
        ans.prer = a2.prer;
    }
    //计算后缀和信息
    if (a2.max_suf > a2.sum + a1.max_suf) 
    {
        ans.max_suf = a2.max_suf;
        ans.sufl = a2.sufl;
    }
    else 
    {
        ans.max_suf = a2.sum + a1.max_suf;
        ans.sufl = a1.sufl;
    }
    //计算连续和信息
    if (a1.max_sub >= max(a2.max_sub, a1.max_suf + a2.max_pre))
    {
        ans.max_sub = a1.max_sub;
        ans.subl = a1.subl;
        ans.subr = a1.subr;
    }
    else if (a1.max_suf + a2.max_pre >= a2.max_sub)
    {
        ans.max_sub = a1.max_suf + a2.max_pre;
        ans.subl = a1.sufl;
        ans.subr = a2.prer;
    }
    else
    {
        ans.max_sub = a2.max_sub;
        ans.subl = a2.subl;
        ans.subr = a2.subr;
    }
    return ans;
}


上一篇:J2EE规范——JDBC
下一篇:zip4j
网友评论
<